Pale machine du mardi 16 octobre 2018


Votre opinion sur le cours de lundi : Votre opinion sur le TD précédent :

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

Exercice 1 : Triplets d'indices consécutifs dans un tableau

On ne vous donne pas de squelette dans cet exercice. Vous devez donc créer vos classes et vos tests vous-mêmes. Vous serez bien attentifs à nommer les classes et méthodes comme spécifié dans l'énoncé.

1.1. Triplets d'entiers distincts d'indices consécutifs

Créez une classe Triple avec trois champs entiers a, b et c, un constructeur Triple(int a, int b, int c), et une méthode public String toString() qui affiche (a, b, c).

Dans une classe ConsecutiveTriples, écrivez une méthode static LinkedList<Triple> consecutiveTriplesDistinctNumbers(int[] t) qui renvoie la liste des triplets d'entiers d'indices consécutifs formés par 3 nombres distincts dans le tableau t. Chaque triplet doit avoir 3 entiers distincts, mais certains triplets peuvent se répéter. Par exemple, sur le tableau {1,1,3,1,5,3,1,5,1}, votre méthode consecutiveTriplesDistinctNumbers doit renvoyer les 4 triplets suivants : (3, 1, 5), (1, 5, 3), (5, 3, 1), (3, 1, 5). Pensez à ajouter import java.util.LinkedList au début de votre fichier.

Dans la classe ConsecutiveTriples, écrivez une méthode public static void main(String[] args) qui affiche tous les triplets d'entiers distincts d'indices consécutifs du tableau {1,1,3,1,5,3,1,5,1}. On rappelle qu'on peut construire ce tableau avec la syntaxe new int[] {1,1,3,1,5,3,1,5,1}.

Déposez le fichier Triple.java, puis le fichier ConsecutiveTriples.java ici :

1.2. Triplets distincts d'entiers d'indices consécutifs

Dans la classe ConsecutiveTriples, écrivez une méthode static LinkedList<Triple> distinctConsecutiveTriples(int[] t) qui renvoie une liste contenant tous les triplets d'entiers d'indices consécutifs dans le tableau t. Cette fois, chaque triplet ne doit être présent qu'une seule fois dans cette liste. L'ordre des triplets dans cette liste n'est pas important. Par exemple, sur le tableau {1,1,3,1,5,3,1,5,1}, votre méthode distinctConsecutiveTriples pourra renvoyer les 6 triplets suivants : (1, 3, 1), (3, 1, 5), (1, 5, 3), (5, 3, 1), (1, 5, 1), (1, 1, 3).

Pour cela, vous devrez implémenter correctement les fonctions public boolean equals(Object o) et public int hashCode() de la classe Triple. Vous utiliserez ensuite un HashSet<Triple> pour mémoriser tous les triplets d'entiers d'indices consécutifs de t. Pensez à ajouter import java.util.HashSet au début de votre fichier.

Modifiez la méthode main de la classe ConsecutiveTriples pour qu'elle affiche tous les triplets distincts d'entiers d'indices consécutifs du tableau {1,1,3,1,5,3,1,5,1}. On rappelle qu'on peut construire ce tableau avec la syntaxe new int[] {1,1,3,1,5,3,1,5,1}.

Déposez le fichier Triple.java, puis le fichier ConsecutiveTriples.java ici :

Exercice 2 : Matrices doublement triées

Dans cet exercice, on recherche une valeur dans une matrice carrée d'entiers en essayant de limiter autant que possible le nombre de requêtes à la matrice.

On vous fournit une classe Matrix avec :

Téléchargez et décompressez dans votre répertoire src le fichier exercice2.zip qui contient la classe Matrix, le squelette de la classe FindMatrix, et un certain nombre de fichiers de tests.

2.1. Recherche exhaustive dans une matrice

