Diviser pour régner et Analyse des Algorithmes

Ce document couvre la méthode algorithmique « diviser pour régner » et son application à l’analyse de plusieurs algorithmes classiques. Il s’adresse aux étudiants en informatique ou en mathématiques souhaitant comprendre la conception, l’analyse et la complexité des algorithmes récursifs, notamment la recherche binaire, les tris (fusion, rapide), la sélection de la médiane et la multiplication matricielle avec l’algorithme de Strassen.

La méthode Diviser-pour-Régner

La méthode « diviser-pour-régner » consiste à résoudre un problème P en trois étapes :

1. Diviser P en sous-problèmes P1, P2, …, PN de même nature mais de taille plus petite.
2. Résoudre récursivement chacun des sous-problèmes.
3. Combiner les solutions des sous-problèmes pour obtenir la solution de P.

Cette méthode est souvent utilisée lorsque le problème initial est trop complexe pour être résolu directement, mais peut être décomposé en problèmes plus simples.

fonction DPR(x)
{
  si x est suffisamment simple alors
    retourner SOLU-AD-HOC(x)
  sinon
    décomposer x en sous-instances x1, …, xk
    pour i = 1 jusqu'à k faire
      yi = DPR(xi)
    combiner les yi pour obtenir y
    retourner y
}

Exemples classiques de Diviser-pour-Régner

Recherche binaire

On cherche un élément x dans une liste triée S[bas..haut].

• Diviser : comparer l’élément central S[milieu] avec x.
• Régner : si x ≠ S[milieu], continuer la recherche dans la moitié où x peut se trouver.
• Combiner : pas nécessaire.

fonction position(bas, haut)
{
  si bas > haut alors
    retourner 0
  milieu = ⌊(bas + haut)/2⌋
  si S[milieu] = x alors
    retourner milieu
  sinon si x < S[milieu] alors
    retourner position(bas, milieu - 1)
  sinon
    retourner position(milieu + 1, haut)
}

Analyse dans le pire cas :

• Une comparaison par division (1 opération).
• Un seul sous-problème de taille n/2 à résoudre.
• Pas d’opération de combinaison.

La complexité W(n) vérifie la relation de récurrence :

W(n) = W(n/2) + 1, avec W(1) = 1.

La solution est W(n) = ⌊log n⌋ + 1 (pour n puissance de 2), démontrée par induction.

Tri par fusion (MergeSort)

Le tri par fusion ordonne un vecteur S de taille n en trois étapes :

1. Diviser le tableau en deux sous-tableaux d’environ n/2 éléments.
2. Résoudre récursivement le tri sur chaque sous-tableau.
3. Combiner les sous-tableaux triés en un seul tableau trié par fusion.

TriFusion(n, S)
{
  h ← n div 2
  m ← n - h
  si n > 1 alors
  {
    copier S[1..h] en U
    copier S[h+1..n] en V
    TriFusion(h, U)
    TriFusion(m, V)
    Fusionner(h, m, U, V, S)
  }
}

L’algorithme de fusion combine deux sous-vecteurs triés U et V en un vecteur S trié :

Fusionner(h, m, U, V, S)
{
  i ← 1; j ← 1; k ← 1;
  while i ≤ h et j ≤ m faire
  {
    si U[i] < V[j] alors
    {
      S[k] ← U[i]
      i ← i + 1
    }
    sinon
    {
      S[k] ← V[j]
      j ← j + 1
    }
    k ← k + 1
  }
  si i > h alors
    copier V[j..m] en S[k..]
  sinon
    copier U[i..h] en S[k..]
}

Analyse dans le pire cas :

• Diviser : calculer le milieu (coût nul).
• Régner : résoudre deux sous-problèmes de taille n/2 → 2W(n/2).
• Combiner : fusion des deux sous-listes triées → n - 1 comparaisons.

La récurrence est :

W(n) = 2 W(n/2) + n - 1, avec W(1) = 0.

La solution est W(n) = O(n log n).

Tri rapide (QuickSort) de Hoare

Le tri rapide choisit un pivot et partitionne le tableau autour de ce pivot :

• Les éléments ≤ pivot sont à gauche.
• Les éléments > pivot sont à droite.

On trie récursivement les sous-tableaux gauche et droit sans fusion.

Quicksort(bas, haut)
{
  si haut > bas alors
  {
    piv ← Pivoter(bas, haut)
    Quicksort(bas, piv - 1)
    Quicksort(piv + 1, haut)
  }
}

Pivoter(bas, haut)
{
  elempivot ← T[bas]
  j ← bas
  pour i de bas+1 à haut faire
    si T[i] < elempivot alors
    {
      j ← j + 1
      échanger T[i] et T[j]
    }
  piv ← j
  échanger T[bas] et T[piv]
  retourner piv
}

Analyse du pire cas :

• Diviser : n - 1 opérations pour le pivotage.
• Régner : un sous-problème de taille n - 1 (déséquilibré).
• Combiner : aucune opération.

