Pale machine du mardi 29 septembre


Votre opinion sur le cours de ce matin : 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 : Range Minimum Query

Le but de cet exercice est de construire une structure de données MinTree, qui représente un tableau d'entiers dont les indices vont de 0 (inclus) à n (exclus) et munie d'une fonction :

On cherche une solution où ce calcul a un coût O(log n). L'idée est de représenter le tableau comme un arbre binaire : les feuilles contiennent les éléments du tableau et chaque nœud contient le minimum de toutes les feuilles qui sont en-dessous. Par ailleurs :

La figure ci-dessous illustre une représentation possible, sous forme d'arbre, d'un tableau de 6 cases.

1.1. Champs et constructeurs

Écrivez dans un fichier MinTree.java une classe publique MinTree représentant un nœud d'un arbre de Min, possédant les 4 champs suivants :

Ajoutez à la classe MinTree :

Vous pouvez tester votre code à l'aide du fichier Test1.java qui construit l'arbre MinTree(3) et l'arbre de la figure ci-dessus. Le résultat doit être le suivant :

Construction de MinTree(3) : [3, 1]
Construction de l'arbre de la figure : [1, 6, [2, 3, [4, 1], [2, 2, [2, 1], [5, 1]]], [1, 3, [3, 1], [1, 2, [6, 1], [1, 1]]]]

Déposez le fichier MinTree.java ici :

1.2. Représentation d'un tableau

On numérote les feuilles d'un arbre de gauche à droite et en commençant la numérotation à 0 : la feuille d'indice 0 d'un arbre t est sa feuille la plus à gauche, sa feuille la plus à droite est celle d'indice n-1 si t a n feuilles.

Écrivez une méthode static MinTree fromArray(int[] tab, int i, int j) qui construit un arbre équilibré qui a j-i feuilles, représentant la plage de cases du tableau tab entre les indices i (inclus) et j (exclus). On supposera que 0 ≤ i < j ≤ nn est la taille du tableau tab. Concrètement, la case du tableau tab d'indice i+k (pour 0 ≤ k < j-i) sera représentée par la feuille de l'arbre d'indice k.
On pourra procéder récursivement.

Vous pouvez tester votre code à l'aide du fichier Test2.java qui appelle fromArray([4, 2, 5, 3, 6, 1], i, j) pour différents indices i et j. Si vous avez choisi de mettre plus de feuilles dans le fils gauche que dans le fils droit lorsque j-i est impair, le résultat doit être le suivant :

Tableau tab : [4, 2, 5, 3, 6, 1]
fromArray(tab, 0, 3) : [2, 3, [2, 2, [4, 1], [2, 1]], [5, 1]]
fromArray(tab, 2, 4) : [3, 2, [5, 1], [3, 1]]
fromArray(tab, 0, 6) : [1, 6, [2, 3, [2, 2, [4, 1], [2, 1]], [5, 1]], [1, 3, [3, 2, [3, 1], [6, 1]], [1, 1]]]

Si vous avez choisi au contraire de mettre plus de feuilles dans le fils droit que dans le fils gauche lorsque j-i est impair, le résultat doit être le suivant :

Tableau tab : [4, 2, 5, 3, 6, 1]
fromArray(tab, 0, 3) : [2, 3, [4, 1], [2, 2, [2, 1], [5, 1]]]
fromArray(tab, 2, 4) : [3, 2, [5, 1], [3, 1]]
fromArray(tab, 0, 6) : [1, 6, [2, 3, [4, 1], [2, 2, [2, 1], [5, 1]]], [1, 3, [3, 1], [1, 2, [6, 1], [1, 1]]]]

Déposez le fichier MinTree.java ici :

1.3. Minimum d'une plage de feuilles

Écrivez dans la classe MinTree une méthode dynamique int min(int i, int j) qui renvoie le minimum des valeurs étiquetant les feuilles de this d'indice compris entre i (inclus) et j (exclus). On suppose que 0 ≤ i < j ≤ nn est le nombre de feuilles de this. Cette méthode doit s'exécuter en temps logarithmique en la taille de l'arbre this.

Indication : on envisagera plusieurs sous-cas récursifs suivant les positions de i et j dans l'arbre this.

Vous pouvez tester votre code à l'aide du fichier Test3.java qui calcule le minimum du tableau [4, 2, 5, 3, 6, 1] entre différentes plages d'indices. Le résultat doit être le suivant :

Le minimum du tableau [4, 2, 5, 3, 6, 1] entre les indices 0 (inclus) et 6 (exclus) est 1
Le minimum du tableau [4, 2, 5, 3, 6, 1] entre les indices 2 (inclus) et 5 (exclus) est 3
Le minimum du tableau [4, 2, 5, 3, 6, 1] entre les indices 0 (inclus) et 4 (exclus) est 2
Le minimum du tableau [4, 2, 5, 3, 6, 1] entre les indices 3 (inclus) et 6 (exclus) est 1

Déposez le fichier MinTree.java ici :

Exercice 2 : Tables de Hachage

Le but de cet exercice est de supprimer les doublons dans une longue liste de personnes. Les personnes sont représentées par une classe Person qui contient leurs noms et prénoms. Pour supprimer les doublons, on comparera deux méthodes : une méthode naïve qui cherche pour chaque couple (prénom, nom) 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. C'est à vous de faire l'ensemble du travail et il est conseillé de faire des tests au fur et à mesure.

2.1. Gérer les individus

Écrivez une classe Person avec deux champs String firstName et String lastName, un constructeur public Person(String firstName, String lastName) et une méthode public String toString() qui renvoie la chaîne de caractères formée par le prénom et le nom séparés par un espace.

Écrivez une méthode public static String randomString(int length, char[] alphabet) qui renvoie un mot de longueur length dont les lettres sont tirées aléatoirement dans l'alphabet (qu'on suppose non vide). En utilisant cette méthode, ajoutez un constructeur public Person(int lengthFirstName, int lengthLastName, char[] alphabet) qui crée une personne dont le prénom et le nom sont des mots de longueur lengthFirstName et lengthLastName dont les lettres sont tirées aléatoirement dans l'alphabet (qu'on suppose non vide).

Déposez le fichier Person.java ici :

2.2. Retirer les doublons

2.2.1. Méthode naïve

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

Déposez le fichier KillDuplicates.java ici :

2.2.2. Utilisation d'une table de hachage

Écrivez une méthode public static LinkedList<Person> killDuplicates(LinkedList<Person> listWithDuplicates) qui prend en argument une liste listWithDuplicates contenant éventuellement des doublons et renvoie une liste contenant une et une seule fois chaque personne de listWithDuplicates. Pour cette nouvelle méthode, utilisez un HashSet<Person> et complétez en conséquence la classe Person avec les méthodes public int hashCode() et public boolean equals(Object o) nécessaires à l'utilisation de HashSet. On pourra se servir de la méthode hashCode() des objets de la classe String.

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

2.2.3. Tests de performance

Dans la méthode public static void main(String[] args) de la classe KillDuplicates, créez une liste listWithDuplicates de 100000 personnes dont le prénom et le nom ont chacun 5 lettres tirées aléatoirement dans l'alphabet {a,b}. Affichez ensuite la taille de la liste sans doublons en utilisant les méthodes killDuplicatesNaive et killDuplicates. Comparez les temps de calcul en utilisant System.currentTimeMillis(). Vous devez obtenir quelque chose comme ça (les nombres peuvent bien sûr varier légèrement) :

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.

Déposez le fichier KillDuplicates.java ici :


solutions