Algorithme diviser pour régner

Diviser pour régner (informatique)

Page d'aide sur l'homonymie Pour les articles homonymes, voir Diviser pour régner.

Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous-problèmes analogues. L'étape de subdivision est appliquée récursivement. Son nom est inspiré du proverbe « Diviser pour régner » (en latin : « Divide ut imperes  »)

Sommaire

Présentation

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

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

Tri fusion

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

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érieur
  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é

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

Théorème

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

Exemple

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

Cas des sous-problèmes de même taille

Théorème 1

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

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

Théorème 2

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 ε > 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 ε > 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(logk(n)) avec k > = 1 alors C(n) = O(logk + 1(n))

Exemple 2

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

Exemples

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Diviser pour r%C3%A9gner (informatique) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme diviser pour régner de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Diviser Pour Régner (Informatique) — Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de subdivision est appliquée récursivement …   Wikipédia en Français

  • Diviser pour regner (informatique) — Diviser pour régner (informatique) Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de… …   Wikipédia en Français

  • Diviser Pour Régner — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Diviser pour régner à l origine provient du latin « Divide et impera » : En politique et en sociologie, diviser pour régner est une… …   Wikipédia en Français

  • Diviser pour regner — Diviser pour régner Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Diviser pour régner à l origine provient du latin « Divide et impera » : En politique et en sociologie, diviser pour… …   Wikipédia en Français

  • Diviser pour régner (informatique) — Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner (divide and conquer) est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de subdivision est… …   Wikipédia en Français

  • Diviser pour régner — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Diviser pour régner provient du latin « Divide et impera ». La phrase correspondante en grec ancien est « Διαίρει καὶ βασίλευε »… …   Wikipédia en Français

  • Algorithme Glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Algorithme génétique — Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d obtenir une solution approchée à un problème d optimisation, lorsqu il n existe pas de méthode exacte (ou que la solution est inconnue) pour le… …   Wikipédia en Français

  • Algorithme glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Algorithme —  Ne pas confondre avec la notion d algorithme en sport Un algorithme est une suite finie et non ambiguë d’opérations ou d instructions permettant de résoudre un problème. Le mot algorithme vient du nom latinisé du mathématicien persan Al… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”