La récurrence est :

W(n) = W(n - 1) + n - 1, avec W(0) = 0, ce qui donne une complexité O(n²).

Analyse du meilleur et du cas moyen :

• Partition équilibrée en deux sous-problèmes de taille n/2.
• Récurrence : W(n) = 2 W(n/2) + n - 1.
• Complexité moyenne : O(n log n).

Sélection de la médiane (algorithme Select)

Problème : trouver l’élément k-ième dans un ensemble S de n éléments distincts.

Algorithme naïf :

• trier S en O(n log n), puis prendre l’élément en position k.

Algorithme Select linéaire (plus efficace) :

1. Si |S| ≤ 5, retourner l’élément k-ième directement.
2. Diviser S en groupes de 5 éléments et trouver la médiane de chaque groupe.
3. Construire l’ensemble M des médianes.
4. Calculer m* = Select(M, ⌈|M|/2⌉), la médiane des médianes.
5. Partitionner S en trois ensembles A, B, C en fonction de m* :
• A : éléments > m*
• B : éléments < m*
• C : éléments égaux à m*
6. Déterminer dans quel sous-ensemble se trouve le k-ième élément et appeler récursivement Select.

Complexité : La complexité dans le pire cas satisfait :

W(n) ≤ W(n/5) + W(7n/10) + O(n), ce qui donne une complexité en O(n).

Algorithme de Strassen pour la multiplication matricielle

Multiplication classique de matrices n x n : complexité W(n) = n³.

Pour multiplier deux matrices 2x2, on effectue classiquement 8 multiplications scalaires.

Strassen réduit ce nombre à 7 multiplications scalaires en calculant :

m1 = (a11 + a22)(b11 + b22)
m2 = (a21 + a22) b11
m3 = a11 (b12 - b22)
m4 = a22 (b21 - b11)
m5 = (a11 + a12) b22
m6 = (a21 - a11) (b11 + b12)
m7 = (a12 - a22) (b21 + b22)

Les coefficients de la matrice résultat C sont obtenus par :

C11 = m1 + m4 - m5 + m7
C12 = m3 + m5
C21 = m2 + m4
C22 = m1 + m3 - m2 + m6

Cette méthode s’applique récursivement pour des matrices de taille n = 2^k, en décomposant chaque matrice en 4 sous-matrices n/2 x n/2.

Strassen(n, A, B, C)
{
  si n ≤ seuil alors
    calculer C ← A x B classiquement
  sinon
  {
    partitionner A en A11, A12, A21, A22
    partitionner B en B11, B12, B21, B22
    calculer M1 à M7 avec Strassen(n/2, ...)
    combiner M1 à M7 pour obtenir C
  }
}

Analyse du pire cas :

• W(1) = 1
• W(n) = 7 W(n/2)

En développant la récurrence :

W(n) = 7^log n = n^log 7 ≈ n^2.81

Cette complexité est meilleure que la multiplication classique O(n³).

Glossaire des termes clés

• Diviser-pour-régner : méthode algorithmique consistant à diviser un problème en sous-problèmes plus petits, les résoudre récursivement, puis combiner les résultats.
• Recherche binaire : algorithme de recherche dans une liste triée en divisant la liste en deux à chaque étape.
• Tri par fusion (MergeSort) : algorithme de tri qui divise le tableau en sous-tableaux, trie récursivement puis fusionne.
• Tri rapide (QuickSort) : algorithme de tri qui partitionne le tableau autour d’un pivot et trie récursivement les sous-parties.
• Sélection de la médiane : problème de trouver l’élément k-ième d’un ensemble, avec un algorithme efficace en temps linéaire.
• Algorithme de Strassen : méthode rapide de multiplication matricielle réduisant le nombre de multiplications nécessaires.
• Récurrence : relation définissant la complexité d’un algorithme récursif en fonction de la taille du problème.
• Complexité dans le pire cas : mesure du temps maximal qu’un algorithme peut prendre pour un input donné.
• Complexité moyenne : mesure du temps moyen attendu pour un algorithme sur un ensemble d’inputs.

Points clés à retenir

• La méthode diviser-pour-régner est une stratégie puissante pour concevoir des algorithmes efficaces.
• La recherche binaire a une complexité logarithmique O(log n) grâce à la division répétée par deux.
• Le tri par fusion garantit un tri en O(n log n) en divisant et fusionnant les sous-tableaux.
• Le tri rapide est efficace en moyenne (O(n log n)) mais peut atteindre O(n²) dans le pire cas.
• L’algorithme Select permet de trouver la médiane en temps linéaire, évitant le tri complet.
• L’algorithme de Strassen améliore la multiplication matricielle classique en réduisant la complexité à environ O(n^2.81).
• Les relations de récurrence sont essentielles pour analyser la complexité des algorithmes récursifs.
• La compréhension des cas pire, moyen et meilleur est cruciale pour évaluer la performance réelle d’un algorithme.