TP — Séance 6 — Ensembles disjoints et tris

Écrire, tester et mesurer union-find, Kruskal et trois tris en Java

TP 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

Écrire les quatre versions d’union-find du cours (QuickFind, QuickUnion, union pondérée, compression de chemin), l’algorithme de Kruskal avec union-find, le tri par insertion, le tri fusion et le tri rapide (partition de Lomuto, pivot aléatoire) ; les faire passer par les tests JUnit fournis, les appliquer aux villages du delta du Saloum et à un classement d’étudiants, puis mesurer leurs coûts : accès au tableau, hauteur des arbres, comparaisons et temps. Durée : une séance de TP.

À rendre. Le dépôt Git du projet (les classes complétées, les tests au vert) et un compte rendu d’une à deux pages qui répond aux questions marquées Observer, Expliquer et Modifier, en recopiant les sorties obtenues.

Préparation

Le TP se fait dans l’environnement Docker du cours (Java 17, Gradle 8, JUnit 5). Sur la machine, décompresser le code de départ, TP_S06_code_depart.zip, dans ~/dsa : le dossier TP_S06_code_depart/ apparaît. Le conteneur se lance depuis ce dossier :

cd ~/dsa
docker run -it --rm -v "$(pwd):/workspace" elbachirtoure/dsa-java:v2.0

Sous Windows (Git Bash), la commande docker run est précédée de MSYS_NO_PATHCONV=1. Dans le conteneur :

cd /workspace
new-project tp-s06
cd tp-s06
cp -r ../TP_S06_code_depart/. .
rm src/test/java/MainTest.java

Le code de départ contient vingt-quatre fichiers, vingt-trois dans src/main/java/ et DisjointsTrisTest.java dans src/test/java/ : la copie les range dans le projet, en remplaçant le Main.java créé par new-project, et rm supprime le MainTest.java créé par new-project. Le dépôt Git du projet se crée dans tp-s06 : git init -b main et l’identité locale, comme à l’étape 7 du TP-1.

Fichier Rôle
UF.java interface union-find (find, union, count, connected, acces), fournie
QuickFindUF.java find et union à écrire à l’étape 1
QuickUnionUF.java find et union à écrire à l’étape 2 ; profondeur, hauteur, etat fournis
WeightedQuickUnionUF.java, PathCompressionUF.java union et find à écrire à l’étape 3
KruskalUF.java construire à écrire à l’étape 4
Tri.java compteurs comparaisons et acces, plusPetit, echanger, estTrie, fournis
TriInsertion.java, TriFusion.java, TriRapide.java méthodes à écrire aux étapes 5, 6 et 7
TriTas.java, BinaryMinHeap.java tri par tas et tas binaire de la Séance 4, fournis
Kruskal.java, Graphe.java, ParcoursLargeur.java Kruskal de la Séance 5 (test de cycle par parcours), fourni
GraphePondere.java, Arete.java, Generateur.java graphes pondérés et graphes au hasard de la Séance 5, fournis
DeltaSaloum.java 12 villages du delta du Saloum, 12 raccordements et 17 liaisons (millions de FCFA), fourni
Etudiant.java, Donnees.java, Paires.java étudiant et note, tableaux et paires au hasard, fournis
Main.java programmes d’observation, fourni
DisjointsTrisTest.java dix-huit tests JUnit, fournis

Les méthodes à écrire contiennent une consigne en commentaire et lèvent UnsupportedOperationException ; tout le reste est fourni. Les deux commandes du TP sont gradle --no-daemon test et gradle --no-daemon run --args="mode", où mode vaut villages, kruskal, classement ou mesures. Un accès est une lecture ou une écriture de id[] ou de parent[] ; les accès de taille[] ne sont pas comptés.

Observer. Lancer les tests avant d’écrire la moindre ligne : combien échouent, et avec quelle exception ?

Étape 1 : QuickFind

Écrire find et union de QuickFindUF en suivant les consignes.

  1. Observer. Les tests quickFindUnion et quickFindAcces doivent passer.
  2. Expliquer. Retrouver les 19 accès attendus par quickFindAcces : détailler les deux unions.
  3. Expliquer. Pourquoi faut-il lire pid avant la boucle, au lieu de comparer id[i] à id[p] ? Donner un exemple où la seconde version se trompe.

Étape 2 : QuickUnion

Écrire find et union de QuickUnionUF : find remonte de parent en parent en comptant \(2d+1\) accès pour une profondeur \(d\).

  1. Observer. Les tests quickUnionFind et quickUnionPireCas doivent passer. Dessiner la forêt du test quickUnionFind.
  2. Expliquer. Le test quickUnionPireCas attend \(9\,999\) accès pour 99 appels union(0, i). Retrouver ce nombre par un calcul.

Étape 3 : union pondérée et compression de chemin

