Pour chaque question, une seule réponse est correcte.
1. Le paradigme « diviser pour régner » repose sur trois étapes. Lesquelles ?
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 ?
Correction publiée après la séance.
3. Quelle est la complexité du tri fusion dans le pire cas ?
Correction publiée après la séance.
4. Quel est l’inconvénient principal du tri fusion par rapport au tri par insertion ?
Correction publiée après la séance.
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 ?
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.
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 ?
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$.
$\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.
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 ?
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.
É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 ?
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.
À 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 ?
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.
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 ...).
fusion (exercice guidé) (suite)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.
fusion (exercice guidé) (suite)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) ?
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 ?
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.
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 ?
Un tableau vide, ou d’un seul élément, est-il déjà trié ?
b) Écrivez la fonction tri_fusion(tab) qui :
tab si c’est le cas de base ;tab en deux moitiés, trie récursivement chaque moitié, puis les fusionne.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.
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).
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.
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.
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.
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.
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 ?
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.
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 … ?
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).
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.
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.
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 de taille × taille pixels ;assembler(haut_gauche, haut_droite, bas_gauche, bas_droite) : assemble quatre blocs en une seule image.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.
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 ?
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'.
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$.
Comparer les deux résultats avec ==, ou les afficher l’un sous l’autre.
Correction publiée après la séance.
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 | … | … | … |
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 ?
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.
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 ?
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.