Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Diviser pour régner (informatique)
Résumé
thumb|652x652px|Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion
En informatique, diviser pour régner (du latin , divide and conquer en anglais) est une technique algorithmique consistant à :
Diviser : découper un problème initial en sous-problèmes ;
Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
Cette technique fournit des algorithmes efficaces pour de nombreux problèmes, comme la recherche d'un élément dans un tableau trié (recherche dichotomique), le tri (tri fusion, tri rapide), la multiplication de grands nombres (algorithme de Karatsuba) ou la transformation de Fourier discrète (transformation de Fourier rapide).
La table suivante donne des exemples d'algorithmes en donnant les trois étapes (diviser, régner, combiner).
On peut utiliser un algorithme diviser pour régner pour effectuer la rotation d'une image d'un quart de tour. Il s'agit d'un exemple pédagogique, enseigné par exemple en France en cours d'informatique au lycée, mais inefficace en pratique car chaque pixel de l'image est déplacé autant de fois qu'il y a d'étape Diviser alors qu'il serait possible avec d'autres algorithme de placer directement chaque pixel à sa destination. L'image à faire pivoter est partagée en quatre carreaux (diviser) et on déplace chaque carreau d'un quart de tour sans le faire tourner sur lui-même (régner) avant de réassembler les carreaux entre eux (combiner). On s'arrête lorsque les carreaux ont une taille de un pixel.
File:Margaret Hamilton - square unprocessed picture.jpg|[[Margaret Hamilton (scientifique)|Margaret Hamilton]] avant rotation
File:Margaret hamilton - divide and conquer rotation 1.jpg|Division n°1
File:Margaret hamilton - divide and conquer rotation 2.jpg|Division n°2
File:Margaret hamilton - divide and conquer rotation 3.jpg|Division n°3
File:Margaret hamilton - divide and conquer rotation 4.jpg|Division n°4
File:Margaret hamilton - divide and conquer rotation 5.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.