TD 5 - Pale machine

Votre opinion sur le cours d'hier matin  : Votre opinion sur le TD de la semaine dernière  :

 Login :  Mot de passe :

Préambule

Les deux exercices sont indépendants.

La clarté du code, sa bonne indentation et des commentaires éventuels seront pris en compte dans la notation.

Nous tiendrons compte également de la complexité de vos algorithmes, notamment lorsqu'une complexité attendue a été spécifiée dans la question.

À la différence de INF311, il n'y a pas de correction automatique à la volée. Comme pour les autres TDs, des tests vous sont proposés à chaque question.

Les documents autorisés sont : le polycopié de cours, les reproductions des planches des amphis, vos notes de cours.

Que la force soit avec vous.



Exercice 1 - Arbres binaires de recherche

Dans cet exercice nous allons programmer quelques constructions sur des arbres binaires de recherche. L'une d'entre elles a des applications à la diffusion chiffrée (voir plus loin).

On rappelle qu'un arbre binaire de recherche est un arbre dont chaque sommet contient un entier et tel que pour tout sommet

Question 1.1 : Mise en route

Les arbres binaires de recherche sont représentés par la classe BST.java fournie.

public class BST {
	final int value;
	final BST left, right;
              ...

Important :

Pour commencer,

Le Test1_1.java permet de tester ces méthodes. Son exécution doit donner exactement :

L'arbre T est-il une feuille? true
L'arbre T est-il une feuille? false
--------------------------
Liste ordonnee des sommets de T :  11 18 20 23 49 57 124 139 228 252
--------------------------
La valeur minimale des sommets de T est : 11
On retire ce sommet.
La valeur minimale des sommets de T est : 18
--------------------------
Liste ordonnee des sommets de T :  18 20 23 49 57 124 139 252
--------------------------
L'arbre T contient-il les sommets 11, 18 et 124?  false true true

Déposez le ficher BST.java   :

Question 1.2 : Vérification

On veut vérifier qu'un arbre binaire vérifie bien les propriétés d'un arbre binaire de recherche. On dispose d'une méthode boolean isBST(BST T) qui fait appel à une méthode annexe isBSTBounded(BST T, int min, int max). On vous demande de compléter la méthode annexe isBSTBounded(BST T, int min, int max) qui vérifie si un arbre est bien un arbre binaire de recherche dont tous les sommets sont strictement compris entre min et max.

On pourra tester cette méthode avec le Test1_2.java, qui doit renvoyer :

Les arbres A, T, W et X sont-ils des arbres binaires de recherche?
false true false false

Déposez le ficher BST.java   :

Question 1.3 : Arbres parfaits

On souhaite construire des arbre binaires de recherche parfaits, c'est-à-dire où chaque sommet est soit une feuille (n'a pas de descendant) soit a exactement deux descendants, et où de plus toutes les feuilles sont à la même distance de la racine. Par exemple, les arbres binaires suivants sont parfaits :



... et celui-ci ne l'est pas :



On souhaite de plus que les étiquettes des sommets contiennent tous les entiers de 0 à 2h+1- 2, où h désigne la hauteur de l'arbre, tout en conservant la propriété d'arbre binaire de recherche. Ce qui donne :



Pour construire de tels arbres, on remarque qu'ils vérifient les propriétés suivantes :
  1. La racine contient l'entier 2h-1 ;
  2. Si un nœud est à l'étage i>0 et a pour valeur v, alors son descendant direct de gauche a pour valeur v-2i-1
  3. et celui de droite a pour valeur v+2i-1.

Dans la classe BST.java,

Indication : on rappelle que 2n peut être codé par 1 << n. Attention cependant à la priorité de l'opérateur <<, moins forte que celle des opérations + et -. Ajouter des parenthèses si nécessaire.

Le Test1_3.java doit renvoyer :

On construit un arbre parfait de hauteur 2.
Est-il equilibre?  true
Liste ordonnee de ses sommets :  0 1 2 3 4 5 6
----------------------------
On construit un arbre parfait de hauteur 4.
Est-il equilibre?  true
Liste ordonnee de ses sommets :  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Déposez le ficher BST.java   :

Question 1.4 : Diffusion chiffrée

On dispose d'un arbre binaire parfait de hauteur h dont les sommets contiennent tous les entiers de 0 a 2h-2 comme défini dans la section précédente. Toutefois, vous pouvez traiter cette question même si vous n'êtes pas parvenu à traiter la précédente. On se donne un ensemble de feuilles de l'arbre, ici colorées en rouge, représenté par un tableau d'entiers triés dans l'ordre croissant. Par exemple [2, 8, 10] :


