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.

Diviser pour régner (divide and conquer) est une technique algorithmique consistant à abandonner par itération ou récursivité une branche du traitement afin de diminuer l'effort à faire pour obtenir la solution à un problème. Un exemple simple est la recherche dichotomique, qui consiste à diviser un ensemble de données ordonnés en deux, dont l'un des sous ensembles est abandonné au profit de l'autre. Son nom est inspiré du proverbe « Diviser pour régner » (en latin : « Divide ut imperes »)

Présentation[modifier | modifier le code]

Les algorithmes récursifs utilisent naturellement cette technique : ils s'appellent eux-mêmes une ou plusieurs fois sur une partition du problème initial et combinent les solutions pour retrouver une solution au problème initial.

Deux stratégies[modifier | modifier le code]

Les algorithmes Diviser pour régner appliquent deux stratégies principales. La première est la récursivité sur les données : on sépare les données en deux parties quelconques (ou plus), puis on résout les sous-problèmes (par la même fonction), pour enfin combiner les résultats. La seconde stratégie, la récursivité sur le résultat, consiste elle à effectuer un pré-traitement pour bien découper les données, puis à résoudre les sous-problèmes, pour que les sous-résultats se combinent d'eux-mêmes à la fin.

Illustration des stratégies[modifier | modifier le code]

Tri fusion[modifier | modifier le code]

Un exemple de récursivité sur les données est le Tri fusion. La donnée initiale est alors une séquence d'entiers non triée. Le résultat est une séquence triée des mêmes entiers.

  1. on divise la séquence de n éléments à trier en deux sous-séquences de n/2 éléments,
  2. on trie les deux sous-séquences à l'aide du tri fusion (appel récursif),
  3. on combine, en les fusionnant, les deux sous-séquences triées pour produire la séquence triée.

La récursivité prend fin quand pour un appel à l'algorithme, la séquence à trier est de taille 1. Dans ce cas il n'y a rien à faire car par définition une telle séquence est déjà triée.

Tri rapide[modifier | modifier le code]

Un exemple de récursivité sur le résultat est le Tri rapide. La donnée initiale et le résultat sont les mêmes que pour le tri fusion.

  1. on choisit un élément du tableau au hasard qui sera 'pivot' ;
  2. 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 ;
  3. on appelle (récursivement) le tri rapide sur les deux moitiés de part et d'autre du pivot.

Lorsque la séquence à trier est de taille 1, il n'y a plus rien à faire, car le tableau est déjà trié.

Complexité[modifier | modifier le code]

La faible complexité des algorithmes Diviser pour régner est l'un de leurs principaux intérêts.

Notations : n taille du problème, C(n) coût en nombre d'opérations. Pour les notations de comparaison asymptotiques, consulter Notations de Landau

Cas où la résolution d'un seul sous-problème suffit[modifier | modifier le code]

Théorème[modifier | modifier le code]

Si C(n)=C(n/k)+g(n), alors C(n)=C(1)+\sum_{i=1}^{|log_k(n)|}g(k^i)

Exemple[modifier | modifier le code]

Recherche dichotomique 
avec deux comparaisons, on choisit le tableau sur lequel continuer la recherche. C(n)=C(n/2)+2=\sum_{i=1}^{|log_2(n)|}2=O(log_2(n))
Exponentiation rapide

Cas des sous-problèmes de même taille[modifier | modifier le code]

Théorème 1[modifier | modifier le code]

Si C(n)=aC(n/b)+cn, avec C(1)=constante alors

  • si a<b, C(n)=O(n)
  • si a=b, C(n)=O(n.log(n))
  • si a>b, C(n)=O(n^{log_b(a)})

a représente ici le nombre de sous-problèmes et n/b leur taille.

Exemple 1[modifier | modifier le code]

Tri fusion : 2 sous-problèmes de taille n/2, donc a=b=2, donc C(n)=O(n.log_2(n))

Théorème 2[modifier | modifier le code]

Si C(n)=aC(n/k)+f(n) avec a et k deux entiers strictement positifs et f une fonction. Alors

  • si f(n)=O(n^{log_k(a-\epsilon)}) avec \epsilon>0, alors C(n)=\circleddash(n^{log_k(a)})
  • si f(n)=\circleddash(n^{log_k(a-\epsilon)}) alors C(n)=\circleddash(n^{log_k(a)}log(n))
  • si f(n)=\Omega(n^{log_k(a+\epsilon)}) avec \epsilon>0 et si \exist c<1 tel que a.f(n/k) <= cf(n) pour n suffisamment grand, alors C(n)=\circleddash(f(n))
  • si a=1 et f(n)=O(log_k(n)) avec k>=1 alors C(n)=O(log_{k+1}(n))

Exemple 2[modifier | modifier le code]

Si C(n)=2.C(n/3)+\circleddash(n), alors C(n)=\circleddash(n)

Exemples[modifier | modifier le code]

Limites[modifier | modifier le code]

La stratégie de programmation « diviser pour régner » permet de fortement diminuer la complexité temporelle dans le cas où les sous-problèmes à traiter sont indépendants, mais n’est pas optimisée du tout s’ils ne le sont pas. Par exemple, le calcul des coefficients du binôme par la relation de Pascal, ou des termes de la suite de Fibonacci par les algorithmes naïfs suivants (en Caml Light) ne sont pas optimaux, les fonctions étant rappelées plusieurs fois avec les mêmes paramètres :

let rec binom k n = match (k,n) with (* Calcule le nombre de combinaisons de k éléments parmi n *)
    | (_,_) when k = n -> 1
    | (0,_) -> 1
    | (_,_) -> (binom (k-1) (n-1)) + (binom k (n-1));;
 
let rec fibonacci n = match n with
    | 0 -> 1
    | 1 -> 1
    | _ -> fibo (n-1) + fibo (n-2);;

Une stratégie simple pour pallier cette limite est alors de recourir à la programmation dynamique, c’est-à-dire de mémoïzer les valeurs déjà calculées afin d’éviter de reproduire plusieurs fois les mêmes calculs.


Liens externes[modifier | modifier le code]