Diviser pour régner
Une idée fondamentale 		D&C logo

Page de Philippe Dumas
Diviser pour régner | Maple | Livres
Publications | Adresse | English version

hline

Introduction
Une idée fondamentale
Complexité et récurrences
Suites 2-rationnelles
Comportement asymptotique
Références

La stratégie diviser pour régner consiste à briser un problème en sous-problèmes plus simples de même type, à résoudre ces sous-problèmes, puis à fusionner les résultats obtenus pour apporter une solution au problème posé. Il s'agit donc d'une démarche essentiellement récursive. Les algorithmes de ce type apparaissent comme composés de deux algorithmes; le premier partage le problème en sous-problèmes, le second algorithme fusionne les résultats partiels en le résultat global.

Tri. Le tri-fusion fournit un exemple clair de cette stratégie. La donnée est une liste d'items (on parle aussi de clés) pris dans un ensemble muni d'un ordre total; le but est d'obtenir une liste constituée de ces mêmes éléments mais rangés dans l'ordre [19, pp. 305-307]. L'algorithme fonctionne comme suit :

-
on partitionne la liste en deux demi-listes;
-
on trie chaque demi-liste;
-
on fusionne les deux demi-listes triées.
Le cas de base de l'algorithme est celui où la liste à trier ne comporte qu'une clé.

L'écriture de l'algorithme dépend de la structure informatique choisie pour représenter les données; nous supposons que l'on représente les listes par des tableaux [19, p. 342]; on pourrait tout aussi bien utiliser des listes chaînées [34, chap. 12]. Dans une première version qui est un pseudo-algorithme on fusionne deux listes triées en une troisième. Ceci a l'inconvénient de créer des listes en pagaille et par une transformation de programme on crée la liste fusionnée en place, moyennant l'utilisation d'une liste auxiliaire [20, § 4.3]; en pratique il suffit de pouvoir fusionner deux listes triées représentées par des sous-intervalles d'un tableau, ces sous-intervalles étant contigus de la forme $\left[i,j\right[$ et $\left[j,k\right[$. Dans la procédure Pascal qui suit ces entiers sont donc les paramètres, le tableau étant une variable globale.

Ce point technique étant acquis l'écriture de l'algorithme reflète directement la stratégie diviser pour régner. 

  procedure mergesort(var a:list; i,j:integer);
    var m:integer;
    begin
      if i+1<j then begin
        m:= (i+j) div 2;
        mergesort(a,i,m);
        mergesort(a,m,j);
        merge(a,i,m,j);
        end
    end;

Pour être exhaustif, indiquons une version possible de la fusion. 

 procedure merge(var a:list; i,j,k:integer);
   var m,n,p:integer;
       b: list;
   begin
     m:=i; n:=j; p:=i;
     while (m<j) and (n<k) do begin
       if a[m]<a[n] then begin b[p]:=a[m]; m:=m+1 end
       else begin b[p]:=a[n]; n:=n+1 end;
       p:=p+1;
     end;
     if (m<j) then for n:=m to j-1 do begin b[p]:=a[n]; p:=p+1; end
     else for m:=n to k-1 do begin b[p]:=a[m]; p:=p+1; end;
     for m:=i to k-1 do a[m]:=b[m];
   end;

Le tri rapide emploie aussi la stratégie diviser pour régner. On choisit un élément particulier, par exemple le premier du tableau à trier, puis on partitionne les éléments suivant leur place par rapport à cette clé distinguée; ceci crée deux sous-listes constituées respectivement des éléments plus petits et des éléments plus grands que la clé, auxquelles on va appliquer récursivement le même traitement; la fusion consiste à mettre la clé distinguée à sa bonne place et les deux sous-listes triées respectivement à gauche et à droite de la clé.

Multiplication. La multiplication d'objets disons structurés fournit une autre application de la stratégie diviser pour régner [20, chap. 6]. Un entier naturel dont l'écriture en base B est $(n_{\ell}\ldots n_0)_B$, ce qui s'énonce aussi

\begin{displaymath} n=n_{\ell}B^{\ell}+n_{\ell-1}B^{\ell-1}+\dotsb+n_0,\qquad 0\leq n_0,\ldots,n_{\ell}<B, \end{displaymath}

est vu comme un tableau de chiffres, la i-ième composante valant ni. Pour multiplier deux entiers n et m suivant la méthode de Karatsuba on coupe les tableaux qui les représentent en deux, ce qui fournit des écritures

