TD 5 - Pale machine

Votre opinion sur le cours de ce 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 - Configurations de points et distances

On appellera configuration un ensemble {p0,..., pn-1} d'entiers distincts. Le but est d'étudier le lien entre les configurations et l'ensemble des couples (d, m) où:

On ne s'intéresse qu'aux distances de multiplicité non nulle.

Question 1.1 : Mise en route, les classes Configuration et DistanceTree

Les configurations de points sont représentées par la classe Configuration.java qui admet un unique champ : un tableau ordonné d'entiers points.
Vous n'avez pas à modifier cette classe.

    public class Configuration {
	public int[] points;
        ...
    }

Les ensembles de distances vont être représentés par des arbres binaires de recherche appartenant à la classe DistanceTree.java. Chaque nœud d'un tel arbre contient deux entiers : dist qui est une distance et mult qui est sa multiplicité.

    public class DistanceTree {
        private final int dist;
        private final int mult;
        private final DistanceTree left, right;

Important :

Dans la classe DistanceTree.java, compléter les méthodes suivantes :

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

Arbre E : [7, 2] [13, 1] [15, 2] [17, 1]

Arbre F : [5, 1] [6, 5] [7, 2] [13, 1] [15, 2] [17, 1]

Arbre A : [5, 1]

Arbre D : [13, 1] [15, 2] [17, 1]

E a 6 noeuds. F a 12 noeuds. (comptes avec multiplicite).

Déposez le ficher DistanceTree.java  :

Question 1.2 : Construction à partir d'une configuration de points

On cherche à ordonner les distances dans l'ordre croissant. Pour ce faire, on va construire un arbre de distances qui est un arbre binaire de recherche : pour tout nœud,


On suppose maintenant que nos arbres de distance vérifient tous cette propriété.

Le Test1_2.java doit renvoyer exactement :

Arbre associe a [0, 4, 5, 7, 11]:
[1, 1] [2, 1] [3, 1] [4, 2] [5, 1] [6, 1] [7, 2] [11, 1]
-----------------------------------------------------------
Arbre associe a [0, 8, 19, 34, 54, 82]:
[8, 1] [11, 1] [15, 1] [19, 1] [20, 1] [26, 1] [28, 1] [34, 1] [35, 1] [46, 1] [48, 1] [54, 1] [63, 1] [74, 1] [82, 1]

Déposez le fichier DistanceTree.java  :

Question 1.3 : Liste partielle de distances

Compléter la méthode distanceTreeToList(DistanceTree T, int min, int max) qui renvoie une liste chaînée contenant l'ensemble des distances de l'arbre T (rappelons qu'il a une structure d'arbre binaire de recherche) qui appartiennent à l'intervalle fermé [min, max]. Il est demandé :

Indication : Vous pouvez (mais ce n'est absolument pas la seule façon de faire) faire appel à une méthode annexe static void addToList(DistanceTree T, LinkedList L, int min, int max) qui ajoute à la liste L en argument les distances de l'arbre situées entre min et max, dans l'ordre, et apparaissant autant de fois que leur multiplicité.

Le Test1_3.java doit renvoyer :

Sommets de A superieurs a 20 et inferieurs a 10: []

Sommets de B dans l'intervalle [82, 82]: [82]

Sommets de E dans l'intervalle [34, 34]: [34, 34, 34, 34, 34]

Sommets de C dans l'intervalle [5, 10]: []

Sommets de E dans l'intervalle [19, 46]: [19, 20, 26, 28, 28, 34, 34, 34, 34, 34, 35, 46]

Déposez le fichier DistanceTree.java  :

Question 1.4 : Critères simples pour vérifier si un arbre provient d'une configuration

Il n'est pas évident de vérifier qu'un arbre de distances provient bien d'une configuration. On peut toutefois chercher quelques critères nécessaires (mais non suffisants). Pour qu'un arbre de distances provienne d'une configuration de n points :

  1. Il doit avoir n(n-1)/2 sommets comptés avec multiplicité.
  2. Son sommet de distance maximale doit être de multiplicité égale à 1: un seul couple de points réalise la distance maximale, à savoir les points formant les extrémités.
  3. Si l'on note max la distance maximale entre deux points d'une configuration et secondmax la seconde plus grande distance alors la distance max - secondmax est aussi atteinte (voir figure ci-dessous). Dans le cas particulier où max - secondmax = secondmax, la distance secondmax doit être de multiplicité au moins deux.





Pour commencer, compléter la méthode getMaxAndSecondMax(DistanceTree T) qui renvoie un tableau à 4 entrées : [dsecmax, dmax, msecmax, mmax]dmax est la valeur maximale de toutes les distances contenues dans les nœuds de T et dsecmax est la seconde plus grande distance et mmax et msecmax sont leurs multiplicités respectives. Pour ce faire :

Le Test1_4.java doit renvoyer exactement :

Arbre E:
[8, 1] [11, 1] [15, 1] [19, 1] [20, 1] [26, 1] [28, 2] [34, 5] [35, 1] [46, 1] [48, 1] [54, 1] [63, 1] [74, 1] [82, 2]
Maximum: 82, de multiplicite 2. Second maximum: 74 de multiplicite 1.

Arbre A:
[8, 1] [11, 1] [15, 1] [19, 1] [20, 1] [26, 1] [28, 1]
Maximum: 28, de multiplicite 1. Second maximum: 26 de multiplicite 1.

Pour finir, compléter la méthode mightBeFromConfig(DistanceTree T) qui vérifie si les critères a., b., c. ci-dessus sont bien vérifiés. En particulier, si elle renvoie false, on est garanti que l'arbre de distances ne provient pas d'une configuration de points.

Indication : vous pouvez utiliser la méthode fournie static boolean contains(DistanceTree T, int d, int m) qui renvoie true si et seulement si l'arbre T possède un nœud de distance d avec multiplicité supérieure ou égale à m.

Le Test1_5.java doit renvoyer :

Test arbre E: true
Test arbre F: false
Test arbre E modifie: false
Test arbre E modifie: false
Test arbre G: true

Déposez le fichier DistanceTree.java  :


Exercice 2 - Calcul de la plus petite distance entre deux points distincts d'un nuage

Le but de cet exercice est de développer un algorithme efficace pour le calcul de la plus petite distance entre deux points distincts d'un nuage de n points dans le plan. Il existe un algorithme déterministe en temps O(n log n), basé sur une technique de division-fusion. Ici nous allons voir un algorithme probabiliste en temps linéaire, basé sur le hachage géométrique. Le principe de l'algorithme est illustré dans l'image ci-dessous : on décompose d'abord le plan en une grille régulière de pas R, puis on calcule, pour chaque point du nuage, la distance à son plus proche voisin parmi les points du nuage situés dans sa cellule ou dans l'une des 8 cellules avoisinantes. Par exemple, dans l'image ci-dessous, on prend le plus proche voisin du point rouge parmi les points situés dans la zone grise. La sortie de l'algorithme est la plus petite distance ainsi calculée.

Par un habile choix de pas de grille R, guidé par un ordre aléatoire sur les points, on peut s'assurer avec forte probabilité que le vrai plus proche voisin de chaque point du nuage est ainsi trouvé, et que le nombre moyen de voisins considérés pour ce faire est constant, ce qui garantit la correction de l'algorithme et sa complexité linéaire. L'analyse théorique est faite dans l'article de Golin et co-auteurs (disponible ici pour votre culture).

Pour simplifier les choses, dans toute la suite on supposera que le nuage de points contient au moins 2 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 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, france_echantillon.txt, à installer à la racine de votre projet Eclipse.

Question 2.1 : Mise en bouche : un algorithme naïf

Dans la classe SmallestPairwiseDistance, complétez la méthode static double smallestPairwiseDistance(Point2D[] pts) qui renvoie la plus petite distance entre deux points distincts du nuage stocké dans le tableau pts en temps O(n2), où n désigne la taille du tableau.

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

Test 2.1
Calcul de la plus petite distance entre 2 points (version naive): 0.1545621531760279
Fin du Test 2.1
Déposez le fichier SmallestPairwiseDistance.java  :

Question 2.2 : Cellules de la grille

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

On fournit le constructeur ci-dessous, 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, 22 points: (20.0,10.0)
second cell, 20 points: (40.0,40.0)
first cell, 9 points: (20.0,10.0)
second cell, 7 points: (45.0,40.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 : Insertion de points dans la grille

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

On fournit le constructeur suivant, qui initialise ces champs :

public Grid(double R) {
	hMap = new HashMap<GridCell, LinkedList<Point2D>>();
	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, int m) qui insère les m premiers points du tableau pts (indexés de 0 à m-1) dans la grille. Il n'est pas nécessaire de tester si m est négatif ou trop grand par rapport à la taille du tableau.

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




Déposez le fichier Grid.java  :

Question 2.4 : Distance au plus proche voisin dans la grille

Complétez dans la classe Grid la méthode double nearestNeighborDistanceInGrid(Point2D p) qui calcule la distance entre le point p et son plus proche voisin parmi les points du nuage situés dans la même cellule que lui ou dans l'une des 8 cellules avoisinantes. S'il n'y a aucun point dans ces cellules, alors la méthode doit renvoyer la constante Double.MAX_VALUE. Par exemple, dans le cas de la première image de l'énoncé, la méthode doit renvoyer la plus petite distance du point rouge au reste des points dans le carré gris. La complexité de cette méthode doit être de l'ordre du nombre de points dans le carré gris. 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) is 2.254479343330557 away from its neighbors in the grid
point (50.0,20.0) is 1.980046442644984 away from its neighbors in the grid
point (0.0,0.0) is 1.7976931348623157E308 away from its neighbors in the grid
point (17.0,17.0) is 5.0705891396504015 away from its neighbors in the grid
Fin du Test 2.4

Déposez à nouveau le fichier Grid.java  :

Question 2.5 : Algorithme probabiliste linéaire

Nous allons maintenant utiliser la grille pour accélérer la procédure de calcul de la plus petite distance entre deux points distincts du nuage. Voici la procédure, qui prend en entrée un tableau Point2D[] pts de taille n >= 2 :

La partie pré-traitement est gérée par la méthode static void randomPermutation(Point2D[] pts) de la classe SmallestPairwiseDistance, qui implémente l'algorithme de Knuth pour permuter aléatoirement les entrées du tableau pts avec distribution uniforme sur les permutations.

Complétez maintenant dans la classe SmallestPairwiseDistance la méthode static double fastSmallestPairwiseDistance(Point2D[] pts) qui implémente la procédure décrite plus haut et renvoie la plus petite distance entre deux points distincts du nuage stocké dans le tableau pts en temps linéaire en moyenne (il ne sera pas nécessaire de justifier formellement la complexité).

Vous pouvez tester votre code à l'aide de la classe Test2_5. Le résultat doit être le même que celui obtenu par la méthode naïve à la question 1.1, à savoir :

Test 2.5
Calcul de la plus petite distance entre 2 points (version optimisee): 0.1545621531760279
Calcul de la plus petite distance entre 2 points (version naive): 0.1545621531760279
Fin du Test 2.5

Vous pouvez également tester votre code sur un plus gros nuage de points à l'aide de la classe Test2_5bis, afin de constater la différence de complexité entre les deux approches (naïve contre hachage géométrique). Le résultat doit être encore une fois le même pour les deux méthodes. Toutefois, il peut changer d'une exécution à l'autre car le nuage de points est aléatoire. Voici un exemple de résultat :

Test 2.5 bis
Generation de 40000 points aleatoires
Calcul de la plus petite distance entre 2 points (version optimisee): 3.076676956515965E-4
Calcul de la plus petite distance entre 2 points (version naive): 3.076676956515965E-4
Fin du Test 2.5 bis
Déposez à nouveau le fichier SmallestPairwiseDistance.java  :

Voici une proposition de correction :