Pale machine du mercerdi 30 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 : Arbres de Fenwick

Le but de cet exercice est de construire une structure de données, appelée arbre de Fenwick, qui représente un tableau d'entiers dont les indices vont de 0 (inclus) à n (exclus) et munie de deux opérations :

On cherche une solution où ces deux opérations ont un coût O(log n). L'idée est d'utiliser un arbre de Fenwick : les feuilles contiennent les éléments du tableau et chaque nœud contient la somme 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 FenwickTree.java une classe publique FenwickTree représentant un nœud d'un arbre de Fenwick, possédant les 4 champs suivants :

Ajoutez à la classe FenwickTree :

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

Construction de FenwickTree(3) : [3, 0]
Construction de l'arbre de la figure : [21, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [10, 1, [3, 0], [7, 1, [6, 0], [1, 0]]]]

Déposez le fichier FenwickTree.java ici :

1.2. Représentation d'un tableau rempli de zéros

Écrivez une méthode static FenwickTree allZeros(int n) qui construit un arbre de Fenwick équilibré contenant n feuilles dont la valeur est systématiquement 0. On supposera que n > 0. On pourra procéder récursivement.

Vous pouvez tester votre code à l'aide du fichier Test2.java qui construit les arbres allZeros(3), allZeros(4), allZeros(5) et allZeros(6). Si vous avez choisi de mettre plus de feuilles dans le fils gauche que dans le fils droit lorsque n est impair, le résultat doit être le suivant :

Construction de allZeros(3) : [0, 2, [0, 1, [0, 0], [0, 0]], [0, 0]]
Construction de allZeros(4) : [0, 2, [0, 1, [0, 0], [0, 0]], [0, 1, [0, 0], [0, 0]]]
Construction de allZeros(5) : [0, 3, [0, 2, [0, 1, [0, 0], [0, 0]], [0, 0]], [0, 1, [0, 0], [0, 0]]]
Construction de allZeros(6) : [0, 3, [0, 2, [0, 1, [0, 0], [0, 0]], [0, 0]], [0, 2, [0, 1, [0, 0], [0, 0]], [0, 0]]]

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

Construction de allZeros(3) : [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]]
Construction de allZeros(4) : [0, 2, [0, 1, [0, 0], [0, 0]], [0, 1, [0, 0], [0, 0]]]
Construction de allZeros(5) : [0, 2, [0, 1, [0, 0], [0, 0]], [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]]]
Construction de allZeros(6) : [0, 3, [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]], [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]]]

Déposez le fichier FenwickTree.java ici :

1.3. Taille d'un arbre

Écrivez une méthode dynamique int size() qui renvoie le nombre de feuilles de l'arbre de Fenwick this. Attention, on demande que la fonction s'exécute en temps logarithmique en la taille de l'arbre this.

Vous pouvez tester votre code à l'aide du fichier Test3.java qui calcule la taille des arbres FenwickTree(6), allZeros(6) et allZeros(12). Le résultat doit être le suivant :

Taille de FenwickTree(6) :    1
Taille de allZeros(6) :       6
Taille de allZeros(12) :      12
Arbre this : [21, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [10, 1, [3, 0], [7, 1, [6, 0], [1, 0]]]]
Taille de this :      6

Déposez le fichier FenwickTree.java ici :

1.4. Modification de la valeur d'une feuille

On numérote les feuilles d'un arbre de Fenwick 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 dynamique void increment(int i, int delta) qui modifie l'arbre this pour ajouter delta à la valeur de la feuille de this d'indice i. On suppose que 0 ≤ i < nn est le nombre de feuilles de l'arbre this. On veillera à ce que l'arbre, après modification, soit bien un arbre de Fenwick, c'est-à-dire que les informations contenues dans les champs de ses nœuds internes aient bien tenu compte de la modification. On veillera également à ce que la fonction s'exécute en temps logarithmique en la taille de l'arbre this.

Vous pouvez tester votre code à l'aide du fichier Test4.java qui construit l'arbre de la figure ci-dessus en partant de la structure ne contenant que des 0 et en ajoutant les valeurs voulues à ses feuilles. Le résultat doit être le suivant :

Arbre this :                  [0, 3, [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]], [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]]]
Résultat de increment(0, 4) : [4, 3, [4, 1, [4, 0], [0, 1, [0, 0], [0, 0]]], [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]]]
Résultat de increment(1, 2) : [6, 3, [6, 1, [4, 0], [2, 1, [2, 0], [0, 0]]], [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]]]
Résultat de increment(2, 5) : [11, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [0, 1, [0, 0], [0, 1, [0, 0], [0, 0]]]]
Résultat de increment(3, 3) : [14, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [3, 1, [3, 0], [0, 1, [0, 0], [0, 0]]]]
Résultat de increment(4, 6) : [20, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [9, 1, [3, 0], [6, 1, [6, 0], [0, 0]]]]
Résultat de increment(5, 1) : [21, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [10, 1, [3, 0], [7, 1, [6, 0], [1, 0]]]]

