Pale machine du mardi 15 octobre 2019

There is an English version of this exam. But you must use this page to submit your files.

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

Les tests fournis ne sont pas parfaits. Un programme validé par les tests n'est pas nécessairement juste !

Vous avez accès à la documentation de Java.

Pour commencer, créer un projet Java PaleMachine, télécharger les sources PaleMachine.tar.gz et les décompresser dans le dossier src de votre projet.

Exercice 1 : Union et intersection

1.1 Classe `Personne`

Créer une classe Personne décrivant une personne avec trois champs

prenom de type String ;
nom de type String ;
age de type int.

Ajouter à cette classe

un constructeur Personne(String prenom, String nom, int age) ;
une méthode public boolean equals(Object obj) (deux personnes sont supposées être la même si elles ont les mêmes nom, prénom et âge) ;
une méthode public int hashCode() (Indication : on pourra utiliser la méthode hashCode de la classe String) ;
une méthode public String toString() représentant une personne sous le format : [ Jean Dupont, 38 ans ].

Déposer votre fichier Personne.java ici.

1.2 Union et intersection

Compléter la classe UnionIntersection avec les deux méthodes suivantes.

Une méthode static LinkedList<Personne> union(LinkedList<Personne> l1, LinkedList<Personne> l2) renvoyant une nouvelle liste contenant la réunion des personnes appartenant aux listes l1 et l2 et telle que
1. Votre fonction doit utiliser HashSet ;
2. La liste renvoyée doit être sans doublons (Attention : les listes l1 et l2 peuvent contenir des doublons) ;
3. L'ordre des éléments dans cette liste n'a pas d'importance ;
4. La complexité de votre algorithme doit être en O(l1.size() + l2.size()).

Une méthode static LinkedList<Personne> intersection(LinkedList<Personne> l1, LinkedList<Personne> l2) qui renvoie une nouvelle liste contenant l'intersection des personnes appartenant aux listes l1 et l2. Cette méthode doit aussi vérifier les contraintes 1, 2, 3, 4 de la méthode union.

Vous avez accès à la documentation de LinkedList et HashSet.

Vous pouvez tester votre code en exécutant Test1.java. Déposer ensuite votre fichier UnionIntersection.java ici.

Exercice 2 : L'arbre de Stern-Brocot

Le but de cet exercice est de construire et étudier des arbres binaires dont les nœuds contiennent des nombres rationnels et dont les propriétés remarquables seront expliquées au fil des questions. Comme dans l'amphi/TD 5, l'arbre vide est représenté par null.

2.1 Construction de l'arbre

On se donne deux nombres rationnels a_l = p_l/q_l et a_r = p_r/q_r et un entier limit > q_l, q_r. L'arbre de Stern-Brocot associé à (a_l, a_r, limit) est construit comme ceci :

Si q_l + q_r > limit, il est vide ;
Sinon, sa racine contient le nombre rationnel x = (p_l + p_r) / (q_l + q_r), son fils gauche est l'arbre de Stern-Brocot associé à (a_l, x, limit) et son fils droit est l'arbre de Stern- Brocot associé à (x, a_r, limit).

Dans SternBrocot.java, compléter la méthode static SternBrocot build(pl, ql, pr, qr, limit) qui renvoie l'arbre de Stern-Brocot associé à (pl/ql, pr/qr, limit). On pourra supposer que pl/ql < pr/qr, que ces deux fractions sont irréductibles (numérateur et dénominateur premiers entre eux) et que pl, ql, pr, qr sont positifs.

