Chapitre 8 - Entraînement : Algorithmique avancée et recherche textuelle

---

Diviser pour régner

Exercice 1 - Tri fusion pas à pas

Dérouler à la main le tri fusion sur le tableau [6, 2, 8, 1, 7, 3, 5, 4] en montrant chaque étape de division et de fusion.

Solution

[6, 2, 8, 1, 7, 3, 5, 4]

Division :
[6, 2, 8, 1]           [7, 3, 5, 4]
[6, 2]    [8, 1]       [7, 3]    [5, 4]
[6] [2]   [8] [1]     [7] [3]   [5] [4]

Fusion :
[2, 6]    [1, 8]       [3, 7]    [4, 5]
[1, 2, 6, 8]           [3, 4, 5, 7]
[1, 2, 3, 4, 5, 6, 7, 8]

---

Exercice 2 - Compter les inversions

Une inversion dans un tableau est un couple (i, j) tel que i < j et tab[i] > tab[j]. Écrire un algorithme « diviser pour régner » qui compte le nombre d'inversions en O(n log n), en modifiant le tri fusion.

Solution

def compter_inversions(tab):
    if len(tab) <= 1:
        return tab, 0

    milieu = len(tab) // 2
    gauche, inv_g = compter_inversions(tab[:milieu])
    droite, inv_d = compter_inversions(tab[milieu:])

    fusionne = []
    inversions = inv_g + inv_d
    i, j = 0, 0

    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            fusionne.append(gauche[i])
            i += 1
        else:
            fusionne.append(droite[j])
            inversions += len(gauche) - i
            j += 1

    fusionne.extend(gauche[i:])
    fusionne.extend(droite[j:])
    return fusionne, inversions

>>> compter_inversions([3, 1, 2])[1]
2    # (3,1) et (3,2)

---

Programmation dynamique

Exercice 3 - Rendu de monnaie

a. Avec les pièces {1, 3, 4}, l'algorithme glouton donne-t-il le résultat optimal pour rendre 6 ? Justifier.

b. Remplir le tableau de programmation dynamique pour rendre la somme 7 avec les pièces {1, 3, 4}.

c. Quelles pièces sont utilisées ?

Solution

a. Glouton : 4 + 1 + 1 = 3 pièces. Optimal : 3 + 3 = 2 pièces. Non, le glouton n'est pas optimal.

b. Tableau nb_pieces[s] :

s	0	1	2	3	4	5	6	7
nb_pieces	0	1	2	1	1	2	2	2

c. Pour rendre 7 : nb_pieces[7] = 2. Reconstruction : 7 - 3 = 4, 4 - 4 = 0. Pièces : 3 et 4.

---

Exercice 4 - Distance d'édition

Calculer la distance d'édition entre "NICHE" et "CHIEN" en construisant le tableau de programmation dynamique.

Solution

		C	H	I	E	N
	0	1	2	3	4	5
N	1	1	2	3	4	4
I	2	2	2	2	3	4
C	3	2	3	3	3	4
H	4	3	2	3	4	4
E	5	4	3	3	3	4

Distance d'édition = 4.

---

Recherche textuelle

Exercice 5 - Boyer-Moore

a. Construire la table du mauvais caractère pour le motif "ALGO".

b. Dérouler l'algorithme de Boyer-Moore pour chercher "ALGO" dans "ANALOGIQUE". Indiquer chaque comparaison et chaque décalage.

Solution

a. Table du mauvais caractère : {'A': 0, 'L': 1, 'G': 2, 'O': 3}

b.

Position 0 : ANALOGIQUE
             ALGO
             Comparaison droite à gauche : O vs L → mismatch
             L est en position 1 du motif, décalage = 3-1 = 2 → avancer de 2

Position 2 : ANALOGIQUE
               ALGO
               O vs L → mismatch
               L en position 1, décalage = 3-1 = 2 → avancer de 2

Position 4 : ANALOGIQUE
                 ALGO
                 O vs O ✓, G vs G ✓, L vs L ✓, A vs O → mismatch
                 O en position 3, décalage = 0-3 < 0 → avancer de 1

Position 5 : ANALOGIQUE
                  ALGO
                  O vs I → mismatch
                  I absent du motif → avancer de j+1 = 4

Motif non trouvé dans le texte.

---

Activités

Activité 1 - Comparer naïf et Boyer-Moore

Instrumenter les algorithmes de recherche naïf et Boyer-Moore pour compter le nombre de comparaisons de caractères effectuées. Tester sur des textes de longueurs croissantes et tracer un graphique comparatif.

Solution

import random
import string