Déposez le fichier FenwickTree.java ici :

1.5. Somme des premières feuilles

Écrivez une méthode dynamique int prefixSum(int upto) qui renvoie la somme des valeurs étiquetant les feuilles de this d'indice compris entre 0 (inclus) et upto (exclus). On suppose que 0 ≤ upto ≤ nn est le nombre de feuilles de l'arbre this. On veillera à ce que la fonction s'exécute en temps logarithmique en la taille de l'arbre this.

Vous pouvez tester votre code à l'aide du fichier Test5.java qui calcule les sommes des premières feuilles de l'arbre de la figure ci-dessus. Le résultat doit être le suivant :

Arbre this : [21, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [10, 1, [3, 0], [7, 1, [6, 0], [1, 0]]]]
Somme des premières feuilles : 
prefixSum(0) : 0
prefixSum(1) : 4
prefixSum(2) : 6
prefixSum(3) : 11
prefixSum(4) : 14
prefixSum(5) : 20
prefixSum(6) : 21

Déposez le fichier FenwickTree.java ici :

1.6. Somme d'une plage de feuilles

Écrivez une méthode dynamique int between(int lo, int hi) qui renvoie la somme des valeurs étiquetant les feuilles de this d'indice compris entre lo (inclus) et hi (exclus). On suppose que 0 ≤ lo ≤ hi ≤ nn est le nombre de feuilles de l'arbre this.

Vous pouvez tester votre code à l'aide du fichier Test6.java qui calcule les sommes de toutes les plages de feuilles de l'arbre de la figure ci-dessus. Le résultat doit être le suivant :

Arbre this : [21, 3, [11, 1, [4, 0], [7, 1, [2, 0], [5, 0]]], [10, 1, [3, 0], [7, 1, [6, 0], [1, 0]]]]
Somme des feuilles entre lo et hi : 
         lo = 0  lo = 1  lo = 2  lo = 3  lo = 4  lo = 5  lo = 6  
hi = 0   0       
hi = 1   4       0       
hi = 2   6       2       0       
hi = 3   11      7       5       0       
hi = 4   14      10      8       3       0       
hi = 5   20      16      14      9       6       0       
hi = 6   21      17      15      10      7       1       0       

Déposez le fichier FenwickTree.java ici :

Exercice 2 : Tables de Hachage

Le but de cet exercice est de supprimer les doublons dans un long tableau de phrases. Une phrase est représentée par un objet de la classe Sentence qui contient un tableau contenant les mots de la phrase. Pour supprimer les doublons, on utilisera 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. Représenter les phrases

Écrivez une classe Sentence avec un champ String[] words, un constructeur public Sentence(String[] words) et une méthode public String toString() qui renvoie la chaîne de caractères formée par les mots de la phrase séparés par des espaces.

Nous allons aussi avoir besoin d'un générateur de phrases. Écrivez un constructeur public Sentence(String[][] possibleWords) qui construit une phrase dont le ième mot est choisi aléatoirement parmi les éléments du ième tableau de possibleWords (qu'on suppose non vide). Par exemple, si possibleWords est le tableau {{"Toto", "Tata", "Tutu"}, {"court", "dort", "lit"}, {"à"}, {"la"}, {"plage", "montagne", "maison"}}, alors Sentence(possibleWords) pourra construire des phrases comme :

Tata lit à la maison
Tutu court à la plage
Tata dort à la plage
Toto lit à la montagne
Toto dort à la plage

Déposez le fichier Sentence.java ici :

2.2. Retirer les doublons

Dans une classe KillDuplicates, écrivez une méthode public static Sentence[] killDuplicates(Sentence[] arrayWithDuplicates) qui prend en argument un tableau de phrases arrayWithDuplicates contenant éventuellement des doublons et renvoie un tableau qui contient une et une seule fois chaque phrase de arrayWithDuplicates. Pour cette méthode, utilisez un HashSet<Sentence> et complétez en conséquence la classe Sentence avec les méthodes public int hashCode() et public boolean equals(Object o) nécessaires à l'utilisation de HashSet.

Ajoutez une méthode public static void main(String[] args) qui teste votre méthode killDuplicates sur un tableau de 1000 phrases construites aléatoirement parmi les mots {{"Toto", "Tata", "Tutu"}, {"court", "dort", "lit"}, {"à"}, {"la"}, {"plage", "montagne", "maison"}}.

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


solutions