Les deux exercices sont indépendants. Attention à déposer les fichiers .java (et pas les .class).
Le double hachage est une méthode de hachage un peu différente de celle vue en cours. On suppose qu'on veut représenter un ensemble d'au plus N éléments d'un type E muni de deux fonctions de hachage hash1 et hash2. On construit un tableau E[] tab de longueur N. Pour insérer un element e, on calcule le code de hachage pos = e.hash1() et on considère la case du tableau tab en position pos modulo N. Si cette case est inoccupée, on y insère e ; sinon, on ajoute e.hash2() à pos (modulo N). On répète ainsi de suite en ajoutant e.hash2() à pos (modulo N) tant que la case de tab en position pos est occupée. En supposant que e.hash2() modulo N est non nul et que N est premier, on ne reviendra sur la position initiale e.hash1() qu'une fois qu'on aura visité toutes les cases de tab, et il sera donc toujours possible d'insérer un nouvel élement e dans le tableau tab tant que celui-ci n'est pas plein.
Dans cet exercice, on suppose qu'on ne retire jamais d'éléments de la table. Ainsi, pour rechercher dans la table, il suffit de visiter les cases de tab dans le même ordre que pour l'insertion.
Dans cet exercice, on va utiliser le double hachage pour détecter les doublons dans une liste de matrices. Les objets de type E seront donc des objets de la classe Matrix que l'on va maintenant écrire.
Créez une classe Matrix avec un champ int[][] mat qui représente une matrice d'entiers, et écrivez un constructeur Matrix(int[][] mat). Ajoutez des fonctions de hachage int hash1() et int hash2() et une méthode public boolean equals(Object o). Dans ces trois fonctions, on supposera que le champ mat n'est pas null. Pour que votre code soit efficace, veillez à ce que vos fonctions de hachage distinguent aussi bien que possible toutes les matrices.
Écrivez une méthode static Matrix randomMatrix(int n, int m, int k) qui construit une matrice de taille n x m dont chaque coefficient est tiré aléatoirement entre 0 et k-1.
Pour tester vos méthodes, écrivez dans la classe Matrix une méthode public static void main(String[] args) qui affiche les codes hash1 et hash2 de 100 matrices tirées aléatoirement avec randomMatrix(4,4,2). Vérifiez que vous n'obtenez pas trop souvent les mêmes valeurs.
Déposez le fichier Matrix.java ici :
Créez une classe DoubleHashing avec :
Pour tester, écrivez dans la classe DoubleHashing une méthode public static void main(String[] args) qui crée une table de hachage et affiche les valeurs de -65536, 1 et 65538 modulo N, en utilisant votre méthode modulo.
Déposez le fichier DoubleHashing.java ici :
Dans cette classe DoubleHashing, écrivez une méthode void add(Matrix m) qui ajoute une matrice à tab comme décrit plus haut : on place m à la position m.hash1() + k * m.hash2() où 0 ≤ k < N est minimal pour que m.hash1() + k * m.hash2() soit vide. On suppose ici que le tableau tab n'est pas plein, de sorte que l'insertion est toujours possible. Attention : pour éviter une possible boucle infinie, remplacez m.hash2() par 1 dans la formule précédente si m.hash2() modulo N est nul.
Pour tester votre insertion, modifiez la méthode main de la classe DoubleHashing pour qu'elle insère 100 matrices tirées aléatoirement avec randomMatrix(4,4,2).
Déposez le fichier DoubleHashing.java ici :
Dans la classe DoubleHashing, écrivez une méthode boolean find(Matrix m) qui recherche une matrice dans tab. Pour cela, vous devrez visiter toutes les positions m.hash1() + k * m.hash2() avec 0 ≤ k < N jusqu'à trouver soit m, soit une case vide. Attention : comme pour l'insertion, vous devez remplacer m.hash2() par 1 dans la formule précédente si m.hash2() modulo N est nul.
Pour tester votre recherche, modifiez la méthode main de la classe DoubleHashing pour qu'elle insère 100 matrices tirées aléatoirement avec randomMatrix(4,4,2), puis cherche la dernière ajoutée.
Déposez le fichier DoubleHashing.java ici :
Créez une classe Duplicates. En utilisant la classe DoubleHashing, écrivez une méthode static boolean containsDuplicate(LinkedList<Matrix> l) qui teste si une liste l de matrices contient deux matrices identiques.
Dans la classe Duplicates, écrivez une méthode public static void main(String[] args) qui teste votre recherche de doublons avec une liste de matrices contenant des doublons et une liste de matrices n'en contenant pas.
Déposez le fichier Duplicates.java ici :
Un QR code est un type de code-barres en deux dimensions formé de cases noires ou blanches. Pour simplifier, on suppose qu'un QR code est la donnée d'une matrice de 0 et de 1 de taille 4 x 4. Ainsi, il y a 2^16 = 65536 QR codes différents.
Dans la méthode main de la classe Duplicates, tirez aléatoirement 100 listes de QR codes de longueur 200 et 100 listes de QR codes de longueur 400. Combien de ces listes possèdent au moins un doublon ?
Déposez le fichier Duplicates.java ici :
Dans cet exercice, on s'intéresse à trois mesures sur les arbres binaires :
Voici quelques exemples :
| t1 | t2 | t3 | |
|---|---|---|---|
|
|
|
|
| taille | 8 | 5 | 5 |
| canopée | 3 | 3 | 2 |
| hauteur | 4 | 3 | 4 |
Pour obtenir des exemples à plus grande échelle, on utilisera particulièrement deux familles d'arbres binaires :
Par exemple, voici le peigne gauche et l'arbre binaire parfait de hauteur 4 :
Pour revenir sur nos mesures, le peigne gauche de hauteur h a pour taille h et pour canopée 1, alors que l'arbre binaire parfait de hauteur h a pour taille 2h-1 et pour canopée 2h-1.
Pour représenter les arbres binaires, on vous fournit la classe Tree suivante :
public class Tree {
final Tree left, right;
Tree(Tree left, Tree right) {
this.left = left;
this.right = right;
}
}
Ces arbres ne contiennent pas de valeurs car elles ne jouent pas de rôle dans cet exercice. Les champs left et right représentent les fils gauche et droit. L'arbre vide est représenté par null. Cette classe se trouve dans le fichier Tree.java à télécharger et ne devra pas être modifiée. Par ailleurs, le fichier Measures.java à télécharger vous fournit le squelette de la classe Measures dans lequel vous allez travailler.
Dans la classe Measures, complétez les méthodes récursives suivantes :
Attention, on demande ici que toutes les méthodes soient récursives.
Pour tester vos méthodes, nous mesurons la taille, la canopée et la hauteur des arbres t1, t2 et t3 ci-dessus, du peigne gauche de hauteur 1000 et de l'arbre binaire parfait de hauteur 10. Utilisez le fichier Test21.java fourni pour valider votre code. Si tout se passe bien, l'exécution doit afficher :
Tests de leftCombRec... [OK] Tests de perfectTreeRec... [OK] Tests de sizeRec... [OK] Tests de canopyRec... [OK] Tests de heightRec... [OK]
Déposez le fichier Measures.java ici :
Pour pousser un peu les tests, nous allons maintenant regarder un peigne de hauteur 20000. Décommentez la ligne leftCombRec(20000); dans la méthode main de la classe Measures. Que constatez-vous ?
En fait, sur le peigne gauche de hauteur 20000 qui est complètement filiforme, les méthodes récursives leftCombRec, sizeRec, canopyRec et heightRec remplissent toute la pile d'appels récursifs et aboutissent donc toutes à une erreur de type StackOverflowError. Pour remédier à ce problème, une solution serait d'augmenter la taille de la pile d'appels récursifs de la machine virtuelle java. Dans la suite de cet exercice, nous allons plutôt écrire des méthodes itératives pour la création d'un peigne gauche et le calcul de la taille, de la canopée et de la hauteur d'un arbre binaire.
Pour la suite, pensez à recommenter la ligne leftCombRec(20000); dans la méthode main de la classe Measures.
Complétez la méthode static Tree leftCombIt(int h) de la classe Measures pour qu'elle renvoie un peigne gauche de hauteur h, construit avec une boucle (cette méthode ne doit pas être récursive). Utilisez le fichier Test221.java fourni pour valider votre code. Si tout se passe bien, l'exécution doit afficher :
Tests de leftCombIt... [OK]
Déposez le fichier Measures.java ici :
Pour effectue le calcul itératif de la taille d'un arbre binaire t, on procède comme suit :
Complétez la méthode static int sizeIt(Tree t) de la classe Measures pour qu'elle renvoie la taille de l'arbre binaire t calculée de manière itérative. Utilisez le fichier Test222.java fourni pour valider votre code. Si tout se passe bien, l'exécution doit afficher :
Tests de sizeIt... [OK]
Déposez le fichier Measures.java ici :
En utilisant une liste comme à la question précédente, complétez la méthode static int canopyIt(Tree t) de la classe Measures pour qu'elle renvoie la canopée de l'arbre binaire t calculée de manière itérative. Utilisez le fichier Test223.java fourni pour valider votre code. Si tout se passe bien, l'exécution doit afficher :
Tests de canopyIt... [OK]
Déposez le fichier Measures.java ici :
Le calcul itératif de la hauteur d'un arbre binaire t est un peu plus complexe. L'idée est d'utiliser une liste auxiliaire subtrees de paires (s, d) où s est un sous-arbre de t et d est la distance de la racine de s à la racine de t.
On représentera ces paires avec la classe Pair suivante :
public class Pair {
Tree t;
int d;
public Pair(Tree t, int d) {
this.t = t;
this.d = d;
}
}
Cette classe se trouve dans le fichier Pair.java à télécharger et ne devra pas être modifiée.
Complétez la méthode static int heightIt(Tree t) de la classe Measures pour qu'elle renvoie la hauteur de l'arbre binaire t calculée de manière itérative. Utilisez le fichier Test224.java fourni pour valider votre code. Si tout se passe bien, l'exécution doit afficher :
Tests de heightIt... [OK]
Déposez le fichier Measures.java ici :
Il existe beaucoup d'autres solutions pour calculer la hauteur d'un arbre binaire de manière itérative. L'une d'entre elles est d'effectuer un parcours en largeur qui sera étudié au TD7.