On va maintenant chercher une valeur v dans une matrice. Sans aucune hypothèse sur la structure de la matrice, nous n'avons d'autre choix qu'une recherche exhaustive de toutes les entrées. Dans la classe FindMatrix, complétez la méthode static int findMatrix(Matrix mat, int v) pour qu'elle recherche la valeur v dans la matrice mat.

Si la valeur v est trouvée en mat.data[i][j], on renverra l'entier mat.size*i+j. Si la valeur v n'est pas dans mat, on renverra la valeur -1.

Testez votre méthode avec le fichier Test21.java.

Déposez le fichier FindMatrix.java ici :

2.2. Recherche dans une matrice doublement triée

On suppose maintenant que les lignes et les colonnes de la matrice sont croissantes. Remarquons que sous cette hypothèse, une requête compare(0, size-1, v) nous permet d'éliminer soit toute la ligne 0 (si mat.data[0][size-1] < v), soit toute la colonne size-1 (si mat.data[0][size-1] > v).

Utilisez cette observation pour compléter la méthode static int findDoublySortedMatrix(Matrix mat, int imin, int jmax, int v) de la classe FindMatrix pour qu'elle recherche la valeur v dans la sous-matrice de mat formée par les lignes de imin à size-1 (inclus) et les colonnes de 0 à jmax (inclus). En déduire la méthode static int findDoublySortedMatrix(Matrix mat, int v) qui recherche la valeur v dans la matrice mat en supposant que les lignes et les colonnes de la matrice sont croissantes.

Si la valeur v est trouvée en mat.data[i][j], on renverra l'entier mat.size*i+j. Si la valeur v n'est pas dans mat, on renverra la valeur -1.

Testez votre méthode avec le fichier Test22.java.

Déposez le fichier FindMatrix.java ici :

2.3. La matrice de Hamming

La matrice de Hamming est la matrice dont le coefficient mat.data[i][j] est 2^i * 3^j. Elle est donc doublement triée. Par exemple, la matrice de Hamming de taille 4 est la matrice suivante :

1 3 9 27
2 6 18 54
4 12 36 108
8 24 72 216

Dans la classe FindMatrix, complétez la méthode static Matrix HammingMatrix(int size) pour qu'elle construise la matrice de Hamming de taille size en utilisant uniquement des additions. Notez que comme le champ data de la classe Matrix est privé, il faudra d'abord construire un tableau bidimensionnel d'entiers et utiliser ensuite le constructeur Matrix(int[][] data).

Testez votre code avec le fichier Test23.java. Ce fichier utilise votre méthode HammingMatrix pour construire toutes les matrices de Hamming de taille au plus 10 et vérifie que ces matrices sont correctes. Ensuite il affiche le nombre de requêtes effectuées par vos méthodes findMatrix et findDoublySortedMatrix pour trouver 512 (= 2^9), 19683 (= 3^9) et 7776 (= 2^5 * 3^5) dans la matrice de Hamming de taille 10.

Déposez le fichier FindMatrix.java ici :

Exercice 3 : Dessiner des arbres

Le but de cet exercice est d'écrire un algorithme pour faire de beaux dessins d'arbres comme ceux-ci :

Téléchargez et décompressez dans votre répertoire src le fichier exercice3.zip qui contient le squelette de la classe Tree qui modélise les arbres, une classe TreeImage qui permettra d'afficher un arbre une fois qu'on aura décidé des coordonnées de ses sommets (section 3), et un certain nombre de fichiers de tests.

3.1. Manipulation d'arbres

3.1.1. Constructeur

On représente les arbres par la classe Tree avec un champ Tree[] children pour les sous-arbres et un champ int height pour la hauteur de l'arbre. On rappelle que la hauteur d'un arbre est le nombre de nœuds le long du plus long chemin de la racine à une feuille de l'arbre (par exemple, une feuille a hauteur 1 et les arbres ci-dessus ont des hauteurs 5, 6 et 5 respectivement).

Notez bien que

