12 — Diviser pour Régner : Cours complet

Niveau : Université — Durée : 4h de cours + 4h de TP

---

Partie I — Le principe

1.1 Les 3 étapes

1. Diviser : découper le problème en sous-problèmes plus petits (souvent 2, de taille n/2).
2. Conquérir : résoudre récursivement chaque sous-problème (cas de base : instance triviale).
3. Combiner : assembler les solutions des sous-problèmes pour produire la solution globale.

def divide_and_conquer(problème):
    if trivial(problème):
        return résolution_directe(problème)     # cas de base
    sous = diviser(problème)                     # 1. DIVISER
    résultats = [divide_and_conquer(s) for s in sous]  # 2. CONQUÉRIR
    return combiner(résultats)                   # 3. COMBINER

1.2 Caractère distinctif : sous-problèmes DISJOINTS

Contrairement à la DP, les sous-problèmes du divide & conquer sont indépendants : aucune mémorisation nécessaire.

---

Partie II — Analyse de récurrences et Master Theorem

2.1 Forme générale

La complexité d'un D&C s'écrit :

T(n) = a·T(n/b) + f(n)

• a = nombre de sous-problèmes
• n/b = taille de chaque sous-problème
• f(n) = coût de division + combinaison

2.2 Master Theorem (3 cas)

Soit T(n) = a·T(n/b) + f(n) avec a ≥ 1, b > 1. On compare f(n) avec n^(log_b a) (noté n^c).

Cas 1 : si f(n) = O(n^(c−ε)) pour ε > 0 (le travail récursif domine) →

T(n) = Θ(n^c)

Cas 2 : si f(n) = Θ(n^c · log^k n) (équilibre) →

T(n) = Θ(n^c · log^(k+1) n)

Cas 3 : si f(n) = Ω(n^(c+ε)) pour ε > 0 et a·f(n/b) ≤ k·f(n) pour k < 1 (le travail de combinaison domine) →

T(n) = Θ(f(n))

2.3 Exemples d'application

2.4 Quand le Master Theorem ne s'applique pas

• Tailles non régulières (T(n) = T(n/3) + T(2n/3) + O(n)) → arbre de récurrence.
• Master theorem généralisé (Akra-Bazzi) pour les cas limites.
• Pour ces cas : dessiner l'arbre de récurrence et sommer les niveaux.

---

Partie III — Merge Sort

3.1 Algorithme

1. Diviser : couper le tableau en 2 moitiés.
2. Conquérir : trier récursivement chaque moitié.
3. Combiner : fusionner deux tableaux triés en un seul (O(n)).

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # diviser + conquérir
    right = merge_sort(arr[mid:])
    return merge(left, right)        # combiner

def merge(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    return res + a[i:] + b[j:]

3.2 Analyse

• Récurrence : T(n) = 2T(n/2) + O(n) → Θ(n log n).
• Stable : oui (ordre des égaux préservé).
• En place : non (mémoire O(n) pour la fusion).

---

Partie IV — Quick Sort

4.1 Algorithme

1. Choisir un pivot.
2. Partitionner : éléments < pivot à gauche, > pivot à droite.
3. Trier récursivement les 2 partitions (le pivot est à sa place finale).

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)   # pivot à sa place
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

4.2 Complexité

• Meilleur/moyen : Θ(n log n) — pivot au milieu.
• Pire : Θ(n²) — pivot min ou max à chaque fois (tableau déjà trié + dernier pivot).
• Randomisation du pivot → le pire devient improbable (O(n log n) attendu).

4.3 Merge vs Quick

---

Partie V — QuickSelect

Problème : trouver le k-ième plus petit élément (k-th smallest). Trie : O(n log n). QuickSelect : O(n) attendu.

import random

def quickselect(arr, k):           # k : 0-indexé
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    if k < len(less):
        return quickselect(less, k)
    if k < len(less) + len(equal):
        return pivot
    return quickselect(greater, k - len(less) - len(equal))

• Récurrence : T(n) = T(n/2) + O(n) (en moyenne, partition en 2) → O(n) attendu.
• Pire : O(n²).
• Utilisation : médiane, percentile, k-th largest.

---

Partie VI — Binary Search et variantes

6.1 Binary search classique

def binary_search(arr, x):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x: return mid
        if arr[mid] < x: lo = mid + 1
        else:            hi = mid - 1
    return -1

Complexité : O(log n).

6.2 Recherche dans un tableau roté

Un tableau trié est pivoté : [4,5,6,7,0,1,2]. Retrouver x en O(log n).

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target: return mid
        if nums[lo] <= nums[mid]:            # moitié gauche triée
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                # moitié droite triée
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

6.3 Find peak (pic local)

Un pic est un élément ≥ ses voisins. Dans un tableau (pas forcément trié), un pic existe toujours.

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1        # le pic est à droite
        else:
            hi = mid            # le pic est à gauche (ou mid)
    return lo

