X Informatique MP 2006

Thème de l'épreuve Dictionnaires
Principaux outils utilisés parcours d'arbre, programmation récursive

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


É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);
* >|<

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP 2006 -- Corrigé
Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par
Sattisvar Tandabany (ENS Lyon) et Samuel Mimram (ENS Lyon).

L'épreuve d'informatique de Polytechnique comporte traditionnellement beaucoup 
de questions consistant à écrire du code. Ce sujet est au-dessus de la moyenne :
une seule question est purement théorique ! Il faut tout de même estimer 
parfois la
complexité des fonctions et deux questions comportent une partie théorique.
Ce problème porte sur deux représentations possibles d'un dictionnaire (un 
ensemble de mots) par un arbre. Les connaissances de cours nécessaires sont le 
parcours
d'arbre et la programmation récursive, mais surtout une expérience de la 
programmation en Caml.
La difficulté est progressive tout au long du sujet si l'on excepte la question 
théorique, dont la complexité perçue peut être très variable. Elle se révèle ne 
pas avoir
d'influence sur la suite. Il ne faut donc pas hésiter à laisser de côté cette 
question
après quelques minutes de recherche infructueuse lors d'un écrit de concours 
(plus
longtemps lors d'un travail personnel...). Toutes les parties concernent le 
même problème, elles ne sont donc pas indépendantes, mais les questions ne 
réutilisent pas les
fonctions écrites dans les questions précédentes (sauf celles de la première 
partie) ;
il s'agit plutôt de les adapter.
· La partie I fait écrire deux fonctions auxiliaires élémentaires.
· La partie II traite la première représentation étudiée, la partie III de la 
seconde.
· La partie IV compare les deux et demande de convertir l'une en l'autre.
· Les parties V et VI contiennent chacune une question et cherchent à départager
les candidats les plus rapides par des fonctions plus subtiles, quoique tout à 
fait
accessibles.
Ce sujet est une bonne préparation aux concours à condition de tester ses 
fonctions, car un problème de taille de tableau est vite arrivé. En effet, 
c'est principalement l'algorithme qui est pris en compte par le correcteur, 
mais trop d'erreurs de
syntaxe peuvent venir à bout de sa patience.
La structure de données nommée trie introduite dans ce sujet, et ses 
améliorations
(non étudiées ici), sont utilisées dans des applications réelles, notamment 
dans le
cadre des correcteurs orthographiques. On retiendra de ce sujet les techniques 
et le
style de programmation, ainsi que des manipulations typiques sur les arbres.

Indications
Première partie
1 Utiliser la fonction rev.
2 Créer une variable resultat de type int list ref et lui ajouter les éléments
de la liste un à un.
Deuxième partie
3.b Il s'agit presque de paraphraser l'énoncé.
4 Parcourir l'arbre en se souvenant (au moyen d'un argument donné à une fonction
récursive auxiliaire) des lettres lues pour atteindre le noeud courant.
5 Lire le mot lettre par lettre en suivant à chaque fois la branche étiquetée 
par
cette lettre. Ne pas oublier le cas où cette branche n'existe pas.
6 Même indication. Si on tente de suivre une branche qui n'existe pas, on la 
crée.
Troisième partie
7 Si l'on ne supprimait pas la racine, quelle serait son étiquette ? son fils 
gauche ?
son fils droit ? Pour la seconde partie, appliquer l'isomorphisme aux valeurs de
la question 3.a.
8 Descendre de fils droit en fils droit revient à parcourir le tableau des fils 
de la représentation tabulée. Mais on n'est pas obligé de le parcourir 
explicitement,
on peut faire simplement un appel récursif sur le fils gauche puis sur le fils 
droit
avec des arguments différents. Adapter la fonction de la question 4.
9 Même indication (en adaptant cette fois la fonction de la question 5).
10 Encore une adaptation, cette fois de la question 6. N'ajouter une branche que
s'il n'y a pas de fils droit. À chaque étape, faire un appel récursif sur le 
bon fils
et renvoyer un nouveau noeud construit avec le résultat de l'appel récursif.
Quatrième partie
11.a Ne pas oublier que le nombre de mots et la longueur moyenne sont fixés. 
Minorer
simplement le nombre de noeuds par le nombre de feuilles. Majorer le nombre
de noeuds par la somme des longueurs de mots.
12 Pour transformer un tableau de fils en une suite de fils droits, commencer 
par
le dernier, puis créer le noeud correspondant à l'avant-dernier qui a pour père
le dernier, etc. Faire un cas particulier pour la case 0.
13 Descendre de fils droit en fils droit pour recréer le tableau des fils à 
l'aide d'une
fonction auxiliaire. Il s'agit toujours d'une fonction récursive.
Cinquième partie
14 Compter d'abord le nombre d'occurrences de chaque lettre dans le mot donné.
Sixième partie
15 Adapter la fonction précédente. Vérifier que toutes les lettres sont 
utilisées. Introduire un espace revient à faire un appel récursif avec le 
dictionnaire d'origine.
Pour estimer la complexité (identique sur les deux représentations), imaginer le
parcours dans la représentation tabulée.

