Partie 3 : Diviser pour régner¶
Programme officiel (B.O.)¶
B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Méthode « diviser pour régner ». | Écrire un algorithme utilisant la méthode « diviser pour régner ». | La rotation d'une image bitmap d'un quart de tour avec un coût en mémoire constant est un bon exemple. L'exemple du tri fusion permet également d'exploiter la récursivité et d'exhiber un algorithme de coût en n log₂ n dans les pires des cas. |
1. Le principe « diviser pour régner »¶
1.1 Les trois étapes¶
La méthode diviser pour régner (divide and conquer) résout un problème en trois phases :
- Diviser : découper le problème en sous-problèmes plus petits de même nature ;
- Régner (résoudre) : résoudre chaque sous-problème récursivement, jusqu'aux cas de base ;
- Combiner : assembler les solutions des sous-problèmes pour obtenir la solution du problème initial.
1.2 Lien avec la dichotomie¶
La recherche dichotomique (vue en première) est un cas particulier : on divise le tableau en deux, on ne résout qu'un seul sous-problème (la moitié contenant la valeur cherchée), et il n'y a pas d'étape de combinaison.
2. Le tri fusion¶
2.1 Principe¶
Le tri fusion (merge sort) trie un tableau en appliquant « diviser pour régner » :
- Diviser : couper le tableau en deux moitiés ;
- Régner : trier récursivement chaque moitié ;
- Combiner : fusionner les deux moitiés triées en un tableau trié.
2.2 Exemple déroulé¶
Tableau initial : [7, 5, 3, 0, 1, 6, 4, 2]
Diviser : [7, 5, 3, 0] [1, 6, 4, 2]
[7, 5] [3, 0] [1, 6] [4, 2]
[7] [5] [3] [0] [1] [6] [4] [2]
Combiner : [5, 7] [0, 3] [1, 6] [2, 4]
[0, 3, 5, 7] [1, 2, 4, 6]
[0, 1, 2, 3, 4, 5, 6, 7]
2.3 Implémentation¶
def tri_fusion(tab):
if len(tab) <= 1:
return tab
milieu = len(tab) // 2
gauche = tri_fusion(tab[:milieu])
droite = tri_fusion(tab[milieu:])
return fusionner(gauche, droite)
def fusionner(g, d):
resultat = []
i, j = 0, 0
while i < len(g) and j < len(d):
if g[i] <= d[j]:
resultat.append(g[i])
i += 1
else:
resultat.append(d[j])
j += 1
resultat.extend(g[i:])
resultat.extend(d[j:])
return resultat
2.4 Complexité¶
Le tri fusion a une complexité en O(n log₂ n) dans tous les cas (meilleur, moyen et pire).
| Tri | Meilleur cas | Pire cas |
|---|---|---|
| Tri sélection (1re) | O(n²) | O(n²) |
| Tri insertion (1re) | O(n) | O(n²) |
| Tri fusion | O(n log₂ n) | O(n log₂ n) |
Pourquoi O(n log₂ n) ? On divise le tableau en deux à chaque niveau (log₂ n niveaux de récursion) et à chaque niveau, la fusion parcourt tous les n éléments.
2.5 Stabilité¶
Le tri fusion est stable : deux éléments de même valeur conservent leur ordre relatif initial. C'est grâce au <= dans la comparaison de la fusion.
3. Rotation d'image¶
3.1 Le problème¶
On veut faire pivoter une image carrée de 90° dans le sens horaire. L'approche « diviser pour régner » permet de le faire avec un coût en mémoire constant (sans créer de copie de l'image).
3.2 Principe¶
- Diviser : découper l'image en 4 blocs (A, B, C, D) ;
- Régner : appliquer récursivement la rotation à chaque bloc ;
- Combiner : permuter les 4 blocs pour réaliser la rotation.
Avant rotation : Après rotation :
┌─────┬─────┐ ┌─────┬─────┐
│ A │ B │ │ D │ A │
├─────┼─────┤ → ├─────┼─────┤
│ D │ C │ │ C │ B │
└─────┴─────┘ └─────┴─────┘
3.3 Implémentation simplifiée¶
def rotation_matrice(matrice):
n = len(matrice)
if n <= 1:
return matrice
k = n // 2
# Diviser en 4 blocs
A = [ligne[:k] for ligne in matrice[:k]]
B = [ligne[k:] for ligne in matrice[:k]]
C = [ligne[k:] for ligne in matrice[k:]]
D = [ligne[:k] for ligne in matrice[k:]]
# Régner : rotation récursive de chaque bloc
A = rotation_matrice(A)
B = rotation_matrice(B)
C = rotation_matrice(C)
D = rotation_matrice(D)
# Combiner : permutation des blocs
resultat = []
for i in range(k):
resultat.append(D[i] + A[i])
for i in range(k):
resultat.append(C[i] + B[i])
return resultat
3.4 Complexité¶
- Temps : O(n²) pour une image n × n (chaque pixel est traité) ;
- Mémoire : O(1) dans la version en place (on permute les pixels directement dans l'image sans copie complète).
4. Autres exemples¶
4.1 Exponentiation rapide¶
Calculer \(x^n\) en réduisant le nombre de multiplications :
def puissance_rapide(x, n):
if n == 0:
return 1
if n % 2 == 0:
demi = puissance_rapide(x, n // 2)
return demi * demi
return x * puissance_rapide(x, n - 1)
Complexité : O(log₂ n) au lieu de O(n) pour la méthode naïve.
4.2 Recherche du maximum et du minimum simultanés¶
Trouver le maximum et le minimum d'un tableau avec moins de comparaisons :
def min_max(tab, debut=0, fin=None):
if fin is None:
fin = len(tab) - 1
if debut == fin:
return tab[debut], tab[debut]
if fin == debut + 1:
if tab[debut] < tab[fin]:
return tab[debut], tab[fin]
return tab[fin], tab[debut]
milieu = (debut + fin) // 2
min1, max1 = min_max(tab, debut, milieu)
min2, max2 = min_max(tab, milieu + 1, fin)
return min(min1, min2), max(max1, max2)
5. Quand utiliser « diviser pour régner » ?¶
| Condition | Description |
|---|---|
| Décomposable | Le problème peut être découpé en sous-problèmes de même nature |
| Indépendance | Les sous-problèmes sont indépendants (sinon → programmation dynamique) |
| Combinaison efficace | La fusion des solutions est rapide |
À retenir¶
| Concept | Description |
|---|---|
| Diviser pour régner | Diviser → Régner (récursion) → Combiner |
| Tri fusion | Divise en 2, trie récursivement, fusionne. O(n log₂ n) |
| Fusion | Combiner deux tableaux triés en un seul. O(n) |
| Rotation d'image | Découper en 4 blocs, tourner chacun, permuter |
| Exponentiation rapide | O(log₂ n) multiplications au lieu de O(n) |
| Complexité type | O(n log n) quand on divise en 2 et combine en O(n) |