Voir la source de Diviser pour régner (informatique)

{{Voir homonymes|Diviser pour régner}}
[[Fichier:Trois étapes illustré avec l'algorithme du tri fusion.svg|thumb|652x652px|Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion]]
En [[informatique]], '''diviser pour régner''' (du [[Proverbe latin|latin]] {{Citation|{{lang|la|''Divide ut imperes''}} }}, ''{{lang|en|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]]).

== Exemples ==
=== Exemples détaillés ===
La table suivante donne des exemples d'algorithmes en donnant les trois étapes (diviser, régner, combiner).
{| class="wikitable"
!
!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 tableau 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.
| -
|}

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 [[Système éducatif en France|lycée]]<ref>{{Lien web|langue = français|année = 2020|titre = Programme de numérique et sciences informatiques de terminale générale|site = [[Éduscol]]|url = https://eduscol.education.fr/document/30010/download}}.</ref>. Il est cependant, dans ce cas, inefficace en pratique. En effet, chaque [[pixel]] de l'image est déplacé autant de fois qu'il y a d'étapes ''Diviser'' alors qu'il serait possible avec d'autres algorithmes 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.
<gallery mode="nolines" perrow="5" caption="Exécution d'un algorithme de rotation d'image d'un quart de tour avec ''Diviser pour régner''.">
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.jpg|Division n°5
File:Margaret hamilton - divide and conquer rotation 6.jpg|Division n°6
File:Margaret hamilton - divide and conquer rotation 7.jpg|Division n°7
File:Margaret hamilton - divide and conquer rotation 8.jpg|Division n°8
File:Margaret hamilton - divide and conquer rotation 9.jpg|Division n°9
</gallery>

=== 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 ;
* L'algorithmes de multiplication [[Algorithme de Karatsuba|de Karatsuba]] pour les nombres ;
* L'algorithme [[Algorithme de Strassen|de Strassen]] pour les [[Matrice (mathématiques)|matrices]] carrées.

== Histoire ==

La recherche dichotomique est formalisée dans un article de [[John William Mauchly|John Mauchly]] en 1946. 

Cependant,  l'idée d'utiliser une liste triée pour faciliter la recherche remonte à [[Babylone]] en -220<ref name="Knuth3" />. 

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).

[[Carl Friedrich Gauss|Gauss]] décrit la transformée de Fourier rapide en 1805 <ref name="Heideman84">{{Article|langue=en|auteur=M. T. Heideman|auteur2=D. H. Johnson|auteur3=C. S. Burrus|titre=Gauss and the history of the fast Fourier transform|revue=IEEE ASSP Magazine|vol=1|numéro=4|p.=14-21|année=1984}}.</ref> 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<ref>{{Harvsp|Knuth|1998|p=159}}.</ref>. L'[[algorithme de Karatsuba]] est inventé par [[Anatoli Karatsouba|Anatolii A. Karatsuba]] en 1960<ref>{{article|langue=ru| nom=Karatsuba | prénom=Anatolii A. |auteur2=Yuri P. Ofman | année=1962 | titre=Умножение многозначных чисел на автоматах | périodique=[[Doklady Akademii Nauk SSSR]] | volume=146 | pages=293–294 |lire en ligne=https://www.researchgate.net/publication/248199959_Umnozenie_mnogoznacnyh_cisel_na_avtomatah_Multiplying_multi-digit_numbers_on_the_machines}} traduit en anglais dans {{article|langue=en|titre=Multiplication of Multidigit Numbers on Automata |périodique=Physics-Doklady | volume=7 | année=1963 | pages=595–596 |présentation en ligne={{Google livre|MrkOAAAAIAAJ}} }}.</ref> : il multiplie deux nombres de ''n'' chiffres en <math>O(n^{\log_2 3})</math> opérations (voir [[Comparaison asymptotique|notations de Landau]]). Cet algorithme contredit la [[conjecture]] d’[[Andreï Kolmogorov]] de 1956 qui stipule que <math>\Omega(n^2)\,\!</math> opérations sont nécessaires. [[Donald Knuth|Knuth]] donne une méthode utilisée par les [[Poste|services postaux]] : les lettres sont triées et séparés en fonction des zones géographiques, puis en sous-zones géographies, etc.<ref name="Knuth3">{{Knuth-TAOCPVol3}}.</ref> 

Ce tri est le [[Tri par base|tri radix]], décrit pour les machines [[IBM]] à cartes ({{Lien|trad=IBM_card_sorter|lang=en|fr=Trieur de cartes IBM}}) dès 1929<ref name="Knuth3" />.

== Intérêts ==

=== Complexité ===
La faible [[complexité en temps|complexité]] des algorithmes ''diviser pour régner'' est l'un de leurs principaux intérêts<ref group = N>L'utilisation du paradigme ''diviser pour régner'' n'est pas une garantie absolue d'optimalité : des algorithmes comme le [[tri faire-valoir]] sont plus mauvais que des algorithmes naïfs bien qu'ils utilisent ce paradigme.</ref>. 

Il existe plusieurs théorèmes facilitant le calcul des [[complexité en temps|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 [[Comparaison asymptotique|Notations de Landau]]) :
{| class="wikitable"
!
!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 par insertion|tri insertion]], [[Tri par sélection|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²)
|<math>O(n^{\log_2 3})</math> avec l'algorithme de Karatsuba
|}

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

=== Circuits ===
Il existe des [[Circuit imprimé|circuits]] pour des entrées de taille fixées pour la [[transformation de Fourier rapide]].

Il existe également des [[Réseau de tri|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 [[algorithme récursif|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<sup>ème</sup> 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|group = N}}

=== Références ===
{{Références}}

== Voir aussi ==
===Articles connexes===
* [[Arbre de produits]]
* [[Programmation dynamique]]

===Liens externes===
*{{lien web|url=http://imss-www.upmf-grenoble.fr/prevert/Prog/Tris/triRapideEval.html|titre=Évaluation de la complexité pour le tri rapide}}
* {{en}} [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-3-divide-and-conquer-strassen-fibonacci-polynomial-multiplication/ 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]].
{{Palette|Informatique théorique}}{{Portail|informatique|informatique théorique}}

[[Catégorie:Méthode algorithmique]]