Diviser pour régner (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Diviser pour régner.
Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion

En informatique, diviser pour régner (du latin « Divide ut imperes », divide and conquer en anglais) est une technique algorithmique consistant à ː

  1. Diviser ː découper un problème initial en sous-problèmes ;
  2. Régner ː résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
  3. 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[modifier | modifier le code]

La table suivante donne des exemples d'algorithmes en donnant les trois étapes (diviser, régner, combiner).

Diviser Régner Combiner
Recherche dichotomique Pour chercher x dans le tableau trié T[1, .. n],
  • on cherche dans T[1, .. n/2] si x < T[n/2]
  • on cherche dans T[n/2 +1,..n] sinon.
- -
Tri fusion on découpe le tableau T[1, .. n] à trier en deux sous-tableaux T[1, .. n/2] et T[n/2 +1,..n] on trie les deux sous-tableaux T[1, .. n/2] et T[n/2 +1,..n] (récursivement, ou on ne fait rien s'ils sont de taille 1) on calcule une permutation triée du tableu initial en fusionnant les deux sous-tableaux triés T[1, .. n/2] et T[n/2 +1,..n].
Tri rapide on choisit un élément du tableau au hasard qui sera 'pivot' et on permute tous les éléments de manière à placer à gauche du pivot les éléments qui lui sont inférieurs, et à droite ceux qui lui sont supérieurs on trie les deux moitiés de part et d'autre du pivot -

Voici d'autres exemples d'algorithmes diviser pour régner ː

Histoire[modifier | modifier le code]

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[1]. 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 [2] 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[3]. L'algorithme de Karatsuba est inventé par Anatolii A. Karatsuba en 1960 [4] : 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.[1] Ce tri est le tri radix, described pour les machines IBM à cartes (Trieur de cartes IBM (en)) dès 1929[1].

Intérêts[modifier | modifier le code]

Complexité[modifier | modifier le code]

La faible complexité des algorithmes diviser pour régner est l'un de leurs principaux intérêts. Il existe plusieurs théorème 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 complexe 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) ː

Complexité avec l'algorithme naïf Complexité avec l'algorithme diviser pour régner
Recherche dans un tableau trié de taille n O(n) O(log n)
Tri d'un tableau de n éléments O(n²) (voir tri insertion, tri sélection) O(n log n) avec le tri fusion

O(n log n) en moyenne avec le tri rapide

Multiplication de deux nombres avec n chiffres O(n²) avec l'algorithme de Karatsuba

Parallélisme[modifier | modifier le code]

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

Circuits[modifier | modifier le code]

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[modifier | modifier le code]

Récursivité[modifier | modifier le code]

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[modifier | modifier le code]

Lorsque l'on applique « diviser pour régner », ils n'y a pas de redondance ː chaque sous-problème 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 ː

 fonction fibonacci(n)
     si(n = 0 ou n = 1)
         retourne 1
     sinon
         retourne 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[modifier | modifier le code]

  1. a, b et c Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
  2. Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform," IEEE ASSP Magazine, 1, (4), 14–21 (1984)
  3. (en) Donald Knuth, The Art of Computer Programming: Volume 3 Sorting and Searching, (ISBN 0-201-89685-0), p. 159
  4. (en) Anatolii A. Karatsuba et Yuri P. Ofman, « Умножение многозначных чисел на автоматах », Doklady Akademii Nauk SSSR, vol. 146,‎ , p. 293–294 tranduit en anglais dans (en) {{Article}} : paramètre « titre » manquant, Physics-Doklady, vol. 7,‎ , p. 595–596

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]