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.

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

 Login :  Mot de passe :

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 Ajouter à cette classe

Déposer votre fichier Personne.java ici.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

1.2 Union et intersection

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

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer



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 al = pl/ql et ar = pr/qr et un entier limit > ql, qr. L'arbre de Stern-Brocot associé à (al, ar, limit) est construit comme ceci :

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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 ]pl/ql, pr/qr[ (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

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

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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/q2.

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.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer




Voici une solution possible : solutions.tar.gz