6.4 Autres variantes

• Lower bound : premier index avec arr[i] ≥ x.
• Upper bound : premier index avec arr[i] > x.
• Search in 2D sorted matrix : O(log n + log m) ou O(n + m).
• Binary search sur la réponse : vérifier une propriété monotone (ex. minimiser le temps max).

---

Partie VII — Exponentiation rapide

def power(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res *= a
        a *= a
        n >>= 1
    return res

• O(log n) multiplications (au lieu de n).
• Version modulo : même code avec res = res * a % m.
• Utilisation : cryptographie (RSA : base^exp mod n), Fibonacci matriciel (chapitre 14).

---

Partie VIII — Strassen (multiplication de matrices)

8.1 Multiplication naïve

• 3 boucles imbriquées : O(n³).

8.2 Découpage par blocs (D&C)

• Multiplier 2 matrices n×n en 8 produits de n/2 × n/2 : T(n) = 8T(n/2) + O(n²) → Θ(n³) (pas mieux que la méthode naïve !).

8.3 L'astuce de Strassen

Strassen calcule les 8 produits en seulement 7 multiplications (au prix de 18 additions) :

P1 = (A11+A22)(B11+B22)
P2 = (A21+A22)B11
P3 = A11(B12−B22)
P4 = A22(B21−B11)
P5 = (A11+A12)B22
P6 = (A21−A11)(B11+B12)
P7 = (A12−A22)(B21+B22)

C11 = P1+P4−P5+P7
C12 = P3+P5
C21 = P2+P4
C22 = P1−P2+P3+P6

Récurrence : T(n) = 7T(n/2) + O(n²) → Θ(n^log₂7) ≈ Θ(n^2.81).

Les algorithmes modernes (Coppersmith–Winograd, plus récents) atteignent ~O(n^2.37), mais avec de très grandes constantes — inutilisables en pratique sauf pour n énormes.

---

Partie IX — Closest Pair of Points

Problème : étant donné n points du plan, trouver la paire de distance euclidienne minimale.

9.1 Force brute

O(n²). On peut faire O(n log n) :

1. Trier par x.
2. Récursivement : closest pair gauche, droite → δ = min(gauche, droite).
3. Fusion : ne considérer que les points à distance < δ de la ligne médiane, triés par y, et comparer chaque point avec ses 7 suivants seulement.

def closest_pair(points):
    points.sort()                    # par x
    return _closest(points)

def _closest(pts):
    if len(pts) <= 3:
        return brute_force(pts)
    mid = len(pts) // 2
    dl = _closest(pts[:mid])
    dr = _closest(pts[mid:])
    d = min(dl, dr)
    strip = [p for p in pts if abs(p[0] - pts[mid][0]) < d]
    strip.sort(key=lambda p: p[1])   # par y
    for i in range(len(strip)):
        for j in range(i + 1, min(i + 7, len(strip))):
            if strip[j][1] - strip[i][1] < d:
                d = min(d, dist(strip[i], strip[j]))
    return d

Clé de l'analyse : dans une bande de largeur 2δ, un point ne peut avoir au plus que 7 voisins dans sa fenêtre y (propriété géométrique du pavage par carrés δ/2) → la fusion est O(n).

Complexité : T(n) = 2T(n/2) + O(n log n) → O(n log² n) ; avec tri par y en O(n) (pre-sort) → O(n log n).

---

Partie X — FFT : Cooley-Tukey

10.1 Problème

Multiplier 2 polynômes de degré n−1 (ou transformer un signal). Naïf : O(n²).

10.2 Idée

• Évaluer les polynômes en n points (racines n-ièmes de l'unité).
• Utiliser la divisibilité : X(n) = X_pair(x²) + x·X_impair(x²).
• Cooley-Tukey exploite cette décomposition récursivement.

10.3 Récurrence

T(n) = 2T(n/2) + O(n) → O(n log n).

10.4 Applications

• Multiplication polynomiale : convolution O(n log n).
• Multiplication de grands nombres : Schönhage–Strassen (division).
• Traitement du signal : spectre, filtrage, JPEG/MP3.
• Solveurs d'équations, calcul d'autocorrélation.

---

Partie XI — Récapitulatif des complexités

---

Check-list de maîtrise

• Je sais appliquer les 3 étapes (diviser/conquérir/combiner).
• Je sais écrire et résoudre une récurrence D&C.
• Je sais identifier le bon cas du Master Theorem.
• J'ai implémenté merge sort, quick sort, quickselect, binary search.
• Je sais résoudre search rotated et find peak.
• Je sais expliquer l'astuce de Strassen (7 produits).
• Je sais pourquoi closest pair fonctionne en O(n log n).
• Je sais différencier D&C et DP.