L'usage et les recommandations des concepteurs du langage demandent,
dans les noms des valeurs Caml, de séparer les mots par des « _ » et non par
des majuscules (c'est même une erreur de syntaxe en OCaml de commencer
le nom d'une fonction ou d'une variable par une majuscule, ce qui est réservé 
(et obligatoire) à quelques catégories de noms, dont les constructeurs
des types somme et les exceptions).
Les fonctions de ce corrigé que nous avons introduites suivent cette règle.
Cependant, pour ne pas agacer le correcteur, il est déconseillé de modifier
le nom des fonctions introduites dans l'énoncé.

I. Mots
1 Il suffit de retourner la liste puis d'imprimer les lettres une à une.
let imprimer mot =
do_list lettre (rev mot);
lettre (-1);;
Rappelons que do_list f [a1; ...; an] applique la fonction f à tous les
éléments de la liste, cet appel signifie donc f a1; f a2; ...; f an.
do_list est ainsi du type ('a -> unit) -> 'a list -> unit.
On peut aussi ne pas utiliser la fonction rev et écrire la fonction récursive
suivante :
let imprimer mot =
let rec imprimer_lettres = function
| [] -> ()
| c :: suite ->
imprimer_lettres suite;
lettre c in
imprimer_lettres mot; lettre (-1);;
2 On crée une variable resultat initialisée à la liste vide puis, en lisant le 
mot
donné de gauche à droite, on ajoute une à une ses lettres en tête de resultat.
let inverseDe mot =
let resultat = ref [] in
do_list (fun i -> resultat := i :: !resultat) mot;
!resultat;;
La fonction suivante, bien que naturelle, a une complexité O(n2 ) (où n est la
longueur de la liste) et est donc à proscrire :
let rec inverseDe = function
| [] -> []
| a::q -> (inverseDe q) @ [a];;
On évite d'utiliser la fonction rev puisque la question consiste justement à
écrire une telle fonction.

On peut aussi utiliser la puissante fonction it_list :
let inverseDe = it_list (fun accu i -> i::accu) [];;
Quelques explications s'imposent :
· it_list f a [b1; ...; bn] est une écriture concise signifiant
f (... (f (f a b1) b2) ...) bn.
En d'autres termes, la fonction it_list commence avec la valeur a
et calcule f a b1 pour former la valeur a1. Elle calcule alors f a1 b2
et obtient a2. Elle itère le processus jusqu'à bn et obtient an, qu'elle
renvoie. (Ici ai est le mot, de type int list, formé des i dernières
lettres du résultat.)
· Son type est donc ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a.
· it_list demande trois arguments et n'en reçoit ici que deux, c'est donc
une application partielle. Cette fonction inverseDe est équivalente à
la suivante, où l'on a explicité le troisième argument :
let inverseDe mot =
it_list (fun accu i -> i::accu) [] mot;;

II. dictionnaires
3.a Il y a N + 1 cases dans chaque tableau, les cases 1 à N représentent les 
branches
étiquetées par les N lettres de A, on décide donc que la case d'indice 0 
représente
la branche d'étiquette $.
L'énoncé indique que chaque noeud contient un tableau de taille N + 1. Le 
dictionnaire vide est donc un NoeudT d'un tableau dont toutes les cases sont 
vides (aucune
branche ne part de la racine) et le dictionnaire contenant seulement le mot vide
(noté ) est identique, mais avec la case 0 non vide. Soit, si l'on choisit N = 
3 :
let dict_vide_tab =
NoeudT [| VideT; VideT; VideT; VideT |];;
let dict_epsilon_tab =
NoeudT [| dict_vide_tab; VideT; VideT; VideT |];;
On ne se servira jamais du tableau d'un noeud atteint par une branche 
d'étiquette $ (car aucune lettre ne peut suivre $), on pourrait donc utiliser 
le tableau vide pour ces noeuds :
let dict_epsilon_tab =
NoeudT [| NoeudT [||]; VideT; VideT; VideT |];;
Mais cela compliquerait le code de certaines fonctions, comme par exemple
à la question 12.
3.b Considérons un arbre représentant un dictionnaire tabulé. Les mots qu'il 
représente sont ceux obtenus en listant les étiquettes vues pendant un parcours 
de la racine jusqu'à une feuille, or les dernières lettres de ces mots sont des 
$, donc toutes les
feuilles sont rattachées à leur père par une branche d'étiquette $. De plus, 
aucun mot