\begin{displaymath} n=aB^k+b,\qquad m=cB^k+d\,;\end{displaymath}

on calcule les produits

\begin{displaymath} x=(a+b)(c+d),\qquad y=ac,\qquad z=bd\,;\end{displaymath}

enfin on écrit [31, p.34]

nm=yB2k+(x-y-z)Bk+z.

Bien sûr les produits x, y et z sont calculés suivant la même stratégie. On remarque que l'on a effectué trois multiplications là où l'algorithme naïf en emploie quatre et c'est là que réside l'intérêt de la stratégie diviser pour régner.

La multiplication des polynômes se traite de la même façon; la mise en \oe uvre est d'ailleurs plus simple car il n'y a pas de problème de retenue [34, chap. 36]. Dans le même esprit l'algorithme de Strassen [27, p. 7] fournit le produit C=AB de deux matrices A et B décomposées en quatre blocs,

\begin{displaymath} A=\left(\begin{array} {cc} A_{1,1}&A_{1,2}\\ A_{2,1}&A_{2,2... ...y} {cc} C_{1,1}&C_{1,2}\\ C_{2,1}&C_{2,2} \end{array}\right).\end{displaymath}

L'évaluation des sept produits [9, p. 739]

\begin{displaymath} P_1=A_{1,1}(B_{1,2}-B_{2,2}),\quad P_2=(A_{1,1}+A_{1,2})B_{2,2},\end{displaymath}

\begin{displaymath} P_3=(A_{2,1}+A_{2,2})B_{1,1},\quad P_4=A_{2,2}(B_{2,1}-B_{1,1}),\end{displaymath}

\begin{displaymath} P_5=(A_{1,1}+A_{2,2})(B_{1,1}+B_{2,2}),\quad P_6=(A_{1,2}-A_{2,2})(B_{2,1}+B_{2,2}),\end{displaymath}

\begin{displaymath} P_7=(A_{1,1}-A_{2,1})(B_{1,1}+B_{1,2})\qquad\end{displaymath}

fournit la matrice C,

\begin{displaymath} C_{1,1}=-P_2+P_4+P_5+P_6,\quad C_{1,2}=P_1+P_2,\end{displaymath}

\begin{displaymath} C_{2,1}=P_3+P_4,\quad C_{2,2}=P_1-P_3+P_5+P_7.\end{displaymath}

À nouveau on remarque que l'algorithme emploie sept multiplications là où l'algorithme naïf en emploie huit; ceci laisse attendre un meilleur comportement sur de grandes données; il sera quantifié dans la dernière section.

Géométrie. L'algorithmique géométrique emploie elle aussi la stratégie diviser pour régner. Citons par exemple la recherche de l'enveloppe convexe d'un nuage de points ([14, pp. 145, 158] ou [32, p. 112]) ou la construction de son diagramme de Voronoï [32, p. 213]. Dans la recherche de l'enveloppe convexe d'une famille de n points d'un plan, on procède comme suit. On trie d'abord les points suivant leurs abscisses, ce qui les range en une liste p1, $\ldots$, pn. On brise la liste en deux sous-listes de même longueur p1, $\ldots$, pk et pk+1, $\ldots$, pn. On fabrique récursivement les enveloppes convexes des deux sous-listes, le cas d'arrêt étant celui où une liste comporte moins de trois points. Enfin on fusionne les deux enveloppes convexes. La difficulté réside dans cette dernière opération; pour l'accomplir on construit le pont supérieur et le pont inférieur entre les deux enveloppes convexes. On obtient le pont supérieur de la façon suivante : le point pk est le point le plus à droite de l'enveloppe de gauche et pk+1 est le point le plus à gauche de l'enveloppe de droite; on introduit deux variables g et d, initialisées respectivement aux valeurs pk et pk+1 et on note D la droite passant par g et d; si le point qui suit g en parcourant l'enveloppe convexe de gauche dans le sens direct est au dessus de D on remplace g par son successeur; de même si le point qui précède d sur l'enveloppe convexe de droite parcourue dans le sens direct est au dessus de D on remplace d par son prédecesseur; on itère ces deux actions autant que possible; à la fin la droite D fournit le pont supérieur. On procède de même pour le pont inférieur.

hline

Page précédente : Introduction
Page suivante : Complexité et récurrences