X Informatique MP 2006

ÉCOLE POLYTECHNIQUE FILIÈRE MP
COEÏFDÛPJINÜNÔROEAÀCÈHQEÜE

CONCOURS D'ADMISSION 2006

COMPOSITION D'INFORMATIQUE

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.

***

Dictionnaires

On attachera une grande importance à la concision, a la clarté, et a la 
précision de la rédaction.

Dans tout ce problème, on s'intéressera a des structures de données pouvant 
représenter un
ensemble de mots, dont l'archétype est un dictionnaire, tel qu'il est utilisé 
dans un correcteur

orthographique.

La première partie de ce problème introduit la structure de données permettant 
de représenter
des mots. Les trois parties suivantes étudient une structure de données 
permettant de représenter
de façon efficace un dictionnaire par partage de préfixes. Cette structure de 
données s'appelle trie
et deux façons de l'implanter sont proposées. La cinquième partie résout la 
recherche du mot le plus
long. La sixième et dernière partie s'intéresse à la recherche d'anagrammes.

Partie I. Mots

Étant donné un alphabet A, contenant un nombre fini de lettres (typiquement 
26), on rappelle
qu'un mot est une suite finie d'éléments de A, et que l'ensemble des mots est 
noté A*.

Pour les réponses aux questions ci--dessous, afin qu'elles ne dépendent pas de 
l'alphabet choisi,
on supposera définies une constante entière N qui est le cardinal de 
l'alphabet, et une fonction
lettre qui prend en entrée un entier 72 compris entre 1 et N et qui écrit la 
z"èmEUR lettre de A. De
plus, lettre(0) écrit un espace, et lettre(--1) fait passer l'impression a la 
ligne suivante.

On définit un type mot permettant de représenter un mot sous la forme d'une 
liste d'entiers
strictement positifs (les indices des lettres du mot). Selon le contexte, le 
parcours de la liste donnera
les lettres du mot de gauche a droite (surnommé motGD) ou bien de droite a 
gauche (surnommé
motDG). Cette seconde option sera choisie lorsque le rajout d'une lettre en fin 
de mot devra se faire
en temps constant.

(* Caml *) {Pascal}

type mot = "Cellule; Cellule = record

type mot == int list ; ; _ _
lettre:1nteger; su1te:mot; end;
En Pascal la liste vide est nil et l'on pourra utiliser la fonction suivante 
pour construire des mots :

function nouveauMot(czinteger; u:mot) : mot;
var vzmot; begin new(v); v".lettre := c; v".suite := u; nouveauMot := v end;

Question 1 Définir une fonction imprimer qui imprime un mot de type motDG et 
passe a la ligne.
Par exemple appeler cette fonction sur la liste <1, 2, 3} avec l'alphabet usuel affiche cba suivi d'un passage a la ligne. (* Caml *) imprimer : mot --> unit

{ Pascal }

procedure imprimer (uzmot);

Question 2 Définir une fonction inverseDe qui transforme un mot de type motDG 
en un type
motGD, et réciproquement. Par exemple (1, 2, 3) devient (3,2,1).

(* Caml *)

inverseDe : mot --> mot

{ Pascal }

function inverseDe (uzmot) : mot;

Partie II. Dictionnaires

Pour simplifier les structures de données, on ajoute à l'alphabet A une lettre 
de terminaison, '
notée $. À tout mot dans A* on associe le mot de A*{$} obtenu en rajoutant un $ 
à la fin du mot;
ainsi, aucun mot du dictionnaire n'est préfixe d'un autre.

On représentera un dictionnaire au moyen de la struc--
ture de données appelée trie, qui est un arbre dont chaque

noeud a un nombre arbitraire de fils, et dont les branches $ . $

sont étiquetées. . , . $ .
Chaque branche de l'arbre est étiquetée par un élément " S . $ .

de A, sauf les branches qui mènent à une feuille et qui sont . . .

étiquetées par $. De plus, les étiquettes des branches is- "' i $ .

sues d'un même noeud sont toutes distinctes. L'ensemble . . . . e . $$ . $

des mots présents dans le dictionnaire est exactement l'en-- S . .

semble des mots qu'on obtient en listant les étiquettes vues ... . $ .

pendant un parcours de la racine jusqu'à une feuille. Voici 9 . $$ .

un exemple de trie, pour le dictionnaire { ame, ames, amen, . n . $ . $ .

amer, ami, amis, amie, amies, ane, anes, annee, annees }. . e . e . S . $ .