On considère le sous-arbre formé par l'ensemble des chemins allant de la racine vers ces feuilles colorées en rouge :



Le but de l'exercice est de programmer une méthode permettant de renvoyer la liste des racines de tous les sous-arbres complémentaires, classées dans l'ordre croissant. Ici on obtient la liste [0, 5, 13] :



On vous demande donc de compléter les deux méthodes:

Dans computeKeys, plusieurs cas sont à considérer :
  1. l'arbre A est vide : il n'y a alors rien à faire ;
  2. il n'y a aucun nœud rouge : on ajoute à la liste L la racine de l'arbre A ;
  3. sinon, on doit procéder à deux appels récursifs sur le sous-arbre gauche et le sous-arbre droit. Pour vous aider, on vous fournit une méthode int indexOfClosestAbove(int[] t, int j). Elle prend en entrée un tableau trié t et un entier j et renvoie le plus petit entier k tel que t[k] soit supérieur ou égal à j. Si j est strictement supérieur à toute entrée de t la méthode renvoie la longueur de t.

Le Test1_4.java doit vous renvoyer :
Arbre parfait de hauteur 0 (un unique sommet).
Feuilles rouges: 0. Noeuds verts: []
Pas de feuilles rouges. Noeuds verts: [0]

Arbre parfait de hauteur 4.
Test computeKeys(t, L, A, 0, 2) avec t = [0, 2, 12, 24]: [5, 11, 23]

Feuilles rouges: 0, 2, 12, 24. Noeuds verts: [5, 9, 14, 19, 26, 29]
feuilles rouges: 6, 12, 16, 20, 22. Noeuds verts: [1, 4, 9, 14, 18, 27]
Pas de feuilles rouges. Noeuds verts: [15]
Toutes les feuilles rouges. Noeuds verts: []

Déposez le ficher BST.java   :

Note culturelle (À ne lire que lorsque vous aurez tout fini !)

La méthode implémentée dans la dernière question permet de résoudre un problème de diffusion chiffrée. Par exemple, une chaîne de télévision à péage diffuse un contenu chiffré et les abonnés se voient distribuer un décodeur (en toute rigueur on devrait appeler ça un déchiffreur) qui contient un trousseau de clés de déchiffrement. La chaîne à péage, quant à elle, va diffuser un signal chiffré qui ne pourra être déchiffré que si l'on dispose d'au moins une clé parmi un certain ensemble de clés choisies par la chaîne. La chaîne à péage a entièrement le choix sur le cet ensemble et peut le modifier à tout moment. Viennent alors deux questions :

L'exercice ci-dessus propose une telle solution. On considère un arbre binaire parfait tel qu'on l'a construit en 1.3 et chaque nœud contient un entier qui sera une clé.



Exercice 2 - Calcul du rayon du plus petit disque contenant k points parmi n dans le plan

Le but de cet exercice est de développer un algorithme efficace pour l'approximation du rayon du plus petit disque contenant k points parmi un nuage de n points dans le plan. L'algorithme est probabiliste, basé sur une approche par sous-échantillonnage aléatoire du nuage de points d'entrée P. En gros, on sélectionne chaque point de P avec probabilité 1/k pour le mettre dans un sous-nuage S. Ensuite, pour chaque point s de S on calcule le rayon du plus petit disque centré en s qui contient k points de P. Le résultat est le plus petit des rayons ainsi calculés. Afin de s'assurer que ce rayon r n'est pas trop grand par rapport à l'optimal ropt (qui est inconnu), on utilise une technique de hachage géométrique sur une grille régulière permettant d'obtenir un minorant raisonnable de ropt. En comparant r avec ce minorant on peut déterminer si l'algorithme a réussi à calculer une bonne approximation de ropt. L'analyse théorique est faite dans l'article de Har-Peled et Mazumdar (disponible ici pour votre culture).

Pour simplifier les choses, dans toute la suite on supposera que le nuage de points contient au moins k points.

Pour le codage il faut télécharger tous les fichiers sources et les installer dans le sous-répertoire src/ de votre projet. Les sources contiennent trois classes à compléter au cours de l'exercice :

Les autres classes fournies vous seront utiles à divers endroits de l'exercice. Parmi celles-ci, la classe Point2D stocke un point du nuage et est munie des méthodes suivantes  :