def recherche_naive_compteur(texte, motif):
    comparaisons = 0
    n, m = len(texte), len(motif)
    positions = []
    for i in range(n - m + 1):
        j = 0
        while j < m:
            comparaisons += 1
            if texte[i + j] != motif[j]:
                break
            j += 1
        if j == m:
            positions.append(i)
    return positions, comparaisons

def boyer_moore_compteur(texte, motif):
    comparaisons = 0
    n, m = len(texte), len(motif)
    if m == 0:
        return [], 0
    table = {}
    for i in range(len(motif)):
        table[motif[i]] = i
    positions = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0:
            comparaisons += 1
            if motif[j] != texte[i + j]:
                break
            j -= 1
        if j < 0:
            positions.append(i)
            i += 1
        else:
            c = texte[i + j]
            if c in table:
                decalage = j - table[c]
                i += max(1, decalage)
            else:
                i += j + 1
    return positions, comparaisons

motif = "ALGO"
for taille in [100, 500, 1000, 5000]:
    texte = ''.join(random.choices(string.ascii_uppercase, k=taille))
    _, comp_naive = recherche_naive_compteur(texte, motif)
    _, comp_bm = boyer_moore_compteur(texte, motif)
    print(f"n={taille:5d} | Naïf : {comp_naive:6d} comparaisons | "
          f"Boyer-Moore : {comp_bm:6d} comparaisons")

---

Projet

Projet - Visualiseur d'algorithmes

Créer un programme Python qui visualise le fonctionnement des algorithmes étudiés, avec un menu permettant de choisir :

1. Tri fusion : affichage pas à pas des divisions et fusions ;
2. ABR : construction visuelle par insertions successives ;
3. Parcours de graphe : DFS et BFS animés sur un graphe.

Solution

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit

def afficher_arbre(noeud, prefixe="", est_gauche=True):
    if noeud is None:
        return
    connecteur = "├── " if est_gauche else "└── "
    print(prefixe + connecteur + str(noeud.valeur))
    nouveau_prefixe = prefixe + ("│   " if est_gauche else "    ")
    if noeud.gauche or noeud.droit:
        if noeud.gauche:
            afficher_arbre(noeud.gauche, nouveau_prefixe, True)
        else:
            print(nouveau_prefixe + "├── (vide)")
        if noeud.droit:
            afficher_arbre(noeud.droit, nouveau_prefixe, False)
        else:
            print(nouveau_prefixe + "└── (vide)")

def demo_tri_fusion():
    def tri_fusion_visuel(tab, profondeur=0):
        indent = "  " * profondeur
        print(f"{indent}tri_fusion({tab})")
        if len(tab) <= 1:
            return tab
        m = len(tab) // 2
        g = tri_fusion_visuel(tab[:m], profondeur + 1)
        d = tri_fusion_visuel(tab[m:], profondeur + 1)
        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:])
        print(f"{indent}→ fusionné : {resultat}")
        return resultat

    print("=== TRI FUSION ===")
    tri_fusion_visuel([6, 2, 8, 1, 7, 3])

def demo_abr():
    print("\n=== CONSTRUCTION D'UN ABR ===")
    def inserer(arbre, val):
        if arbre is None:
            return Noeud(val)
        if val < arbre.valeur:
            arbre.gauche = inserer(arbre.gauche, val)
        elif val > arbre.valeur:
            arbre.droit = inserer(arbre.droit, val)
        return arbre

    racine = None
    for val in [7, 3, 11, 1, 5, 9]:
        racine = inserer(racine, val)
        print(f"\nAprès insertion de {val} :")
        afficher_arbre(racine)

def demo_parcours_graphe():
    from collections import deque
    print("\n=== PARCOURS DE GRAPHE ===")
    graphe = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    print("DFS depuis A :")
    visites = set()
    pile = ['A']
    while pile:
        s = pile.pop()
        if s not in visites:
            visites.add(s)
            print(f"  Visite : {s}")
            for v in reversed(graphe[s]):
                if v not in visites:
                    pile.append(v)

    print("\nBFS depuis A :")
    visites = set(['A'])
    file = deque(['A'])
    while file:
        s = file.popleft()
        print(f"  Visite : {s}")
        for v in graphe[s]:
            if v not in visites:
                visites.add(v)
                file.append(v)

print("Choisir une démonstration :")
print("1. Tri fusion")
print("2. ABR")
print("3. Parcours de graphe")
choix = input("Votre choix (1/2/3) : ")
if choix == "1":
    demo_tri_fusion()
elif choix == "2":
    demo_abr()
elif choix == "3":
    demo_parcours_graphe()