(Pour simplifier, les accents sont ignorés).
Plusieurs implantations des tries sont possibles.

Dans cette partie, on choisira d'utiliser une structure tabuléc : Puisqu'on 
peut identifier par leurs
étiquettes les branches issues d'un même noeud, chaque noeud contiendra un 
tableau indicé de 0 a
N, dont la case d'indice fl indique le sous--arbre issu de la branche 
d'étiquette i, ou bien l'arbre vide
si cette branche n'est pas présente.

On définit le type dictTab qui permet de représenter un dictionnaire tabulé.

(* Caml *) {Pascal}
type dictTab = type tabN = array[0..N] of dictTab;
VideT ! dictTab = "NoeudT;
NoeudT of dictTab vect ;; NoeudT = record fils:tabN; end;

En Pascal l'arbre vide est représenté par nil et l'on pourra utiliser le 
constructeur suivant :

function nouveauDictTab(var a: tabN) : dictTab;
var r:dictTab; begin new(r); r".fils := &; nouveauDictTab := r end;

Question 3

a) Décrire la représentation tabulée du dictionnaire vide et celle du 
dictionnaire contenant comme
unique élément le mot vide.

b) Prouver qu'une valeur de type dictTab représente un dictionnaire tabulé si, 
et seulement si,
les feuilles sont exactement les noeuds rattachés à leur père par une branche 
d'étiquette $. Cette
propriété pourra être nommée cohérence d'une valeur de type dictTab.

Question 4 Écrire la fonction imprimerDictTab qui prend en argument un 
dictionnaire tabulé
et écrit successivement tous les mots du dictionnaire (il s'agit bien 
d'afficher a l'écran les mots du

dictionnaire, et non pas d'en retourner la liste).

(* Caml *) {Pascal}
imprimerDictTab : dictTab --> unit procedure imprimerDictTab (dzdictTab);

La principale opération utile pour la correction orthographique est le test 
d'appartenance au
dictionnaire.

Question 5 Écrire la fonction estDansDictTab qui prend en argument un mot de 
type motGD
et un dictionnaire tabulé, et qui détermine si le mot est dans le dictionnaire. 
La réponse doit être
donnée par la valeur de retour de la fonction.

(* Caml *) {Pascal}
estDansDictTab : function estDansDictTab (uzmot, d:dictTab)
mot --> dictTab --> bool : boolean;

Une autre opération importante pour la correction orthographique est 
l'insertion d'un nouveau
mot dans le dictionnaire.

Question 6 Écrire la fonction aj outADictTab qui prend en argument un mot u de 
type motGD
et un dictionnaire tabulé et qui retourne le dictionnaire modifié après 
insertion du mot a.

(* Caml *) {Pascal}
ajoutADietTab : function ajoutADictTab (uzmot, d:dictTab)
mot --> dictTab --> dictTab : dictTab;

Partie III. Dictionnaire binaire

Une autre implantation est la structure binaire. Il s'agit
de faire descendre les étiquettes des branches vers les fils
puis d'utiliser l'isomorphisme entré les arbres dont les noeuds
ont un nombre arbitraire de fils (ordonnés), et les arbres
binaires. L'arbre binaire se construit ainsi : dans la liste des @ ° @
fils d'un noeud, le premier fils devient le fils gauche de son @ 9 © © © @
père, et chacun des fils suivants devient le fils droit de son @ © @ @
frère immédiatement précédent; enfin, on fait disparaître la @
rac1ne. @

On définit le type dictBin qui permet de représenter un dictionnaire binaire.

(* Caml *) {Pascal}
type dictBin = type dictBin = "NoeudB; NoeudB = record
VideB l NoeudB of etiq:integer; filstdictBin;
dictBin * int * dictBin ;; filsD:dictBin; end;

En Pascal l'arbre vide est représenté par nil et l'on pourra utiliser le 
constructeur suivant :

function nouveauDictBin(czinteger; a,b:dictBin) : dictBin;
var r:dictBin; begin new(r); r".etiq = c;
r".filsG := a; r".filsD := b; nouveauDictTab := r end;

Question 7 Expliquer pourquoi on fait disparaître la racine. Décrire la 
représentation binaire du
dictionnaire vide et celle du dictionnaire contenant comme unique élément le 
mot vide.

Question 8 Ecrire la fonction imprimerDictBin qui prend en argument un 
dictionnaire binaire
et écrit successivement tous les mots du dictionnaire.

(* Caml *) {Pascal}

imprimerDictBin : dictBin --> unit procedure imprimerDictBin (dzdictBin);

Pour les deux prochaines questions, deux réponses @
sont possibles, selon qu'on impose ou non que les éti-- @
quettes parcourues en descendant vers les fils droits
soient par ordre croissant des indices des lettres dans
l'alphabet. Il faudra choisir la solution supposant que
les fils droits ne sont pas triés en ordre croissant.

Ainsi le dictionnaire binaire ci--contre peut aussi @
représenter le dictionnaire { ame, ames, amen, amer, @
ami, amis, amie, amies, ane, anes, annee, annees }.

© EUR 9

Question 9 Écrire la fonction estDansDictBin qui prend en argument un mot de 
type motGD et
un dictionnaire binaire et qui détermine si le mot est dans le dictionnaire.

(* Caml *) {Pascal}
estDansDictBin : function estDansDictBin (u:mot, d:dictBin)
mot -> dictBin --> bool : boolean;

Question 10 Écrire la fonction aj outADictBin qui prend en argument un mot de 
type motGD et
un dictionnaire binaire et qui modifie le dictionnaire pour y ajouter le mot.

(* Caml *) {Pascal}

ajoutADictBin : function ajoutADictBin (uzmot; d:dictBin)
mot --> dictBin -> dictBin : dictBin;

Partie IV. Comparaison des coûts; conversion de représentations

On se place dans le cas où le dictionnaire manipulé contient n5 mots de 
longueur moyenne n.

Question 11

a) Donner un encadrement du nombre de sommets S en fonction de n et N. Calculer 
en fonction
de S le coût mémoire de chacune des deux représentations, et comparer.

