INF411
Pour commencer :
Remarque: les deux exercices sont indépendants et peuvent se traiter dans n’importe quel ordre.
La documentation de Java est accessible en local via le lien suivant: Documentation Java
The english version of this midterm can be downloaded here (.pdf file): english version
Une solution possible du TD7 se trouve ici: solution
Dans cet exercice nous allons implémenter une manière efficace de supprimer les doublons dans une collection d’images fournie en entrée.
Les images que nous allons manipuler sont binaires (pixels noirs ou blancs) et seront représentées par la classe
class BinaryImage {
public static final boolean WHITE = false;
public static final boolean BLACK = true;
/** 2D array representing the image pixels */
final boolean[][] pixels;
/** Create an image of n rows and m columns */
BinaryImage(int n, int m) {
1 && m >= 1;
assert n >= this.pixels = new boolean[n][m];
} }
Afin de détecter de manière efficace l’existence d’éventuels doublons, nous allons nous servir de tables de hachage. Pour ce faire, on vous rappelle notamment l’existence de la classe HashSet<K>
fournie par Java, permettant de stocker un ensemble d’éléments dont le type est K
.
Dans la classe BinaryImage
, complétez la méthode boolean equals(Object o)
qui renvoie true
si l’image courante est égale à l’image o
en entrée (les valeurs de leurs pixels coïncident), false
sinon.
Testez votre code avec la classe Test11
.
Déposez BinaryImage.java
.
Dans la classe BinaryImage
, complétez la méthode int hashCode()
qui renvoie la valeur de hachage de l’image. Deux images égales devraient avoir la même valeur de hachage.
Dans la classe BinaryImage
, complétez la méthode BinaryImage[] deleteDuplicates(BinaryImage[] t)
qui prend en entrée un tableau d’images t
et qui renvoie un nouveau tableau sans doublons. Plus précisément, si le tableau t
a taille k
et contient d
images distinctes alors le tableau à renvoyer aura la taille d
et ne contiendra aucun doublon.
Suggestion : la classe
HashSet<K>
fournit une implémentation à base de hachage des opérations qui agissent sur un ensemble d’éléments de typeK
(notamment l’ajout d’un élément ainsi que le test d’appartenance).
Testez votre code avec la classe Test12
.
Déposez BinaryImage.java
.
Dans cet exercice nous allons étudier les arbres rouges et noirs, qui sont une variante des arbres binaires de recherche permettant de garder un bon équilibre de l’arbre : la hauteur d’un arbre rouge et noir contenant n nœuds est O(log2n).
Un arbre rouge et noir est défini comme un arbre binaire de recherche dont les nœuds ont une couleur (rouge ou noir) et satisfaisant les conditions ci-dessous :
class RBT extends IntegerPoint2D {
final static boolean RED = true;
final static boolean BLACK = false;
boolean color;
RBT left, right;String element;
/* Construit un noeud d'un arbre binaire Rouge-Noir */
RBT(boolean color, RBT left, String element, RBT right) {
this.color = color;
this.left = left;
this.element = element;
this.right = right;
} }
On représente un arbre ou un sous-arbre par son nœud racine à l’aide de la classe RBT
(Red-Black Tree). Un nœud contient un champ String element
(la donnée à stocker), et des pointeurs vers les sous-arbres gauche et droit. On ajoute à chaque nœud l’information concernant sa couleur (champ boolean color
). Les couleurs rouge et noire sont encodées par des constantes final static boolean RED
et final static boolean BLACK
.
Comme déjà fait auparavant (TD6 et cours), l’arbre vide est représenté par null
. Les feuilles (qui sont noires) sont représentées par des nœuds sentinelles encodés par null
(petits carrés noirs dans l’image ci-dessous).
Voici deux exemples d’arbres rouges et noirs :
Lors du debugging de votre code, il pourrait s’avérer utile de visualiser un arbre t
donné. Pour cela il suffit d’utiliser l’instruction
new DrawBinaryTree(t);
qui ouvre une fenêtre graphique et y dessine l’arbre comme dans l’exemple ci-dessus.
On souhaite implémenter une fonction qui teste si un arbre (qu’on suppose vérifier la condition des arbres binaires de recherche) est un arbre rouge et noir.
Dans la classe RBT
, complétez la méthode boolean isRedValid(RBT t)
qui renvoie true
si l’arbre t
vérifie la condition (2) pour tous les nœuds rouges.
Testez votre code avec la classe Test21
.
Déposez RBT.java
.
Dans la classe RBT
, complétez la méthode boolean isBlackValid(RBT t)
qui renvoie true
si l’arbre t
vérifie la condition (3) de la définition ci-dessus.
Testez votre code avec la classe Test22
.
Déposez RBT.java
.
Dans la classe RBT
, complétez la méthode boolean isValid(RBT t)
qui renvoie true
si l’arbre t
est un arbre binaire rouge et noir.
Testez votre code avec la classe Test23
.
Déposez RBT.java
.
Pour construire un arbre rouge et noir à partir d’une liste triée une solution simple à implémenter consiste à procéder de la manière suivante (illustrée par les images ci-dessous). D’abord on estime la hauteur finale de l’arbre rouge et noir (supposant qu’on essaie d’obtenir un équilibrage parfait). Ensuite on construit un arbre binaire de recherche dont tous les nœuds sont noirs, sauf éventuellement au dernier niveau (le seul qui pourrait être incomplet).
Voici quelques exemples d’arbres rouges et noirs construits avec cette stratégie à partir de listes triées de différentes tailles :
Dans la classe RBT
, complétez la méthode int estimateBlackHeight(int n)
qui renvoie l’entier h ≥ 0 satisfaisant (pour n ≥ 0) :
2h − 1 ≤ n < 2h + 1 − 1
Remarque : la fonction ci-dessus permet d’estimer le nombre de niveaux complets de l’arbre. On considère que pour l’arbre vide la fonction ci-dessus renvoie 0 (pas de nœuds internes) et pour un arbre de taille 1 (un seul nœud interne, la racine) elle renvoie 1.
Testez votre code avec la classe Test24
.
Déposez RBT.java
.
Dans la classe RBT
, complétez la méthode RBT ofList(LinkedList<String> l)
qui renvoie un arbre binaire de recherche rouge et noir contenant les éléments de la liste l
comme décrit plus haut.
Remarque : la fonction
ofList(LinkedList<String> l)
peut modifier la listel
en entrée (si cela peut s’avérer utile).
Testez votre code avec la classe Test25
.
Déposez RBT.java
.