La classe Median permet de calculer en temps O(n) la médiane d'un ensemble de n valeurs réelles. Plus précisément, la classe fournit la méthode suivante :

La classe SmallestkRadiusDet sera utile à la dernière question et sera décrite en temps voulu.

La classe Fenetre permet de gérer les affichages graphiques lors de certains tests. Vous n'avez pas besoin de savoir ni de comprendre ce qui s'y cache pour faire l'exercice.

Pour les tests on fournit un jeu de données, rand_cloud.txt, à installer à la racine de votre projet.

Question 2.1 : Version naïve de l'algorithme

Commençons par coder une version naïve de l'algorithme, qui ne vérifie pas si le rayon calculé est trop grand.

Dans la classe SmallestkRadius, complétez la méthode static double kRadius (Point2D p, Point2D[] pts, int k) qui renvoie le rayon du plus petit disque centré en p et contenant au moins k points du nuage pts. La complexité de cette méthode doit être O(n), où n désigne la taille du tableau pts. Pour cela vous pourrez utiliser la méthode double linearMedian (double t[], int k) de la classe Median, qui calcule la k-ième plus petite valeur contenue dans le tableau t.

Complétez maintenant la méthode static double minkRadiusRand(Point2D[] pts, int k) qui code la version naïve de l'algorithme, à savoir :

Vous pouvez tester votre code à l'aide de la méthode main de la classe Test2_1. Le résultat doit être similaire (mais pas forcément identique, l'algorithme étant probabiliste) à celui-ci :

Test 2.1
0.36961715125479083 <= 1000-radius <= 0.7392343025095817
0.2801695386908175 <= 900-radius <= 0.560339077381635
0.25494159855439674 <= 800-radius <= 0.5098831971087935
0.23755131082624564 <= 700-radius <= 0.4751026216524913
0.21895795492601605 <= 600-radius <= 0.4379159098520321
0.1977384401215657 <= 500-radius <= 0.3954768802431314
0.17627280358206163 <= 400-radius <= 0.35254560716412325
0.1515147936646399 <= 300-radius <= 0.3030295873292798
0.12096665639262914 <= 200-radius <= 0.2419333127852583
0.08279579931286242 <= 100-radius <= 0.16559159862572484
0.0785081468438912 <= 90-radius <= 0.1570162936877824
0.07417250926930676 <= 80-radius <= 0.1483450185386135
0.06708175881470055 <= 70-radius <= 0.1341635176294011
0.06029004620890927 <= 60-radius <= 0.12058009241781854
0.054698243696129585 <= 50-radius <= 0.10939648739225917
0.04679443948456477 <= 40-radius <= 0.09358887896912954
0.04036712169469199 <= 30-radius <= 0.08073424338938398
0.02978147705626883 <= 20-radius <= 0.05956295411253766
0.016585902848547943 <= 10-radius <= 0.03317180569709589
Fin du Test 2.1
Déposez le fichier SmallestkRadius.java   :

Question 2.2 : Grille régulière : les cellules

Nous préparons maintenant le terrain pour l'algorithme complet. La première chose à faire est de créer une structure de grille régulière qui permette l'insertion de points et la récupération des points situés dans la cellule d'un point donné ou dans les cellules avoisinantes. Voir l'image ci-dessous.

La classe GridCell sert à stocker une cellule de la grille. Cette classe contient trois champs  :

On fournit le constructeur suivant, qui prend en argument un point p arbitraire dans la cellule ainsi que le pas R de la grille :

public GridCell(Point2D p, double R) {
	this.R = R;
	this.x = R*Math.floor(p.getX()/R);
	this.y = R*Math.floor(p.getY()/R);
}

Complétez la méthode public boolean equals(Object o) qui renvoie true si deux instances de GridCell ont les mêmes coordonnées x,y (on ignore le pas R).

Complétez aussi la méthode public int hashCode() qui renvoie une valeur de hachage calculée à partir des quantités x/R et y/R.

Complétez enfin la méthode public String toString() qui renvoie une chaîne de caractères contenant les valeurs des coordonnées x,y de la cellule, sous la forme "(x,y)".

Vous pouvez tester votre code à l'aide de la classe Test2_2. Le résultat du test doit être le suivant :

Test 2.2
first cell, 110 points : (0.0,20.0)
second cell, 115 points : (40.0,40.0)
first cell, 35 points : (50.0,10.0)
second cell, 25 points : (10.0,30.0)
Fin du Test 2.2

Par ailleurs, le programme doit ouvrir 2 fenêtres avec les affichages suivants :

    

