Pale Machine
Jean-Christophe Filliâtre

Introduction

L'examen contient deux exercices indépendants.

Pour chaque exercice, un fichier contenant deux classes est fourni. Une classe doit être complétée ; l'autre est fournie dans le but de tester votre code.

Vous pouvez déposer à n'importe quel moment. Le dépôt se trouve à la fin de chaque exercice. Seul le dernier dépôt de chaque exercice sera corrigé.

Note : Vous n'avez pas accès au réseau mais vous pouvez néanmoins consulter la documentation Java en local.

1. Tableaux redimensionnables

On s'intéresse ici à une structure de données de tableaux dont la taille peut être modifiée dynamiquement. Pour simplifier, on considère ici uniquement des tableaux d'entiers.

Un fichier Ex1.java est fourni. Il contient deux classes.

La classe ResizeableArray contient les méthodes que vous devez compléter.

La classe Ex1 contient le code pour effectuer les tests. Elle ne doit pas être modifiée. C'est la méthode main de cette classe qu'il faudra exécuter pour tester vos réponses.

Principe

Un tableau redimensionnable r est représenté par un tableau usuel (champ r.data) et par le nombre d'éléments disponibles dans ce tableau (champ r.length). On ne peut lire et écrire que dans la portion située entre les indices 0 et r.length-1. Les éléments situés à partir de l'indice r.length ne sont là qu'en réserve. On a donc la situation suivante :
          +--------------------------+--------------------------+
   r.data |    éléments disponibles  |   éléments de réserve    |
          +--------------------------+--------------------------+
          <-------- r.length -------->
          <------------------ r.data.length -------------------->
Dans tout ce qui suit, on maintiendra l'invariant suivant pour tout tableau redimensionnable r : 0 <= r.length <= r.data.length.

Pour éviter toute confusion, on parlera par la suite de taille d'un tableau redimensionnable r pour désigner r.length et de longueur d'un tableau usuel a (de type int[]) pour désigner a.length. Dans l'illustration ci-dessus, on a donc un tableau redimensionnable de taille r.length utilisant un tableau de longueur r.data.length.

Question 1.1 : opérations élémentaires

Écrire le code du constructeur ResizeableArray, qui prend en argument la taille initiale du tableau. Les éléments du tableau doivent être initialisés avec la valeur 0.

Compléter le code des méthodes get et set, qui permettent respectivement d'accéder à et de modifier un élément du tableau.

Tester avec la classe Ex1 fournie.

Question 1.2 : redimensionnement

Écrire le code de la méthode resize(int len) qui permet de modifier la taille d'un tableau redimensionnable. On adoptera la stratégie suivante :

Tester avec la classe Ex1 fournie.

Question 1.3 : concaténation

Écrire le code de la méthode append(int a[]) qui concatène les éléments du tableau a à la fin du tableau redimensionnable this. En particulier, la taille de this est augmentée de la longueur de a.

Tester avec la classe Ex1 fournie.

Déposer le fichier Ex1.java :

2. Le mode T9

Les vieux téléphones portables proposent une méthode pour saisir des textes sur un clavier numérique, appelée mode T9 : au lieu de taper plusieurs fois sur une touche pour faire défiler les lettres, une seule frappe suffit et le téléphone propose de lui-même les mots qui correspondent à la séquence de touches qui vient d'être tapée, à partir d'un dictionnaire qu'il a en mémoire.

Par exemple, en tapant successivement les touches 2, 6, 6, 5, 6, 8 et 7 vous obtenez le mot bonjour. Il est possible qu'une suite de touches corresponde à plusieurs mots. Ainsi, la suite 5, 6, 4 et 3 correspond aux mots joie et loge et la suite 2, 5, 3 et 3 à clef et bled.

Le but de cet exercice est de programmer une solution efficace pour la recherche des mots du dictionnaire qui correspondent à une séquence de touches.

Un fichier Ex2.java est fourni. Il contient deux classes. La classe T9 contient les méthodes que vous devez compléter. La classe Ex2 contient le code pour effectuer les tests. Elle ne doit pas être modifiée. C'est la méthode main de cette classe qu'il faudra exécuter pour tester vos réponses.

