Algorithmique

⚙️ Chapitre : La méthode « diviser pour régner ».

1️⃣ Principe de la méthode

La méthode diviser pour régner consiste à :

• Diviser un problème en sous-problèmes plus petits ;
• Résoudre ces sous-problèmes (souvent récursivement) ;
• Combiner les résultats pour obtenir la solution finale.

Cette méthode est très efficace lorsque les sous-problèmes sont similaires au problème initial. Elle utilise souvent la récursivité.

Structure générale :

def diviser_regner(probleme):
    
    if cas_simple(probleme):
        return solution_simple
    
    sous_problemes = diviser(probleme)
    
    solutions = [diviser_regner(p) for p in sous_problemes]
    
    return combiner(solutions)

2️⃣ Exemple simple : la recherche dichotomique

La recherche dichotomique permet de chercher une valeur dans une liste triée.

Principe :

• On regarde l’élément du milieu ;
• Si c’est la valeur cherchée → terminé ;
• Sinon on recommence dans la moitié gauche ou droite.

Exemple visuel :

Liste : [2, 5, 8, 12, 16, 23, 38] On cherche 16.

On coupe en deux → on compare avec 12. 16 est plus grand → on garde la moitié droite. On recommence jusqu’à trouver 16.

def recherche_dichotomique(tab, valeur):
    
    gauche = 0
    droite = len(tab) - 1
    
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        
        if tab[milieu] == valeur:
            return milieu
        
        elif tab[milieu] < valeur:
            gauche = milieu + 1
        
        else:
            droite = milieu - 1
    
    return -1

Dans le pire des cas, on divise la taille par 2 à chaque étape. Le nombre d’étapes est donc proportionnel à \(log_2(n) \).

Exemple: la recherche dichotomique d’un mot dans un dictionnaire

La recherche dichotomique permet de chercher une valeur dans une liste triée. Dans cette animation sur le site PhysAlgo, on ouvre un dictionnaire de 386264 mots au milieu, puis on élimine la moitié inutile. Avec cette métode, on trouve le mot en 19 essais dans le pire des cas.

En effet, \( \log_2(386264) \approx 18{,}6 \).

3️⃣ Le tri fusion : diviser pour régner appliqué au tri

Le tri fusion est un algorithme de tri basé sur la même idée :

• Diviser la liste en deux ;
• Trier chaque moitié ;
• Fusionner les deux listes triées.

Exemple visuel :

[8, 3, 6, 2] → on divise : [8, 3] et [6, 2] → on divise encore : [8], [3], [6], [2] → on fusionne : [3, 8] et [2, 6] → fusion finale : [2, 3, 6, 8]

On descend jusqu’à des listes d’un seul élément (cas simple), puis on remonte en fusionnant.

4️⃣ Implémentation simple du tri fusion

def fusion(gauche, droite):
    
    resultat = []
    i = 0
    j = 0
    
    while i < len(gauche) and j < len(droite):
        
        if gauche[i] < droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1
    
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    
    return resultat


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 fusion(gauche, droite)

5️⃣ Complexité du tri fusion

À chaque niveau :

• On divise la liste en deux ;
• On effectue une fusion proportionnelle à n.

Le nombre de niveaux de division est \( \log_2(n) \).

Complexité :

\[O( n \times \log_2(n)) \]

Le tri fusion est donc un algorithme efficace, même dans le pire des cas.

6️⃣ Exemple détaillé du tri fusion

Voici un exemple complet du fonctionnement du tri fusion :

Liste initiale : [4, 7, 3, 9, 1, 2, 5]

🔹 Étape 1 : Division

On découpe la liste en deux parties :

[4, 7, 3] et [9, 1, 2, 5]

On continue à diviser jusqu’à obtenir des listes d’un seul élément. Une liste d’un élément est déjà triée : c’est le cas simple.

🔹 Étape 2 : Fusion

On fusionne ensuite les listes deux par deux.

Exemple :

Fusion de [7] et [3] → on compare 7 et 3 → on place le plus petit d’abord → résultat : [3, 7]

Autre exemple :

Fusion de [9] et [1] → résultat : [1, 9]

On répète le processus jusqu’à obtenir :

[1, 2, 3, 4, 5, 7, 9]

🔹 Ce qu’il faut comprendre

• On descend en divisant (phase "diviser").
• On remonte en fusionnant (phase "régner").
• Chaque niveau traite toute la liste.
• Il y a environ \(\log_2(n) \) niveaux.

C’est cette structure en arbre (visible sur le schéma) qui explique la complexité en \(O( n \times \log_2(n) \)).

7️⃣ À retenir

• Diviser pour régner consiste à découper un problème en sous-problèmes.
• La recherche dichotomique est un premier exemple simple.
• Le tri fusion applique cette méthode au tri.
• Sa complexité est en \( n \times \log_2(n) \).
• À comparer à la complexité quadratique des algorithmes de tri vus en première.

La méthode « diviser pour régner » est fondamentale en algorithmique et permet de concevoir des algorithmes très performants.

🔗 Aucun exercice sur le tri fusion dans la base.