Déposez le fichier GridCell.java   :

Question 2.3 : Grille régulière : insertion de points

La classe Grid sert à stocker la grille complète, ou plutôt l'ensemble des cellules non vides. Cette classe contient deux champs  :

On fournit le constructeur suivant, qui initialise ces champs :

public Grid(double R) {
	hMap = new HashMap>();
	this.R = R;
}

Complétez la méthode void addPoint(Point2D p) qui insère le point p dans la grille, à savoir :

Vous pourrez pour cela vous servir des méthodes get, put et containsKey de la classe HashMap.

Complétez maintenant la méthode void addPoints(Point2D[] pts) qui insère tous les points du tableau pts dans la grille.

Vous pouvez tester votre code à l'aide de la classe Test2_3. Le programme doit ouvrir 2 fenêtres avec les affichages suivants :

    

Déposez le fichier Grid.java   :

Question 2.4 : Grille régulière : récupération des points dans le voisinage

Complétez dans la classe Grid la méthode Point2D[] getNearbyPoints(GridCell c) qui renvoie un tableau (de la bonne taille) contenant tous les points situés dans la cellule c ou dans l'une de ses 8 cellules adjacentes dans la grille. Pour parcourir les 3x3 cellules situées autour d'une cellule donnée, c'est-à-dire cette cellule et ses huit voisines immédiates, on pourra procéder avec une double boucle for de la forme :

for (int dx = -1; dx <= 1; dx++)
  for (int dy = -1; dy <= 1; dy++)
    ...
et on pourra utiliser la méthode public GridCell shift(int dx, int dy) de la classe GridCell qui renvoie la cellule obtenue par décalage de dx colonnes et de dy lignes.

Vous pouvez tester votre code à l'aide de la classe Test2_4. Le résultat doit être le suivant :

Test 2.4
point (30.5,35.0) has 148 neighbors in the grid
point (50.0,20.0) has 142 neighbors in the grid
point (0.0,0.0) has 69 neighbors in the grid
Fin du Test 2.4

Déposez à nouveau le fichier Grid.java   :

Question 2.5 : Algorithme complet

Nous allons maintenant utiliser la grille pour rendre l'algorithme naïf de la question 2.1 robuste. Pour cela on vous a fourni la classe SmallestkRadiusDet qui contient une méthode static double minkRadiusDet(Point2D[] pts, int k) qui est lente mais calcule à coup sûr une approximation du rayon du plus petit disque contenant k points, avec un facteur au plus deux. L'idée va être de n'appeler cette méthode qu'en cas de nécessité.

Voici la procédure à suivre. L'entrée est constituée d'un tableau Point2D[] pts de taille n et d'un paramètre k :

Complétez dans la classe SmallestkRadius la méthode static double minkRadiusRandDet(Point2D[] pts, int k) qui implémente la procédure décrite ci-dessus.

Vous pouvez tester votre code à l'aide de la classe Test2_5. Le résultat doit être similaire (mais pas forcément identique) à celui-ci :

Test 2.5
0.353984955715939 <= 1000-radius <= 0.707969911431878
0.29061368355245465 <= 900-radius <= 0.5812273671049093
0.2741925285981373 <= 800-radius <= 0.5483850571962746
0.23828076616057375 <= 700-radius <= 0.4765615323211475
0.22047472041719596 <= 600-radius <= 0.4409494408343919
0.19902164365481667 <= 500-radius <= 0.39804328730963334
0.17849877219633523 <= 400-radius <= 0.35699754439267045
0.15192292544725952 <= 300-radius <= 0.30384585089451904
0.12002947586215425 <= 200-radius <= 0.2400589517243085
0.08296151445211748 <= 100-radius <= 0.16592302890423496
0.0794148889239204 <= 90-radius <= 0.1588297778478408
0.07356151775838965 <= 80-radius <= 0.1471230355167793
0.06680793200246078 <= 70-radius <= 0.13361586400492156
0.059980991161789066 <= 60-radius <= 0.11996198232357813
0.05334285291322342 <= 50-radius <= 0.10668570582644683
0.04733755548475306 <= 40-radius <= 0.09467511096950612
0.03807799597008744 <= 30-radius <= 0.07615599194017487
0.028990721593457114 <= 20-radius <= 0.05798144318691423
0.015303048373100295 <= 10-radius <= 0.03060609674620059
End Test 2.5
Déposez à nouveau le fichier SmallestkRadius.java   :

Voici une proposition de correction :