Exercices - Algorithmique¶
Arbres binaires¶
Exercice 1 - Taille, hauteur et parcours¶
Soit l'arbre binaire suivant :
a. Donner la taille et la hauteur de cet arbre.
b. Donner le résultat de chaque parcours : préfixe, infixe, suffixe, largeur.
c. Cet arbre est-il un ABR ? Justifier.
Solution
a. Taille = 7 nœuds. Hauteur = 3 (chemin 15 → 9 → 4 → 2).
b. - Préfixe (R-G-D) : 15, 9, 4, 2, 12, 10, 20, 25 - Infixe (G-R-D) : 2, 4, 9, 10, 12, 15, 20, 25 - Suffixe (G-D-R) : 2, 4, 10, 12, 9, 25, 20, 15 - Largeur : 15, 9, 20, 4, 12, 25, 2, 10
c. Oui, c'est un ABR : le parcours infixe donne les valeurs dans l'ordre croissant, et pour chaque nœud, les valeurs à gauche sont inférieures et celles à droite sont supérieures.
Exercice 2 - Construction d'un ABR¶
a. Construire l'ABR obtenu en insérant successivement les valeurs : 7, 3, 11, 1, 5, 9, 13, 4, 8.
b. Quelle est la hauteur de l'arbre obtenu ?
c. En insérant les mêmes valeurs dans un autre ordre, peut-on obtenir un arbre de hauteur différente ? Donner un exemple.
Solution
a.
b. Hauteur = 3.
c. Oui. En insérant dans l'ordre croissant 1, 3, 4, 5, 7, 8, 9, 11, 13, on obtient un arbre filiforme de hauteur 8 (dégénéré en liste). L'ordre d'insertion détermine la forme de l'ABR.
Exercice 3 - Fonctions récursives sur les arbres¶
Écrire les fonctions suivantes :
a. somme(arbre) : renvoie la somme de toutes les valeurs.
b. recherche(arbre, valeur) : renvoie True si la valeur est dans l'arbre (arbre quelconque, pas un ABR).
c. miroir(arbre) : renvoie un nouvel arbre qui est l'image miroir (gauche ↔ droite).
Solution
def somme(arbre):
if arbre is None:
return 0
return arbre.valeur + somme(arbre.gauche) + somme(arbre.droit)
def recherche(arbre, valeur):
if arbre is None:
return False
if arbre.valeur == valeur:
return True
return recherche(arbre.gauche, valeur) or recherche(arbre.droit, valeur)
def miroir(arbre):
if arbre is None:
return None
return Noeud(arbre.valeur, miroir(arbre.droit), miroir(arbre.gauche))
Graphes¶
Exercice 4 - Parcours DFS et BFS¶
Soit le graphe suivant :
graphe = {
'A': ['B', 'D'],
'B': ['A', 'C', 'E'],
'C': ['B', 'F'],
'D': ['A', 'E'],
'E': ['B', 'D', 'F'],
'F': ['C', 'E']
}
a. Donner l'ordre de visite des sommets par un parcours en profondeur à partir de A.
b. Donner l'ordre de visite par un parcours en largeur à partir de A.
c. Donner un plus court chemin de A à F.
Solution
a. DFS depuis A : A, B, C, F, E, D (on explore B d'abord, puis C, puis F, puis E via F, puis D via E ou retour).
b. BFS depuis A : A, B, D, C, E, F (niveau 0 : A, niveau 1 : B et D, niveau 2 : C et E, niveau 3 : F).
c. Plus court chemin de A à F (en nombre d'arêtes) : A → B → C → F (3 arêtes). Ou A → D → E → F (3 arêtes également).
Exercice 5 - Détection de cycle¶
a. Le graphe de l'exercice 4 contient-il un cycle ? Lequel ?
b. Supprimer des arêtes pour obtenir un graphe sans cycle mais restant connexe. Combien d'arêtes reste-t-il ?
Solution
a. Oui, plusieurs cycles. Par exemple : A → B → E → D → A.
b. Un graphe connexe sans cycle (arbre couvrant) sur 6 sommets a exactement 5 arêtes. Par exemple : A-B, B-C, C-F, A-D, D-E.
Diviser pour régner¶
Exercice 6 - 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
Exercice 7 - 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
Programmation dynamique¶
Exercice 8 - 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 9 - 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 10 - 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 - Visualiser les parcours d'arbres¶
Écrire un programme qui construit un arbre binaire et affiche visuellement les étapes de chaque type de parcours (préfixe, infixe, suffixe, largeur), en numérotant l'ordre de visite.
Solution
from collections import deque
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def afficher_parcours(nom, resultat):
print(f"{nom} :")
for i, val in enumerate(resultat, 1):
print(f" Étape {i} : visite du nœud {val}")
print()
arbre = Noeud(15,
Noeud(9, Noeud(4, Noeud(2)), Noeud(12, Noeud(10))),
Noeud(20, None, Noeud(25))
)
def prefixe(a):
if a is None: return []
return [a.valeur] + prefixe(a.gauche) + prefixe(a.droit)
def infixe(a):
if a is None: return []
return infixe(a.gauche) + [a.valeur] + infixe(a.droit)
def suffixe(a):
if a is None: return []
return suffixe(a.gauche) + suffixe(a.droit) + [a.valeur]
def largeur(a):
if a is None: return []
res, file = [], deque([a])
while file:
n = file.popleft()
res.append(n.valeur)
if n.gauche: file.append(n.gauche)
if n.droit: file.append(n.droit)
return res
afficher_parcours("Préfixe", prefixe(arbre))
afficher_parcours("Infixe", infixe(arbre))
afficher_parcours("Suffixe", suffixe(arbre))
afficher_parcours("Largeur", largeur(arbre))
🧪 Activité 2 - Résoudre un labyrinthe¶
Modéliser un labyrinthe sous forme de graphe et écrire un programme Python qui trouve un chemin de l'entrée à la sortie avec un parcours en profondeur, puis le plus court chemin avec un parcours en largeur.
Solution
from collections import deque
labyrinthe = {
(0,0): [(0,1), (1,0)],
(0,1): [(0,0), (0,2)],
(0,2): [(0,1), (1,2)],
(1,0): [(0,0), (2,0)],
(1,2): [(0,2), (1,3)],
(1,3): [(1,2), (2,3)],
(2,0): [(1,0), (2,1)],
(2,1): [(2,0), (2,2)],
(2,2): [(2,1), (2,3)],
(2,3): [(2,2), (1,3)]
}
entree = (0, 0)
sortie = (2, 3)
def chemin_dfs(graphe, depart, arrivee, visites=None):
if visites is None:
visites = set()
visites.add(depart)
if depart == arrivee:
return [depart]
for voisin in graphe[depart]:
if voisin not in visites:
chemin = chemin_dfs(graphe, voisin, arrivee, visites)
if chemin is not None:
return [depart] + chemin
return None
def chemin_bfs(graphe, depart, arrivee):
visites = {depart}
file = deque([(depart, [depart])])
while file:
sommet, chemin = file.popleft()
for voisin in graphe[sommet]:
if voisin not in visites:
nouveau = chemin + [voisin]
if voisin == arrivee:
return nouveau
visites.add(voisin)
file.append((voisin, nouveau))
return None
print("DFS :", chemin_dfs(labyrinthe, entree, sortie))
print("BFS :", chemin_bfs(labyrinthe, entree, sortie))
🧪 Activité 3 - 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 :
- Tri fusion : affichage pas à pas des divisions et fusions ;
- ABR : construction visuelle par insertions successives ;
- 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()