Figure 1. L'arbre de Stern-Brocot associé à (0/1, 1/1, 7) que l'on obtient en appelant la méthode build(0,1,1,1,7). Les valeurs 0/1 et 1/1 et les traits pointillés illustrent que tous les rationnels de l'arbre appartiennent à l'intervalle ]0/1,1/1[. Pour mieux visualiser l'arbre, cliquer ici.

Tester votre programme avec Test21.java. Déposer ensuite votre fichier SternBrocot.java ici.

2.2 Taille

Compléter la méthode static int size(SternBrocot t) qui renvoie le nombre de nœuds de l'arbre t.

Tester votre programme avec Test22.java. Déposer ensuite votre fichier SternBrocot.java ici.

2.3 Les arbres de Stern-Brocot sont des arbres binaires de recherche

Les arbres de Stern-Brocot ont, par construction, une structure d'arbres binaires de recherche dont tous les nœuds sont dans l'intervalle ]p_l/q_l, p_r/q_r[ (on admettra cet énoncé). Pour le vérifier, compléter la méthode static boolean isBST(SternBrocot t, int pl, int ql, int pr, int qr) qui renvoie true si et seulement si

l'arbre t est bien un arbre binaire de recherche ;
tous ses nœuds sont dans ]p_l/q_l, p_r/q_r[.

Tester votre programme avec Test23.java. Déposer ensuite votre fichier SternBrocot.java ici.

2.4 Énumeration

On souhaite énumérer les nœuds d'un arbre de Stern-Brocot dans l'ordre croissant, comme une LinkedList<String> l dont les éléments sont des chaînes de caractères de la forme "p/q".

Compléter la méthode treeToList. On pourra utiliser une méthode annexe static void treeToList(SternBrocot t, LinkedList<String> l).

Tester votre code avec Test24.java. Déposer ensuite votre fichier SternBrocot.java ici.

2.5 Chemin dans l'arbre

On considère l'arbre de Stern-Brocot associé à (0/1, 1/1, limit) pour un certain entier limit. L'arbre de Stern-Brocot étant un arbre binaire de recherche, on peut y rechercher efficacement un nombre rationnel p/q donné, en allant soit à gauche, soit à droite, et en s'arrêtant lorsque le nœud contient p/q (succès) ou lorsque l'arbre est vide (échec). On peut représenter le chemin parcouru dans l'arbre par une telle recherche comme une séquence de caractères L (on est allé à gauche) ou R (on est allé à droite). Avec l'arbre de la Figure 1, on associe à 1/3 la séquence L (succès), à 2/7 la séquence LLR (succès) et à 5/14 la séquence LLRR (échec).

Compléter la méthode String path(SternBrocot t, int p, int q) qui renvoie la chaîne de caractères correspondant à la recherche du rationnel p/q. La chaîne se terminera par ! si p/q figure dans t et par ? sinon. Ainsi, pour l'arbre t de la Figure 1, path(t, 2, 7) renvoie la chaîne "LLR!" et path(t, 5, 14) renvoie la chaîne "LLRR?" (car 2/7 < 5/14 < 1/3).

Tester votre code avec Test25.java. Déposer ensuite votre fichier SternBrocot.java ici.

2.6 De la séquence au nombre rationnel

Compléter la méthode fromPath qui effectue l'opération inverse : partant d'une chaîne de caractères L ou R, elle renvoie le nombre rationnel correspondant dans un arbre de Stern-Brocot associé à (0/1, 1/1, limit) pour une valeur de limit assez grande pour que ce chemin aboutisse à un rationnel.

Attention. On demande un programme calculant ce nombre sans construire l'arbre.

Le rationnel est renvoyé sous la forme d'un tableau de deux entiers. Ainsi, fromPath("RLL") renvoie le tableau {4,7}. On rappelle que la syntaxe pour la création d'un tableau à deux éléments a et b est new int[]{a,b}.

Testez votre programme avec Test26.java Déposer ensuite SternBrocot.java ici.

2.7 Approximation rationnelle

Compléter la méthode lowApprox(t, x) qui prend en entrée un arbre de Stern-Brocot t et un réel x et renvoie le plus grand élément de t qui soit inférieur ou égal à x s'il existe et null sinon. Si le résultat n'est pas null on renvoie un nombre rationnel sous la forme d'un tableau de deux entiers {numérateur, dénominateur}.

Tester votre programme avec Test27.java. Déposer ensuite SternBrocot.java ici.

2.8 Bonnes approximation rationnelles

De manière similaire, écrire une méthode static int[] upApprox(SternBrocot t, double x) qui renvoie le plus petit élément de t supérieur ou égal à x s'il existe et null sinon.

Soit x un réel. On dit que p/q est une bonne approximation rationnelle de x si p, q sont premiers entre eux et

|x - p/q| < 1/q².
Dans SternBrocot.java, ajouter une méthode public static void main(String[] args), dans laquelle on construit l'arbre de Stern-Brocot avec limit = 100, puis on teste, pour 1000 réels x ∈ [0.01, 0.99[ tirés au hasard (utiliser la méthode Math.random()), qu'au moins une des deux approximations données par lowApprox et upApprox est une bonne approximation.

Déposer SternBrocot.java ici.

Voici une solution possible : solutions.tar.gz

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