On vous fournit un constructeur Tree() qui construit un arbre constitué d'un unique nœud. Complétez le constructeur Tree(Tree[] children) pour qu'il construise un arbre dont les sous-arbres sont donnés par le tableau children. Attention à bien mettre à jour le champ height. Ne vous préoccupez pas pour l'instant des autres champs de la classe Tree.

Testez votre classe avec le fichier Test311.java.

Déposez le fichier Tree.java ici :

3.1.2. Miroir

On appelle miroir d'un arbre t l'arbre obtenu par une symétrie verticale de t. Par exemple, les deux arbres suivants sont miroirs l'un de l'autre :

Dans la classe Tree, complétez la méthode Tree mirror() qui crée et renvoie l'arbre obtenu comme miroir de l'arbre this.

Testez votre classe avec le fichier Test312.java.

Déposez le fichier Tree.java ici :

3.1.3. Arbres réguliers

On dit qu'un arbre est régulier de degré d si tous ses nœuds internes (i.e. qui ne sont pas des feuilles) ont exactement d sous-arbres. Un arbre est complet si toutes ses feuilles sont à la même profondeur. Par exemple, les arbres suivants sont réguliers et complets, de degré 2 et 3, et de hauteur 5 et 4 respectivement.

Dans la classe Tree, complétez la méthode static Tree regularTree(int degree, int height) pour qu'elle renvoie un arbre régulier de degré degree et de hauteur height.

Testez votre classe avec le fichier Test313.java.

Déposez le fichier Tree.java ici :

3.2. Dessins d'arbres

On passe maintenant aux dessins d'arbres. On se fixe les règles esthétiques suivantes :

  1. Deux nœuds au même niveau doivent être espacés horizontalement d'une distance au moins 1.
  2. Tout nœud est centré au-dessus de ses sous-arbres (autrement dit, l'abscisse d'un nœud est la moyenne des abscisses de son premier et de son dernier sous-arbre).
  3. Si deux sous-arbres sont identiques, ils doivent être dessinés identiquement.
  4. Le dessin du miroir d'un arbre doit être la symétrie verticale du dessin de cet arbre.

L'idée de l'algorithme de dessin que vous allez implémenter est de procéder inductivement : pour dessiner un arbre t, on commence par dessiner séparément les sous-arbres de t, puis on essaie de placer ces sous-arbres les uns à côté des autres en respectant les règles esthétiques décrites ci-dessus.

Chaque nœud n de l'arbre t va être positionné à une certaine position (xn, yn) que nous allons déterminer. L'ordonnée yn sera juste donnée par la profondeur du nœud n dans l'arbre t et nous n'avons donc pas à nous en préoccuper ici. Pour calculer l'abscisse xn, le nœud n va se souvenir de son abscisse relative par rapport à son nœud parent (négative si le nœud est à gauche de son parent, positive s'il est à droite). Cette information va être stockée dans un champ relativePosition de la classe Tree.

Voici un exemple concret :

Par ailleurs, pour pouvoir placer les sous-arbres les uns à côté des autres, nous avons besoin de nous souvenir de la zone occupée par un arbre t. Pour cela, nous allons utiliser 4 champs additionnels dans la classe Tree résumés sur le schéma suivant :

On appelle ombre de t la donnée de ces 4 champs.

Par exemple, sur l'arbre dont les coordonnées sont données par :

les valeurs de ces champs seront les suivantes :

3.2.1. Calcul de l'ombre

Complétez votre constructeur Tree(Tree[] children) pour qu'il initialise :

On suppose maintenant que nous avons décidé des abscisses relatives des sous-arbres d'un arbre t et que les ombres des sous-arbres de t ont été calculées. Complétez la méthode void updateShadow() de la classe Tree pour qu'elle mette alors à jour l'ombre de l'arbre t. Autrement dit, après l'appel de updateShadow, l'ombre de l'arbre t doit contenir les valeurs suivantes :

