TD — Séance 6 — Ensembles disjoints et tris

Union-find, tri par insertion, tri fusion, tri rapide et borne inférieure

TD de la séance 6 de Structures de données et algorithmes avancés : union-find, tri par insertion, tri fusion, tri rapide et borne inférieure.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Appliquer à la main, sur des données nouvelles, les mécanismes du cours : QuickFind, QuickUnion, union pondérée et compression de chemin, Kruskal avec union-find, tris par insertion, fusion et rapide, borne inférieure des tris par comparaison. Chaque réponse se donne sous la forme demandée (tableau, valeur, trace) et se justifie en une ou deux phrases.

Conventions. Les classes sont celles du cours. union(p, q) place la racine de \(p\) sous celle de \(q\) en QuickUnion ; en union pondérée, la racine du plus petit arbre passe sous celle du plus grand, et à égalité la racine de \(q\) passe sous celle de \(p\). Un accès est une lecture ou une écriture de id[] ou de parent[] : find coûte 1 accès en QuickFind, \(2d+1\) en QuickUnion pour un élément de profondeur \(d\), \(4d+1\) avec compression ; union ajoute, en QuickFind, la lecture des \(n\) cases et l’écriture des cases modifiées, et ailleurs une écriture si les racines diffèrent. Les tris comptent les appels de plusPetit, qui compare strictement. Le tri fusion coupe en \(\texttt{mid}=\texttt{lo}+(\texttt{hi}-\texttt{lo})/2\) ; le tri rapide utilise la partition de Lomuto du cours, pivot tiré puis placé en a[hi].

Exercice 1 : QuickFind et QuickUnion

Dix éléments, numérotés de 0 à 9, reçoivent dans cet ordre les unions union(4, 9), union(2, 7), union(9, 7), union(0, 5), union(5, 7), union(3, 8), union(1, 3), union(8, 7).

  1. Avec QuickFind, compléter le tableau id[] après chaque union et le nombre d’accès de chaque union.
  2. Avec QuickUnion, compléter parent[] après chaque union et le nombre d’accès de chaque union. Dessiner la forêt finale.
  3. Combien reste-t-il de composantes ? Quelle est la hauteur de la forêt de QuickUnion ? Comparer les accès totaux des deux versions.
  4. Donner une suite de 9 unions sur ces dix éléments qui donne à QuickUnion une hauteur de 9.
union QuickFind : id[] acc. QuickUnion : parent[] acc.
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
(4, 9)
(2, 7)
(9, 7)
(0, 5)
(5, 7)
(3, 8)
(1, 3)
(8, 7)

Exercice 2 : union pondérée et compression de chemin

Douze éléments, numérotés de 0 à 11, reçoivent dans cet ordre les unions union(1, 0), union(3, 2), union(5, 4), union(7, 6), union(0, 2), union(4, 6), union(2, 6), union(9, 8), union(11, 10), union(8, 10), union(10, 6).

  1. Avec l’union pondérée par la taille, compléter parent[] après chaque union, et la taille de la racine qui reçoit l’autre.
  2. Dessiner la forêt finale. Donner la profondeur de chaque élément et la hauteur ; la comparer à \(\log_2 12\).
  3. On refait la même suite avec PathCompressionUF. Quelles unions modifient parent[] au-delà du lien entre les racines ? Donner parent[] final et la hauteur.
  4. Dans la forêt de (c), dérouler find sur l’élément le plus profond de plus petit numéro : chemin, accès, parent[] après.
  5. Expliquer pourquoi, dans la forêt de (a), aucun élément ne peut avoir une profondeur de 4.
union 0 1 2 3 4 5 6 7 8 9 10 11 taille de la racine
(1, 0)
(3, 2)
(5, 4)
(7, 6)
(0, 2)
(4, 6)
(2, 6)
(9, 8)
(11, 10)
(8, 10)
(10, 6)

Exercice 3 : Kruskal avec union-find