b) Évaluer et comparer la complexité en temps du test d'appartenance et de 
l'ajout d'un mot
de longueur EUR , pour chacune des deux représentations.

Question 12 Écrire la fonction tabVersBin qui prend en argument un dictionnaire 
tabulé et
retourne le dictionnaire binaire équivalent.

(* Caml *)
tabVersBin : dictTab --> dictBin

{ Pascal }
function tabVersBin (dzdictTab) : dictBin;

Question 13 Écrire la fonction binVersTab qui prend en argument un dictionnaire 
binaire et
retourne le dictionnaire tabulé équivalent.

(* Caml *)
binVersTab : dictBin --> dictTab

{ Pascal }
function binVersTab (d:dictBin) : dictTab;

Partie V. Le mot le plus long

Il s'agit, étant donné un chevalet rempli de lettres, de trouver tous les mots 
du dictionnaire qu'on
peut composer à l'aide de ces lettres, et en particulier le(s) plus long(s) 
d'entre eux. Le dictionnaire
est représenté par un trie. Le choix de l'une des deux implantations ci--dessus 
est libre.

Question 14 Écrire la fonction imprimerMotsDans qui prend en argument un mot et 
un diction-
naire et qui retourne la liste des mots de ce dictionnaire composés de lettres 
du mot fourni en entrée.
Une même lettre pourra être utilisée au plus le nombre de fois où elle apparaît 
dans le mot initial.

Estimer la complexité de cette fonction.
(* Caml *) {Pascal}

imprimerMotsDans :

_ _ procedure imprimerMotsDans (dzdictXXX, u:mot);
d1ctXXX --> mot --> un1t

Partie VI. Anagrammes

Un mot est un anagramme d'un mot a donné s'il est composé de mots du 
dictionnaire et si cha--
cune de ses lettres apparaît le même nombre de fois que dans u. Par exemple si
a : cceeeehillnoopqtuy, le mot a a pour anagrammes, entre autres, 
ecole...polytechnique,
hellenique...type...coco ou encore pole...cyclone...ethique. Les mots du 
dictionnaire sont sépa--
rés dans un même anagramme par le caractère ... imprimé en appelant la fonction 
lettre avec le
paramètre O.

Question 15 Ecrire la fonction imprimerAnagrammes qui prend en argument un mot 
et un dic--
tionnaire et qui imprime la liste des anagrammes de ce mot composés de mots du 
dictionnaire.
Estimer la complexité de cette fonction.

(* Caml *) {Pascal}
imprimerAnagrammes : procedure imprimerAnagrammes (d:dictXXX;
dictXXX --> mot --> unit u:mot);
* >|<