Diviser pour régner (informatique)

En informatique, diviser pour régner (du latin ,  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).

Exemples

Exemples détaillés 
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.

Autres exemples 
Voici d'autres exemples d'algorithmes diviser pour régner :
 La transformation de Fourier rapide pour calculer la transformation de Fourier d'un signal ;
 Il existe un algorithme de type diviser pour régner pour la recherche des deux points les plus rapprochés ;
 L'algorithme quickhull et l'algorithme de Shamos pour le calcul de l'enveloppe convexe d'un ensemble de points ;
 Les algorithmes de multiplication de de Karatsuba pour les nombres et de Strassen pour les matrices carrées.

Histoire 

La recherche dichotomique est formalisée dans un article de John Mauchly en 1946, mais l'idée d'utiliser une liste triée pour faciliter la recherche remonte à Babylone en -220. L'algorithme d'Euclide pour calculer le plus grand commun diviseur de deux nombres peut être vu comme un algorithme diviser pour régner (les deux nombres diminuent et on se ramène à un problème plus petit). Gauss décrit la transformée de Fourier rapide en 1805  sans en faire l'analyse de complexité. La transformée de Fourier rapide est redécouverte un siècle plus tard.

John von Neumann invente le tri fusion en 1945. L'algorithme de Karatsuba est inventé par Anatolii A. Karatsuba en 1960 : il multiplie deux nombres de n chiffres en  opérations (voir notations de Landau). Cet algorithme contredit la conjecture d’Andreï Kolmogorov de 1956 qui stipule que  opérations sont nécessaires. Knuth donne une méthode utilisée par les services postaux : les lettres sont triées et séparés en fonction des zones géographiques, puis en sous-zones géographies, etc. Ce tri est le tri radix, décrit pour les machines IBM à cartes () dès 1929.

Intérêts

Complexité 
La faible complexité des algorithmes diviser pour régner est l'un de leurs principaux intérêts. Il existe plusieurs théorèmes facilitant le calcul des complexités des algorithmes de type diviser pour régner. Le principal théorème est le Master theorem. Pour des cas plus complexes on peut citer le théorème d'Akra-Bazzi. La table suivante compare la complexité d'un algorithme naïf et de l'algorithme diviser pour régner pour quelques problèmes (voir Notations de Landau) :

Parallélisme 
Les algorithmes diviser pour régner sont souvent adaptés pour être exécutés sur des machines avec plusieurs processeurs.

Circuits 
Il existe des circuits pour des entrées de taille fixées pour la transformation de Fourier rapide. Il existe également des réseaux de tris pour le tri fusion, appelé le tri bitonique.

Limites

Récursivité 
Les algorithmes diviser pour régner se prêtent naturellement à une écriture récursive. Mais parfois, l'exécution d'algorithmes récursifs peut conduire à un dépassement de pile. On préfère donc parfois un algorithme itératif.

Sous-problèmes redondants 
Lorsque l'on applique « diviser pour régner », il n'y a pas de redondance : chaque sous-problème n’est résolu qu'une seule fois lors des appels récursifs. Par contre, lorsque les sous-problèmes sont redondants, l'algorithme récursif obtenu à partir de « diviser pour régner » peut avoir une mauvaise complexité. Prenons l'exemple du calcul du nème terme de la suite de Fibonacci. L'algorithme suivant est en temps exponentiel en n :

  fonction fibonacci(n)
      si(n = 0 ou n = 1)
          renvoyer 1
      sinon
          renvoyer fibonacci(n-1) + fibonacci(n-2)

Pour pallier cette limite, on peut mémoriser les valeurs déjà calculées afin d'éviter de résoudre les sous-problèmes déjà rencontrés. Il s'agit de la mémoïsation (aussi utilisée en programmation dynamique).

Notes et références

Notes

Références

Voir aussi

Articles connexes
 Arbre de produits
 Programmation dynamique

Liens externes

  Diviser pour régner : tri, exponentiation, nombres de Fibonacci, multiplication matricielle, algorithme de Strassen… : vidéo d'une leçon dans le cadre d'un cours d'introduction à l'algorithmique au MIT.

Méthode algorithmique