Testez votre classe avec le fichier Test321.java.

Déposez le fichier Tree.java ici :

3.2.2. Placer deux ombres l'une à côté de l'autre

Considérons que nous avons deux ombres G et D que nous souhaitons placer le plus proche possible l'une à côté de l'autre (avec G à gauche et D à droite) de sorte qu'à chaque niveau, l'extrémité droite de G est au moins à distance 1 de l'extrémité gauche de D. Voici une illustration :

Pour calculer la distance minimale entre les racines de G et D, il suffit donc de connaître les tableaux rightmostPositions des abscisses les plus à droite de G et leftmostPositions des abscisses les plus à gauche de D et de chercher la valeur maximale de rightmostPositions[j] - leftmostPositions[j] + 1. Attention tout de même que les tableaux rightmostPositions et leftmostPositions peuvent être de longueur différente.

Complétez la méthode static float minimalDistance(float[] rightmostPositions, float[] leftmostPositions) de la classe Tree pour qu'elle calcule et renvoie cette valeur minimale.

Testez votre classe avec le fichier Test322.java.

Déposez le fichier Tree.java ici :

3.2.3. Positionnement des sous-arbres

Nous supposons maintenant que nous avons dessiné séparément tous les sous-arbres d'un arbre t, c'est-à-dire qu'on a décidé des positions relatives de tous leurs descendants et que leurs ombres sont bien à jour. Nous allons maintenant décrire la méthode qui va nous permettre de positionner ces sous-arbres par rapport à la racine de l'arbre t en changeant juste les valeurs de leur champ relativePosition. L'idée est d'ajouter un à un les sous-arbres de t le plus proche possible de ceux que l'on a déjà placés. Le résultat dépend de l'ordre dans lequel on ajoute les nœuds. Par exemple, si les sous-arbres d'un arbre sont dessinés ainsi :

alors nous obtiendrions les dessins suivants en ajoutant les sous-arbres de t de gauche à droite, ou de droite à gauche :

Pour régler cette asymétrie et satisfaire notre quatrième critère esthétique (« le dessin du miroir d'un arbre doit être la symétrie verticale du dessin de cet arbre »), nous allons faire une moyenne entre ces deux solutions pour obtenir le dessin suivant :

Complétez la méthode void computeChildrenPositions() de la classe Tree pour qu'elle calcule les positions relatives des sous-arbres de t (qu'on suppose déjà dessinés séparément, c'est-à-dire qu'on a décidé des positions relatives de tous leurs descendants et que leurs ombres sont à jour) en deux étapes symétriques l'une de l'autre :

  1. ajout des sous-arbres de gauche à droite :
  2. Voici à quoi ressemble une étape de cette première partie :

  3. ajout des sous-arbres de droite à gauche :
  4. Voici à quoi ressemble une étape de cette deuxième partie :

Testez votre classe avec le fichier Test323.java.

Déposez le fichier Tree.java ici :

3.2.4. Dessin et visualisation

Nous sommes maintenant prêts à calculer le dessin d'un arbre t. Pour cela, il faut effectuer 3 opérations :

  1. calculer les dessins des sous-arbres de t,
  2. calculer les positions relatives des sous-arbres de t en utilisant la méthode computeChildrenPositions,
  3. mettre à jour l'ombre de t en utilisant la méthode updateShadow.

Complétez la méthode void computeDrawing() de la classe Tree pour qu'elle calcule le dessin de l'arbre t.

Testez votre classe avec le fichier Test3241.java.

Pour finir, on veut visualiser les dessins de nos arbres. On vous a fourni un fichier TreeImage.java qui s'occupe du dessin une fois que vous avez décidé de toutes les coordonnées relatives. Vous pouvez donc tester votre code avec le fichier Test3242.java. Vous devriez obtenir les dessins suivants :

Déposez le fichier Tree.java ici :


Voici une solution possible : solutions.zip