Sept villages du Saloum sont à relier par un réseau d’adduction d’eau : 0 Nioro du Rip, 1 Keur Madiabel, 2 Médina Sabakh, 3 Wack Ngouna, 4 Porokhane, 5 Paoskoto, 6 Kaymor. Les liaisons possibles et leur coût, en millions de FCFA, sont, dans l’ordre de saisie : 0–1 11, 0–3 9, 1–3 10, 0–4 7, 4–5 14, 1–5 16, 2–3 13, 2–6 8, 3–6 12, 5–6 18, 1–2 15.

  1. Dérouler KruskalUF (union pondérée et compression) : pour chaque liaison sortie du tas, la décision et sa raison, puis parent[] et taille[] de la racine.
  2. Donner le réseau obtenu et son coût. Quelles liaisons ne sont jamais examinées, et pourquoi ?
  3. Combien d’accès à parent[] le test d’une liaison coûte-t-il au plus dans cet exemple ? Le comparer au nombre de sommets atteints par le test de la Séance 5 (parcours en largeur de la forêt).
liaison décision 0 1 2 3 4 5 6 taille de la racine

Exercice 4 : tri par insertion et stabilité

Six étudiants ont déposé leur copie dans cet ordre, avec leur note : Astou 13, Modou 10, Bineta 13, Saliou 8, Dieynaba 10, Alioune 15. Le classement se fait par note décroissante, par le tri par insertion du cours (compareTo de la classe Etudiant : une note plus haute est « plus petite »).

  1. Compléter le tableau : la liste après chaque tour, les comparaisons et les échanges.
  2. Compter les inversions de la liste de départ et les comparer au nombre d’échanges.
  3. Le classement garde-t-il l’ordre de dépôt entre Astou et Bineta, entre Modou et Dieynaba ? Justifier par le code.
  4. Donner le nombre de comparaisons au mieux et au pire pour 6 éléments, et une liste de départ pour chaque cas.
tour liste après le tour comparaisons échanges
\(i=1\)
\(i=2\)
\(i=3\)
\(i=4\)
\(i=5\)
total

Exercice 5 : tri fusion

Huit prix, en FCFA : a = [520, 180, 760, 340, 180, 910, 260, 430].

  1. Donner, dans l’ordre d’exécution, chaque appel de fusionner(lo, mid, hi), le sous-tableau obtenu et ses comparaisons.
  2. Le total des comparaisons. Quelle est la position finale de chacun des deux 180 ?
  3. Donner la récurrence du nombre de comparaisons au pire, puis sa valeur pour \(n=16\), et la comparer à \(\lceil\log_2 16!\rceil\).
  4. Sur un tableau déjà trié de \(n=2^k\) éléments, combien de comparaisons fait une fusion de deux moitiés de \(m\) éléments ? En déduire le total.
appel sous-tableau après la fusion comparaisons
total

Exercice 6 : tri rapide

Sept prix, en centaines de FCFA : a = [48, 72, 15, 63, 29, 81, 37], triés par new TriRapide<Integer>(13). Les tirages successifs donnent \(r=6\), puis \(0\), \(4\) et \(3\).

  1. Dérouler la première partition : pour chaque \(j\), la comparaison, \(i\) et le tableau.
  2. Pour chaque appel de partition : le sous-tableau, le pivot, les comparaisons, le tableau après et la valeur rendue.
  3. Le total des comparaisons et la profondeur des appels.
  4. Un tri rapide qui prend toujours a[hi] comme pivot, sans tirage, trie [10, 20, 30, 40, 50, 60, 70] : combien de comparaisons ? Et le tri du cours sur sept prix égaux à 500 ? Expliquer.
étape test \(i\) tableau
pivot —
\(j=0\)
\(j=1\)
\(j=2\)
\(j=3\)
\(j=4\)
\(j=5\)
fin —

Exercice 7 : arbres de décision et borne inférieure

  1. Dessiner l’arbre de décision du tri fusion du cours pour trois éléments \(a\), \(b\), \(c\) (mid \(=1\) : a[0..1] puis a[2]). Donner sa hauteur, le nombre de comparaisons au mieux et la moyenne sur les six ordres.
  2. Calculer \(\lceil\log_2 n!\rceil\) pour \(n=6\), 7, 10 et 12. Le tri fusion atteint-il cette borne pour \(n=6\) et \(n=7\) ? Calculer son pire cas pour ces deux tailles.
  3. Un arbre binaire a \(n!\) feuilles. Montrer que la profondeur moyenne de ses feuilles est au moins \(\log_2 n!\), et en déduire qu’un tri par comparaison fait \(\Omega(n\log n)\) comparaisons en moyenne sur les \(n!\) ordres.
  4. Un tableau est dit « presque trié » si chaque élément est à au plus \(k\) cases de sa place finale. Majorer le nombre d’inversions, puis le coût du tri par insertion, en fonction de \(n\) et de \(k\). Cela contredit-il la borne ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet