Pale machine du mardi 27 septembre


Votre opinion sur le cours de lundi : Votre opinion sur le TD de la semaine dernière :

 Login :  Mot de passe :

Les deux exercices sont indépendants. Attention à déposer les fichiers .java (et pas les .class).

Exercice 1 : ensembles de rationnels

Le but de cet exercice est de supprimer les doublons dans une longue liste de nombres. Les nombres qui nous intéressent sont rationnels et sont représentés par une classe Rational avec deux champs entiers num pour le numérateur et den pour le dénominateur. On considérera bien sûr que deux rationnels num1/den1 et num2/den2 sont les mêmes lorsque num1 * den2 = den1 * num2. Pour supprimer les doublons de notre longue liste de rationnels, on comparera deux méthodes : une méthode naïve qui cherche pour chaque rationnel s'il est déjà dans la liste sans doublons et une méthode utilisant une table de hachage (implémentée par HashSet).

Nous ne fournissons ni le squelette, ni les tests pour cet exercice.

1.1. Rationnels

Écrivez une classe Rational avec deux champs int num et int den et un constructeur Rational(int num, int den). Le constructeur ne sera jamais appelé avec den = 0 ; on ne vous demande donc pas d'y faire attention.

Ajoutez une méthode public String toString() qui renvoie la chaîne de caractères formée par le numérateur et le dénominateur séparés par un /.

Ajoutez une méthode static Rational randomRational(int min, int max) qui renvoie un rationnel dont le numérateur est un entier aléatoire dans l'intervalle [min, max[ et dont le dénominateur est un entier aléatoire dans l'intervalle [1,max].

Ajoutez une méthode static boolean areEqual(Rational r, Rational s) qui teste si les rationnels r et s sont égaux.

Toujours dans la classe Rational, ajoutez une méthode public static void main(String[] args) qui teste toutes vos méthodes.

Déposez le fichier Rational.java ici :

1.2. Retirer les doublons

Créez une nouvelle classe KillDuplicates, et ajoutez en haut du fichier import java.util.*; pour pouvoir utiliser les classes LinkedList et HashSet.

1.2.1. Méthode naïve

Dans la classe KillDuplicates, écrivez une méthode static LinkedList<Rational> killDuplicatesNaive(LinkedList<Rational> listWithDuplicates) qui prend en argument une liste listWithDuplicates contenant éventuellement des doublons et renvoie une liste contenant une et une seule fois chaque rationnel de listWithDuplicates. Pour cette méthode, utilisez l'approche naïve : créez une liste LinkedList<Rational> listWithoutDuplicates initialement vide, puis ajoutez itérativement chaque élément de listWithDuplicates dans la liste listWithoutDuplicates s'il ne s'y trouve pas déjà.

Déposez le fichier KillDuplicates.java ici :

1.2.2. Utilisation d'une table de hachage

Complétez en conséquence la classe Rational avec les méthodes public int hashCode() et public boolean equals(Object o) nécessaires à l'utilisation de HashSet. On rappelle que la méthode hashCode() doit renvoyer le même code sur deux rationnels égaux (pour que le code soit juste), et qu'elle doit autant que possible distinguer les rationnels différents (pour que le code soit efficace). Pour cela, on conseille d'ajouter à la classe Rational la méthode

	static int gcd(int a, int b) {
		if(a < 0) return gcd(-a, b);
		if(b < 0) return gcd(a, -b);
		if(b == 0) return a;
		return gcd(b, a%b);
	}

qui renvoie le plus grand diviseur commun de a et b, et de l'utiliser pour calculer un hashCode correct et efficace.

Dans la classe KillDuplicates, écrivez une méthode static LinkedList<Rational> killDuplicatesHashSet(LinkedList<Rational> listWithDuplicates) qui prend en argument une liste listWithDuplicates contenant éventuellement des doublons et renvoie une liste contenant une et une seule fois chaque élément de listWithDuplicates. Pour cette nouvelle méthode, utilisez un HashSet<Rational>.

Déposez les fichiers Rational.java et KillDuplicates.java ici :

1.2.3. Tests de performance

Dans la classe KillDuplicates, écrivez une méthode static void testKillDuplicatesMethods(LinkedList<Rational> listWithDuplicates) qui compare vos méthodes killDuplicatesNaive et killDuplicatesHashSet lorsqu'elles sont lancées sur une même liste listWithDuplicates. La méthode devra afficher la taille de la liste sans doublons obtenue ainsi que le temps de calcul de chacune des méthodes killDuplicatesNaive et killDuplicatesHashSet. Pour le temps de calcul, on utilisera long System.currentTimeMillis() qui renvoie le temps courant (en millisecondes). Ainsi, vous devez obtenir quelque chose comme ça (bien sûr, les nombres dépendront de la liste fournie à la méthode) :

suppression des doublons méthode naïve : 1024 elements, calcul en 1732 millisecondes.
suppression des doublons avec table de hachage : 1024 elements, calcul en 27 millisecondes.

Dans la classe KillDuplicates, écrivez les deux méthodes de test suivantes :

Dans la classe KillDuplicates, écrivez une méthode public static void main(String[] args) qui exécute testRepeatedList(100000) et testRandomList(100000, -20, 20). Vous devez obtenir quelque chose comme ça :

test longue liste répétée :
suppression des doublons methode naive : 1 elements, calcul en 32 millisecondes.
suppression des doublons avec table de hachage : 1 elements, calcul en 21 millisecondes.

test longue liste aléatoire :
suppression des doublons methode naive : 495 elements, calcul en 350 millisecondes.
suppression des doublons avec table de hachage : 495 elements, calcul en 20 millisecondes.

Déposez le fichier KillDuplicates.java ici :

Exercice 2 : arbres d'intervalles

Le but de cet exercice est de construire une structure de données IntervalTree qui représente efficacement des ensembles d'entiers assez denses, c'est-à-dire contenant de nombreux entiers consécutifs. L'idée est d'utiliser une sorte d'arbre binaire de recherche, mais dans lequel les nœuds correspondent à des intervalles d'entiers consécutifs. Plus précisément, un « arbre d'intervalles » est un arbre binaire dont chaque nœud correspond à un intervalle [lo, hi] et tel que :

Notez que les deux dernières conditions assurent en particulier que les intervalles d'un tel arbre sont maximaux, dans le sens qu'il est impossible de grouper deux intervalles pour obtenir un nouvel intervalle.

Un arbre d'intervalles représente l'ensemble d'entiers obtenu par union des intervalles dans ses nœuds. Par exemple, les arbres d'intervalles suivants

représentent tous l'ensemble {2,3,4,5,8,15,16,18,20,21,22,23,24,25,30,31,32,33,34,35,36,37,38,39,40,42,43,45,46,48,49,50}. Cette représentation est évidemment efficace pour les ensembles d'entiers denses puisqu'un arbre d'intervalles représentant un ensemble S a autant de nœuds qu'il y a d'intervalles d'entiers consécutifs maximaux dans S.

2.0. La classe IntervalTree

Téléchargez le fichier IntervalTree.java. Ce fichier contient le squelette de la classe IntervalTree représentant un nœud d'un arbre d'intervalles, et possédant les 4 champs suivants :

L'arbre vide est représenté par null.

Le squelette contient déjà un constructeur IntervalTree(int lo, int hi, IntervalTree left, IntervalTree right).

2.1. Représentation

Dans la classe IntervalTree, complétez la méthode static String stringRep(IntervalTree it) qui renvoie la chaîne "." pour l'arbre vide et une chaîne de caractères de la forme "(lo, hi, left, right)" sinon. Par exemple, votre méthode doit renvoyer la chaîne "(30, 40, (8, 8, (2, 5, ., .), (18, 18, (15, 16, ., .), (20, 25, ., .))), (45, 46, (42, 43, ., .), (48, 50, ., .)))" pour l'arbre

Utilisez la classe Test21.java fournie pour valider votre code. L'exécution de cette dernière doit afficher :

Tests de stringRep... [OK]

Déposez le fichier IntervalTree.java ici :

2.2. Cardinal, Minimum, Maximum

Dans la classe IntervalTree, complétez les méthodes suivantes :

Utilisez la classe Test22.java fournie pour valider votre code. L'exécution de cette dernière doit afficher :

Tests de cardinality... [OK]
Tests de minimum... [OK]
Tests de maximum... [OK]

Déposez le fichier IntervalTree.java ici :

2.3. Vérification

Dans cette question, on implémente deux méthodes pour vérifier qu'un objet de type IntervalTree donné est bien un arbre d'intervalles. On rappelle qu'on doit donc vérifier que :

Commencez par compléter dans la classe IntervalTree la méthode naive static boolean isIntervalTreeNaive(IntervalTree it) qui teste si it est un arbre d'intervalles en utilisant les méthodes minimum et maximum de la question précédente.

Pour obtenir un test plus efficace, complétez dans la classe IntervalTree la méthode static boolean isIntervalTreeBounded(IntervalTree it, int min, int max) qui vérifie que it est un arbre d'intervalles dont tous les entiers x vérifient min ≤ x ≤ max. Complétez ensuite la méthode static boolean isIntervalTree(IntervalTree it) qui teste efficacement si it est un arbre d'intervalles (on se servira des constantes Integer.MIN_VALUE et Integer.MAX_VALUE qui sont respectivement la plus petite et la plus grande valeur du type int).

Utilisez la classe Test23.java fournie pour valider votre code. L'exécution de cette dernière doit afficher :

Tests de isIntervalTreeNaive... [OK]
Tests de isIntervalTreeBounded... [OK]
Tests de isIntervalTree... [OK]

Déposez le fichier IntervalTree.java ici :

2.4. Recherche

Dans la classe IntervalTree, complétez la méthode static boolean contains(IntervalTree it, int x) qui teste si l'entier x est contenu dans l'arbre d'intervalles it. On veillera à utiliser les propriétés des arbres d'intervalles et donc à éviter de visiter inutilement les deux sous-arbres de it si on n'a pas trouvé x à la racine de it.

Utilisez la classe Test24.java fournie pour valider votre code. L'exécution de cette dernière doit afficher :

Tests de contains... [OK]

Déposez le fichier IntervalTree.java ici :

2.5. Trouver et supprimer l'intervalle minimum (ou maximum)

Dans la classe IntervalTree, complétez la méthode static IntervalTree getMinimalInterval(IntervalTree it) qui renvoie un nouvel arbre d'intervalles contenant uniquement l'intervalle minimal de l'arbre it (celui qui contient le plus petit entier de it). De la même manière, complétez la méthode static IntervalTree getMaximalInterval(IntervalTree it) qui renvoie un nouvel arbre d'intervalles contenant uniquement l'intervalle maximal de l'arbre it (celui qui contient le plus grand entier de it).

Dans la classe IntervalTree, complétez la méthode static IntervalTree deleteMinimalInterval(IntervalTree it) qui supprime de l'arbre d'intervalles it son intervalle minimal. On renvoie l'arbre après suppression, pour traiter correctement le cas où l'intervalle supprimé se trouvait à la racine (c'est analogue à la suppression dans les arbres binaires de recherche telle qu'elle a été vue en cours). Le résultat devra bien entendu vérifier les propriétés des arbres d'intervalles. De la même manière, complétez la méthode static IntervalTree deleteMaximalInterval(IntervalTree it) qui supprime de l'arbre d'intervalles it son intervalle maximal et renvoie l'arbre après suppression.

Utilisez la classe Test25.java fournie pour valider votre code. L'exécution de cette dernière doit afficher :

Tests de getMinimalInterval... [OK]
Tests de getMaximalInterval... [OK]
Tests de deleteMinimalInterval... [OK]
Tests de deleteMaximalInterval... [OK]

Déposez le fichier IntervalTree.java ici :

2.6. Insertion

Dans la classe IntervalTree, complétez la méthode static IntervalTree insert(IntervalTree it, int x) qui insère l'entier x dans l'arbre d'intervalles it. On renvoie l'arbre après insertion, pour traiter correctement le cas d'une insertion dans un arbre vide (c'est analogue à l'insertion dans les arbres binaires de recherche telle qu'elle a été vue en cours). Le résultat devra bien entendu vérifier les propriétés des arbres d'intervalles. Lorsque it n'est pas vide, c'est-à-dire it = (lo, hi, left, right), on distingue les cas suivants :

Dans tous ces cas, pensez à bien renvoyer it après avoir inséré x.

En particulier, le cas compliqué de l'insertion est illustré sur l'exemple suivant (avec x qui vaut 41) :

Utilisez la classe Test26.java fournie pour valider votre code. L'exécution de cette dernière doit afficher :

Tests de insert... [OK]

Déposez le fichier IntervalTree.java ici :


Solution