Écrire la méthode union de la classe WeightedQuickUnionUF, puis la méthode find de la classe PathCompressionUF, qui hérite de l’union pondérée.

  1. Observer. Les quatre tests dont le nom commence par ponderee ou par compression doivent passer. Lancer le mode villages et recopier sa sortie.
  2. Expliquer. Les villages forment-ils un seul réseau après les douze raccordements ? Quels raccordements étaient inutiles, et pourquoi ?
  3. Expliquer. Dessiner les forêts de QuickUnion et de l’union pondérée à partir des tableaux écrits. Pourquoi la compression coûte-t-elle ici plus d’accès que l’union pondérée seule ?
  4. Modifier. Inverser provisoirement la règle de l’union pondérée (taille[i] > taille[j] au lieu de taille[i] < taille[j]). Quels tests échouent ? Expliquer la hauteur obtenue sur la chaîne union(0, i). Revenir au code correct.
  5. Modifier. Supprimer provisoirement le second passage de find dans PathCompressionUF. Quel test échoue ? Comment évolue la colonne compression du mode mesures (étape 8) ? Revenir au code correct.

Étape 4 : Kruskal avec union-find

Écrire construire de KruskalUF : c’est le code de la Séance 5, où le test par parcours devient uf.connected et l’ajout à la forêt uf.union.

  1. Observer. Les tests kruskalUFPoids et kruskalUFCommeParcours doivent passer. Lancer le mode kruskal, recopier sa sortie et dessiner le réseau obtenu.
  2. Expliquer. Quelles liaisons sont rejetées, et quel cycle chacune aurait-elle fermé ? Pourquoi les trois liaisons les plus chères ne sont-elles jamais examinées ?
  3. Expliquer. Comparer les colonnes visites et acces quand \(V\) double. Estimer leur rapport pour \(V=64\,000\).
  4. Modifier. Remplacer provisoirement PathCompressionUF par QuickFindUF dans KruskalUF. Les tests passent-ils ? Que deviennent les accès du mode kruskal ? Revenir au code correct.

Étape 5 : le tri par insertion

Écrire trier de TriInsertion, avec plusPetit et echanger de la classe Tri.

  1. Observer. Les tests insertionTrieEtCompte et insertionStable doivent passer.
  2. Expliquer. Retrouver à la main les 10 comparaisons attendues sur [7, 3, 9, 1, 5, 8] : combien sont suivies d’un échange ?
  3. Modifier. Remplacer provisoirement la condition plusPetit(a, j, j - 1) par !plusPetit(a, j - 1, j) (inférieur ou égal). Quel test échoue ? Le tableau est-il encore trié ? Revenir au code correct.

Étape 6 : le tri fusion

Écrire la méthode récursive trier(a, aux, lo, hi) et fusionner de TriFusion.

  1. Observer. Les tests fusionTrieEtCompte, fusionStable et fusionBorne doivent passer.
  2. Expliquer. Retrouver les 11 comparaisons de fusionTrieEtCompte : les cinq fusions et leurs comparaisons.
  3. Modifier. Prendre provisoirement la tête de droite à égalité (!plusPetit(aux, i, j) au lieu de plusPetit(aux, j, i)). Quel test échoue, et pourquoi ? Revenir au code correct.

Étape 7 : le tri rapide

Écrire partition (Lomuto, pivot tiré par hasard) et la méthode récursive trier(a, lo, hi) de TriRapide.

  1. Observer. Les tests partitionLomuto, rapideTrie et rapideClesEgales doivent passer, et les dix-huit tests au total. Lancer le mode classement et recopier sa sortie.
  2. Expliquer. Dérouler à la main la partition de partitionLomuto (le tirage vaut 0).
  3. Expliquer. Dans le mode classement, quels tris gardent l’ordre de dépôt entre deux étudiants de même note ? Relever, pour le tri rapide, deux paires inversées.
  4. Modifier. Remplacer provisoirement le tirage par int r = hi;. Quel test échoue ? Trier un tableau croissant de \(2\,000\), puis \(4\,000\) éléments, et relever les comparaisons. Revenir au code correct.

Étape 8 : les coûts mesurés

Le mode mesures tire des paires au hasard (graine 2027) jusqu’à la connexité, pour \(n\) de \(2\,000\) à \(32\,000\), et écrit les accès par paire et les hauteurs finales des trois forêts ; il trie ensuite des entiers au hasard et écrit les comparaisons, leur rapport à \(n\log_2 n\), les accès et le temps en millisecondes, puis trie un tableau croissant de \(128\,000\) éléments par le tri rapide et le tri fusion.

  1. Observer. Lancer le mode mesures et recopier les deux tableaux.
  2. Expliquer. Quelles colonnes restent constantes quand \(n\) double, lesquelles doublent ? Comparer les hauteurs à \(\log_2 n\).
  3. Expliquer. Pour les tris, quel rapport reste proche d’une constante ? Comparer aux valeurs du cours (\(\approx0{,}9\) pour la fusion, \(\approx1{,}2\) pour le tri rapide) et à la borne \(\log_2 n!\approx n\log_2 n-1{,}44\,n\).
  4. Expliquer. Le tri rapide fait plus de comparaisons que le tri fusion, mais il est le plus rapide en temps. Avancer deux raisons à partir des colonnes acces et du code. Pourquoi le tri fusion d’un tableau croissant fait-il deux fois moins de comparaisons ?
  5. Expliquer. Les temps varient d’une exécution à l’autre et d’une machine à l’autre : relancer deux fois le mode et indiquer quelles colonnes changent.

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet