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