Exercice 1 : QCM
Pour chaque question, une seule réponse est correcte.
1. Le paradigme « diviser pour régner » repose sur trois étapes. Lesquelles ?
- A. Lire, trier, afficher
- B. Diviser le problème, résoudre les sous-problèmes, combiner les résultats
- C. Comparer, échanger, recommencer
- D. Initialiser, itérer, terminer
Correction publiée après la séance.
2. Quelle est la complexité de la recherche dichotomique dans un tableau trié de $n$ éléments ?
- A. $O(n)$
- B. $O(n^2)$
- C. $O(\log n)$
- D. $O(n \log n)$
Correction publiée après la séance.
3. Quelle est la complexité du tri fusion dans le pire cas ?
- A. $O(n^2)$
- B. $O(n)$
- C. $O(2^n)$
- D. $O(n \log n)$
Correction publiée après la séance.
4. Quel est l’inconvénient principal du tri fusion par rapport au tri par insertion ?
- A. Il nécessite de la mémoire supplémentaire proportionnelle à $n$
- B. Sa complexité est moins bonne dans le pire cas
- C. Il n’est pas stable
- D. Il ne fonctionne que sur des entiers
Correction publiée après la séance.
Exercice 2 : dérouler la recherche dichotomique (exercice guidé)
On considère le tableau trié tab = [3, 7, 11, 18, 25, 33, 42, 56, 68] (neuf éléments, indices de 0 à 8).
On cherche la valeur 33.
a) Au départ, les bornes sont gauche = 0 et droite = 8. Calculez l’indice du milieu : milieu = (gauche + droite) // 2. Quelle est la valeur de tab[milieu] ? Est-elle égale à 33, inférieure ou supérieure ?
Indice
Le quotient entier // arrondit vers le bas, et les indices se comptent à partir de 0.
b) En déduire les nouvelles bornes. Recalculez le milieu et comparez tab[milieu] à 33.
Indice
Si tab[milieu] est plus petit que 33, la valeur ne peut être qu’à droite du milieu : gauche = milieu + 1. S’il est plus grand, elle ne peut être qu’à gauche : droite = milieu - 1.
c) Continuez jusqu’à trouver 33. Combien d’étapes ont été nécessaires ?
d) Déroulez maintenant la recherche de la valeur 20 (absente du tableau). À quelle condition l’algorithme s’arrête-t-il en concluant que 20 n’est pas dans le tableau ?
Indice
Suivre l’évolution de gauche et de droite : que se passe-t-il quand gauche dépasse droite ?
e) Combien de comparaisons au maximum faut-il pour un tableau de neuf éléments ? Vérifiez avec la formule $\lfloor \log_2 n \rfloor + 1$.
Indice
$\lfloor \log_2 9 \rfloor$ est le plus grand entier $k$ tel que $2^k \leq 9$.
Correction publiée après la séance.
Exercice 3 : dérouler le tri fusion (exercice guidé)
On souhaite trier le tableau [38, 12, 45, 7, 21, 33] par tri fusion.
a) Première étape : diviser. Coupez le tableau en deux moitiés. Quelles sont-elles ?
Indice
La moitié gauche contient len(tab) // 2 éléments, la moitié droite tous les autres.
b) Continuez à diviser chaque moitié jusqu’à obtenir des tableaux d’un seul élément. Dessinez l’arbre de décomposition complet.
Indice
Écrire sous chaque tableau ses deux moitiés, puis recommencer sur chaque moitié jusqu’à n’avoir que des tableaux d’un seul élément.
c) Deuxième étape : fusionner. On commence par le bas de l’arbre. Fusionnez [12] et [45] en un tableau trié, puis [21] et [33]. Que deviennent [38] et [7], restés seuls à leur niveau ?
Indice
Fusionner deux tableaux triés, c’est comparer leurs premiers éléments et prendre le plus petit, encore et encore. Un tableau resté seul est déjà trié : il remonte tel quel jusqu’à la fusion suivante.
d) Remontez l’arbre en fusionnant les sous-tableaux triés deux à deux. Détaillez chaque fusion en indiquant les comparaisons effectuées.
Indice
À chaque comparaison, le plus petit des deux éléments de tête passe dans le résultat ; quand l’un des deux tableaux est vide, le reste de l’autre est recopié sans comparaison.
e) Combien de comparaisons ont été effectuées au total ? Combien en aurait fait le tri par sélection sur ce même tableau de six éléments ?
Indice
Additionner les comparaisons de toutes les fusions. Le tri par sélection fait toujours $\frac{n(n-1)}{2}$ comparaisons.
Correction publiée après la séance.
Exercice 4 : compléter la fonction fusion (exercice guidé)
La fonction fusion prend deux listes déjà triées et renvoie une seule liste triée contenant tous les éléments. Complétez les parties manquantes (notées ...).
def fusion(gauche, droite):
resultat = []
i, j = 0, 0
while i < len(gauche) and j < len(droite):
if gauche[i] <= droite[j]:
resultat.append(...) # (1)
i += 1
else:
resultat.append(...) # (2)
... # (3)
# Ajouter les éléments restants
resultat.extend(gauche[...]) # (4)
resultat.extend(droite[...]) # (5)
return resultat
a) Que faut-il écrire à la place de (1) et (2) ? Justifiez.
Indice
On ajoute au résultat le plus petit des deux éléments comparés : gauche[i] dans un cas, droite[j] dans l’autre.
b) Que faut-il écrire à la place de (3) ?
Indice
Après avoir pris droite[j], il faut passer à l’élément suivant de droite, comme on le fait pour gauche avec i += 1.
c) Que faut-il écrire à la place de (4) et (5) ? Pourquoi faut-il ajouter les éléments restants ?
Indice
La boucle s’arrête dès qu’une des deux listes est épuisée : les éléments non encore pris de l’autre, déjà triés, se placent à la fin. Le slicing gauche[i:] donne les éléments à partir de l’indice i.
d) Testez votre fonction avec fusion([3, 8, 15], [1, 9, 12]). Détaillez les étapes.
Correction publiée après la séance.
Exercice 5 : programmer le tri fusion
On dispose de la fonction fusion de l’exercice précédent.
a) Quel est le cas de base du tri fusion ? C’est-à-dire : pour quel type de tableau n’a-t-on rien à trier ?
Indice
Un tableau vide, ou d’un seul élément, est-il déjà trié ?
b) Écrivez la fonction tri_fusion(tab) qui :
- renvoie
tabsi c’est le cas de base ; - sinon, coupe
taben deux moitiés, trie récursivement chaque moitié, puis les fusionne.
Indice
Le milieu est len(tab) // 2, et les deux moitiés sont tab[:milieu] et tab[milieu:]. Trier chacune par un appel récursif, puis renvoyer leur fusion.
Code à copier puis compléter
def tri_fusion(tab):
if len(tab) <= 1:
return tab
milieu = len(tab) // 2
gauche = tri_fusion(tab[:milieu])
droite = tri_fusion(...)
return fusion(..., ...)
c) Vérifiez que tri_fusion([38, 27, 43, 3, 9, 82, 10]) renvoie [3, 9, 10, 27, 38, 43, 82].
d) En quoi cet algorithme relève-t-il du paradigme diviser pour régner ? Identifiez chacune des trois étapes (diviser, régner, combiner).
Indice
Associer chaque ligne de tri_fusion à une étape : où coupe-t-on le tableau, où résout-on les sous-problèmes, où rassemble-t-on les résultats ?
Correction publiée après la séance.
Exercice 6 : recherche dichotomique récursive
a) Écrire une fonction récursive recherche_dicho(x, tab, gauche, droite) qui renvoie l’indice de x dans le tableau trié tab (entre les indices gauche et droite), ou $-1$ si x est absent.
Indice
Si gauche > droite, la zone de recherche est vide : renvoyer -1. Sinon, comparer x à l’élément du milieu, puis soit renvoyer milieu, soit relancer la recherche sur la moitié gauche ou sur la moitié droite, avec de nouvelles bornes.
Code à copier puis compléter
def recherche_dicho(x, tab, gauche, droite):
if gauche > droite:
return -1
milieu = (gauche + droite) // 2
if tab[milieu] == x:
return ...
elif tab[milieu] < x:
return recherche_dicho(x, tab, ..., droite)
else:
return recherche_dicho(x, tab, gauche, ...)
b) Écrire une fonction enveloppe chercher(x, tab) qui appelle recherche_dicho avec les bornes initiales.
Indice
Les bornes initiales couvrent tout le tableau : de 0 à len(tab) - 1.
c) En quoi cet algorithme relève-t-il du paradigme diviser pour régner ? Quelle particularité a-t-il par rapport au tri fusion ?
Indice
Combien de sous-problèmes la recherche résout-elle à chaque étape, et y a-t-il une étape de combinaison ?
Correction publiée après la séance.
Exercice 7 : rotation d’un quart de tour d’une image
Une image carrée en niveaux de gris est représentée par une liste de listes (matrice carrée) de dimension $n \times n$, où $n$ est une puissance de deux.
Par exemple, l’image $4 \times 4$ suivante :
image = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
Après rotation d’un quart de tour dans le sens horaire, elle devient :
[
[13, 9, 5, 1],
[14, 10, 6, 2],
[15, 11, 7, 3],
[16, 12, 8, 4]
]
a) Vérifiez sur l’exemple : où se retrouve le pixel en position (0, 0) (valeur 1) après rotation ? Et le pixel en position (3, 0) (valeur 13) ? Quelle est la règle générale : le pixel (i, j) se retrouve en position … ?
Indice
Repérer où vont les pixels de la première ligne, puis ceux de la première colonne : la ligne d’arrivée dépend de j, la colonne d’arrivée de i et de n.
b) Écrire une fonction rotation_directe(image) qui effectue la rotation sans DPR, en appliquant la règle trouvée en a).
Indice
Créer une matrice $n \times n$ remplie de 0, puis, pour chaque couple (i, j), recopier image[i][j] à sa position d’arrivée.
Code à copier puis compléter
def rotation_directe(image):
n = len(image)
resultat = []
for i in range(n):
resultat.append([0] * n)
for i in range(n):
for j in range(n):
resultat[...][...] = image[i][j]
return resultat
c) Voici l’approche diviser pour régner. On découpe l’image $n \times n$ en quatre blocs de taille $\frac{n}{2} \times \frac{n}{2}$ :
Après rotation d’un quart de tour horaire, les blocs se réarrangent ainsi :
où chaque bloc est lui-même tourné d’un quart de tour. Expliquez pourquoi.
Indice
Tourner l’image entière déplace chaque bloc à la place du bloc voisin dans le sens horaire, et fait aussi tourner le contenu de chaque bloc : appliquer la règle de la question a) au coin supérieur gauche de chaque bloc.
d) Écrire les fonctions auxiliaires suivantes :
extraire_bloc(image, ligne_debut, col_debut, taille): renvoie le sous-bloc detaille × taillepixels ;assembler(haut_gauche, haut_droite, bas_gauche, bas_droite): assemble quatre blocs en une seule image.
Indice
extraire_bloc construit taille lignes, chacune étant un morceau de ligne de l’image pris avec un slicing à partir de col_debut. assembler construit d’abord les lignes du haut, en mettant bout à bout chaque ligne de haut_gauche et la ligne de même indice de haut_droite, puis les lignes du bas.
Code à copier puis compléter
def extraire_bloc(image, ligne_debut, col_debut, taille):
bloc = []
for i in range(ligne_debut, ligne_debut + taille):
bloc.append(image[i][...:...])
return bloc
def assembler(haut_gauche, haut_droite, bas_gauche, bas_droite):
image = []
for i in range(len(haut_gauche)):
image.append(haut_gauche[i] + ...)
for i in range(len(bas_gauche)):
image.append(...)
return image
e) Écrire la fonction récursive rotation_dpr(image) utilisant l’approche DPR. Quel est le cas de base ?
Indice
Une image 1 × 1 est son propre quart de tour. Sinon, extraire les quatre blocs A, B, C et D, tourner chacun par un appel récursif, puis les assembler dans l’ordre C’, A’, D’, B'.
Code à copier puis compléter
def rotation_dpr(image):
n = len(image)
if n == 1:
return image
m = n // 2
a = rotation_dpr(extraire_bloc(image, 0, 0, m))
b = rotation_dpr(extraire_bloc(image, 0, m, m))
c = rotation_dpr(extraire_bloc(image, m, 0, m))
d = rotation_dpr(extraire_bloc(image, ..., ..., m))
return assembler(..., ..., ..., ...)
f) Vérifier que les deux fonctions donnent le même résultat sur l’image $4 \times 4$.
Indice
Comparer les deux résultats avec ==, ou les afficher l’un sous l’autre.
Correction publiée après la séance.
Exercice 8 : synthèse – comparer les algorithmes
a) Complétez le tableau suivant :
| Algorithme | Paradigme | Complexité (pire cas) | En place ? |
|---|---|---|---|
| Recherche séquentielle | … | … | Oui |
| Recherche dichotomique | … | … | Oui |
| Tri par sélection | Itératif | … | … |
| Tri par insertion | Itératif | … | … |
| Tri fusion | … | … | … |
Indice
Un algorithme « en place » travaille dans le tableau lui-même, sans en créer de nouveau : est-ce le cas du tri fusion, qui construit une liste à chaque fusion ? Pour les complexités, reprendre les exercices précédents et le cours.
b) Pour un tableau d’un million d’éléments, estimez le nombre d’opérations pour la recherche séquentielle et la recherche dichotomique. Quel est l’ordre de grandeur du facteur de gain ?
Indice
La recherche séquentielle fait de l’ordre de $n$ comparaisons, la recherche dichotomique de l’ordre de $\log_2 n$ ; $\log_2(10^6)$ vaut environ 20.
c) Un élève affirme : « le tri fusion est toujours le meilleur choix pour trier ». Donnez un argument en sa faveur et un contre-argument.
Indice
Penser à la complexité dans le pire cas, puis à la mémoire utilisée, et aux tableaux presque triés, que le tri par insertion traite très vite.
d) La recherche dichotomique nécessite un tableau trié. Si l’on dispose d’un tableau non trié de $n$ éléments et qu’on doit y faire $k$ recherches, quel est le coût total si l’on trie d’abord avec le tri fusion puis on fait $k$ recherches dichotomiques ? À partir de combien de recherches cette stratégie devient-elle plus avantageuse que $k$ recherches séquentielles ?
Indice
Comparer $n \log_2 n + k \log_2 n$ et $k \times n$ : pour quelles valeurs de $k$ le premier coût est-il le plus petit ?
Correction publiée après la séance.