Principe

Nous allons représenter le dictionnaire par un arbre digital (en anglais trie) c'est-à-dire un arbre où chaque branche est étiquetée par le numéro d'une touche du téléphone et chaque nœud par les mots du dictionnaire correspondant à la séquence des touches menant de la racine de l'arbre à ce nœud.

Par exemple, l'arbre que l'on obtient pour le petit dictionnaire composé des mots {id, if, in, get, to, void, unit} est le suivant :

                        {}
                       /  \
		     4/    \8
		     /      \
		   {}        {}
		  /  \        \
		6/    \3       \6
		/      \        \
	      {in}   {id,if}    {to}
	                |        |
			|8       |4
			|        |
		      {get}     { }
		               /   \
			     3/     \8
			     /       \
			  {void}    {unit}
Un nœud de l'arbre est réalisé par un objet de la classe T9 fournie. Un tel objet contient d'une part un ensemble de mots (champ words) et d'autre part un tableau de taille 10 (champ branches). Les éléments d'indices 0 et 1 de ce tableau ne seront jamais utilisées (seules les touches 2 à 9 du téléphone correspondent à des lettres).

2.1. Constructeur

Écrire le code du constructeur de la classe T9, qui renvoie un dictionnaire vide. Les branches seront initialisées à null.

Tester avec la classe Ex2 fournie.

2.2. Recherche

Écrire le code de la méthode find(int keys[]) qui renvoie l'ensemble des mots situés dans le nœud correspondant à la séquence de touches donnée par le tableau keys. Si aucun mot ne correspond à la séquence de touches, cette méthode doit renvoyer un TreeSet vide (mais pas null).

Indication : On pourra écrire une méthode auxiliaire récursive findRec(int keys[], int i) qui considère la séquence keys[i..], c'est-à-dire à partir de l'indice i.

Tester avec la classe Ex2 fournie.

2.3. Ajout

Écrire le code de la méthode add(String word) qui ajoute le mot word dans le dictionnaire. Une fois que le nœud correspondant au mot word a été trouvé, on ajoute le mot avec la méthode add de TreeSet. On ne se pose pas la question de savoir si le mot est déjà présent dans l'ensemble.

Une méthode key est fournie, qui donne le chiffre correspondant à chaque caractère.

Indication : On pourra écrire une méthode auxiliaire récursive addRec(String word, int i) qui considère les lettres du mot word à partir de l'indice i.

Tester avec la classe Ex2 fournie.

2.4. Suppression

Écrire le code de la méthode remove(String word) qui supprime le mot word de l'arbre this s'il est présent et ne fait rien sinon. On ajoute la contrainte suivante : la méthode remove ne doit pas laisser de sous-arbre interne vide, c'est-à-dire de sous-arbre non null mais ne contenant aucun mot.

Indications :

Tester avec la classe Ex2 fournie.

2.5. Affichage de l'arbre

Dans cette dernière question, on se propose d'écrire une méthode prettyPrint() qui affiche un arbre T9 de façon arborescente, de la manière suivante (il s'agit ici de l'arbre donné plus haut en exemple) :
[]
+-4-[]
|   +-3-[id, if]
|   |   +-8-[get]
|   +-6-[in]
+-8-[]
    +-6-[to]
        +-4-[]
            +-3-[void]
            +-8-[unit]
Plus précisément : pour afficher un nœud t, on commence par afficher sa liste de mots (c'est-à-dire la chaîne t.words.toString()), suivie d'un retour chariot, puis toutes ses branches non null, la i-ième branche étant précédée de +-i- sur sa première ligne puis, sur les lignes suivantes, soit d'une barre verticale et de trois espaces s'il ne s'agit pas de la dernière branche non nulle de t, soit de quatre espaces sinon.

Écrire le code de la méthode prettyPrint(). Attention : les retours à la ligne sont importants (les tests fournis les prennent en compte).

Tester avec la classe Ex2 fournie.

Déposer le fichier Ex2.java :