Mines Informatique MP 2009

Thème de l'épreuve Étude d'une fonction sur les langages et arbres enracinés non ordonnés
Principaux outils utilisés langages rationnels, automates finis, parcours d'arbre, listes triées
Mots clefs arbres de Prüfer

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


Épreuve deinformatique 2009 A 2009 INFO. MP ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE LeAÉRONAUTIQUE ET DE LeESPACE, DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY, DES TÉLÉCOMMUNICATIONS DE BRETAGNE, ÉCOLE POLYTECHNIQUE (FILIÈRE TSI) CONCOURS DeADMISSION 2009 ÉPREUVE D'INFORMATIQUE Filière MP Durée de l'épreuve : 3 heures. L'usage de calculettes est autorisé. L'utilisation d'un ordinateur est interdite. Sujet mis à disposition des concours : ENSAE ParisTech, TELECOM SudParis (ex INT), TPE-EIVP Les candidats sunt priés de mentiunner de façun apparente sur la première page de la cupie : INFORMATIQUE - MP L'énuncé de cette épreuve cumpurte 8 pages. Recommandations aux candidats · Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre. · Tout résultat fourni dans l'énoncé peut être utilisé pour les questions ultérieures même s'il n'a pas été démontré. · Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents même lorsque l'énoncé ne le demande pas explicitement. Composition de l'épreuve Leépreuve comporte deux problèmes indépendants : · un problème sur les automates, pages 2 et 3 ; · un problème dealgorithmique, pages 4 à 8. Préliminaire pour l'ensemble de l'épreuve concernant la programmation Il faudra écrire des fonctions ou des procédures à leaide deun langage de programmation qui pourra être soit Caml, soit Pascal, tout autre langage étant exclu. Indiquer en début d'épreuve le langage de programmation choisi ; il est interdit de modifier ce choix au cours de l'épreuve. Certaines questions des problèmes sont formulées différemment selon le langage de programmation ; cela est indiqué chaque fois que cela est nécessaire. Lorsque le candidat écrira une fonction ou une procédure, il pourra faire appel à une autre fonction ou procédure définie dans les questions précédentes. Enfin, si les paramètres deune fonction ou deune procédure à écrire sont supposés vérifier certaines hypothèses, il ne sera pas utile dans leécriture de cette fonction ou de cette procédure de tester si les hypothèses sont bien vérifiées. Dans les énoncés des problèmes, un même identificateur écrit dans deux polices de caractères différentes désignera la même entité mais du point de vue mathématique pour une police (en italique ; par exemple a) et du point de vue informatique pour leautre (en romain ; par exemple a). Page 1 sur 8 Épreuve deinformatique 2009 Problème 1. Automates Les quelques rappels de définitions qui suivent permettent de fixer la terminologie et les notations. Un alphabet est un ensemble fini deéléments appelés lettres. Un mot sur est une suite finie de lettres de ; la longueur deun mot est le nombre de lettres le composant ; le mot de longueur nulle est noté . On désigne par * leensemble des mots sur , y compris le mot . Un langage sur est une partie de *. Un autumate fini A est décrit par une structure < , Q, T, I, F>, où : · est un alphabet ; · Q est un ensemble fini et non vide appelé ensemble des états de A ; · T Q × × Q est appelé leensemble des transitiuns ; étant donnée une transition (p, x, q) T, on x q ; dit queelle est deurigine p, deextrémité q et queelle est deétiquette x ; on pourra la noter p · I Q est appelé ensemble des états initiaux de A ; · F Q est appelé ensemble des états finals de A. Dans ce problème, on considérera uniquement des automates ayant un seul état initial, noté q0. x x x 1 2 k Un chemin de A est une suite de transitions de la forme p0 p1 p2 ... pk. On dit alors que ce chemin va de p0 à pk. Dans un automate fini, un état q est dit utile seil existe à la fois un chemin de leétat initial q0 à q et un chemin de q à un état final. On rappelle le théorème de Kleene : un langage sur un alphabet est rationnel si et seulement seil existe un automate fini dealphabet qui le reconnaît. On ne considère dans tout ce problème que l'alphabet = {a, b}. Tous les mots et langages considérés seront définis sur cet alphabet. On définit une application de dans de la façon suivante : · () = ; · si un mot u de longueur 2k > 0 seécrit u = u1u2 ... u2k­1u2k où, pour i {1, 2, ..., 2k}, ui appartient à , alors (u) = u2u1u4u3 ... u2ku2k­1 ; · si un mot u de longueur 2k + 1 > 0 seécrit u = u1u2 ... u2ku2k+1 où, pour i {1, 2, ..., 2k, 2k + 1}, ui appartient à , alors (u) = u2u1u4u3 ... u2ku2k­1u2k+1. La fonction agit donc en échangeant chaque lettre deindice pair avec la lettre (deindice impair) qui la précède immédiatement. Ainsi, (a) = a, (abba) = baab, (aabab) = aaabb. 1 - Soit u un mot dans *. Établir une condition nécessaire et suffisante pour que, quel que soit le mot v dans *, leégalité (uv) = (u)(v) soit vérifiée. On note L1 leensemble des mots u tels que (u) u. 2 - Caractériser les mots de L1. 3 - Proposer, preuve à leappui, une expression rationnelle décrivant L1 ; on privilégiera une expression rationnelle simple. 4 - Dessiner un automate fini reconnaissant L1 ; on privilégiera un automate ayant peu deétats. On note L2 le langage décrit par leexpression rationnelle a*b*. 5 - Proposer une expression rationnelle décrivant (L2). Justifier brièvement la réponse. 6 - Dessiner un automate fini reconnaissant (L2). Justifier brièvement la réponse. On se propose de montrer que si L est un langage rationnel, alors (L) est aussi un langage rationnel. Les questions 7 à 14 permettent deobtenir ce résultat. Page 2 sur 8 Épreuve deinformatique 2009 Si L est un langage, on note P(L) leensemble des mots de L de longueur paire et I(L) leensemble des mots de L de longueur impaire. 7 - Montrer que si L est rationnel, P(L) et I(L) sont rationnels. 8 - On considère un automate fini A reconnaissant un langage L ne contenant que des mots de longueur paire ; soit q un état utile de A. Montrer que A ne possède pas de transition dont leorigine et leextrémité soient q. 9 - On considère un automate fini A = < , Q, T, {q0}, F> reconnaissant un langage L ne contenant que des mots de longueur paire ; soit q un état utile de A. Montrer que les chemins de q0 à q sont soit tous de longueur paire, soit tous de longueur impaire. Soit A un automate fini. Soit q un état de A. On suppose que : · q est un état utile ; · q neest ni leétat initial, ni un état final ; · il neexiste dans A aucune transition dont leorigine et leextrémité soient simultanément q, x ceest-à-dire aucune transition qui seécrive q q quelle que soit leétiquette x considérée ; · il existe au moins deux transitions deorigine q ou au moins deux transitions deextrémité q. On considère leautomate obtenu à partir de A et q de la façon suivante : pour chaque quadruplet (q , q, x, y), où q et q sont deux états de A, x et y deux lettres de distinctes ou non, et tel que A contienne les x y x y transitions q q et q q, on ajoute un nouvel état r et les transitions q r et r q ; on ajoute donc autant deétats que de tels quadruplets ; chaque état ajouté est extrémité deune unique transition et origine deune unique transition. Enfin, on supprime leétat q et toutes les transitions deorigine ou deextrémité q. On note S A, q) leautomate ainsi obtenu. 10 - Soit q un état vérifiant les hypothèses ci-dessus. Montrer que les automates A et S(A, q) reconnaissent le même langage. 11 - Montrer que, si L est un langage rationnel, alors (P(L)) est aussi un langage rationnel. Soit L un langage rationnel. Soit x une lettre de . On note M(L, x) le langage défini comme suit : pour tout mot u sur lealphabet , le mot u appartient à M(L, x) si et seulement si le mot ux est dans L. 12 - Montrer que si L est un langage rationnel et x appartient à , le langage M(L, x) est rationnel. 13 - Soit L un langage. Donner une relation entre (I(L)), (M(I(L), a)) et (M(I(L), b)). 14 - Soit L un langage rationnel. Montrer que (L) est aussi un langage rationnel. 15 - Soit L un langage non rationnel. Indiquer si (L) peut être un langage rationnel. 16 - Il seagit deécrire la fonction en langage de programmation. Caml : On utilise le type suivant pour représenter les lettres de lealphabet : type lettre = a | b ;; Un mot est codé par une liste de type lettre list ; par exemple, le mot abbab est codé par la liste [a;b;b;a;b]. La liste vide [] code le mot de longueur nulle . Écrire en Caml une fonction phi telle que, si un mot u sur lealphabet est codé par une liste u de type lettre list, alors phi u renvoie une liste de type lettre list codant (u). Attention : leemploi de références ou de vecteurs est interdit. Pascal : On définit la constante et les types suivants : const MAX = 100; type Sigma = (a, b); type Mot = array[1 .. MAX] of Sigma; Écrire en Pascal une fonction phi telle que, si u de type Mot code un mot u sur lealphabet de longueur k inférieure ou égale à MAX, alors phi(u, k) renvoie un tableau de type Mot codant (u). Page 3 sur 8 Épreuve deinformatique 2009 Problème 2. Algorithmique Leobjectif de ce problème est de compter le nombre dearbres enracinés, nun urdunnés et étiquetés de nombre de noeuds donné. Pour cela, on étudie un codage particulier de ces arbres appelé cudage de Prüfer. Un arbre possède un nombre fini deéléments appelés noeuds. Les arbres considérés dans ce problème possèdent tous au moins un noeud. Un arbre enraciné nun urdunné A est défini récursivement de la façon suivante : il est constitué deun noeud particulier appelé racine de A et deun ensemble fini non ordonné, éventuellement vide, dearbres enracinés nun urdunnés appelés suus-arbres de A. Les racines des sous-arbres de A sont les fils de la racine de A et la racine de A est le père de ces derniers. Dans un arbre, deux noeuds sont dits frères seils ont même père. Learité deun noeud est son nombre de fils ; dans ce problème, learité deun noeud peut être quelconque. Les noeuds dearité 0 sont les feuilles de learbre. Un arbre est dit étiqueté si à chaque noeud est associé un entier positif ou nul, ces entiers étant deux à deux distincts ; leentier associé à un noeud est leétiquette du noeud. On pourra nommer un noeud par son étiquette ; si i est un entier, on pourra donc parler du noeud i pour le noeud deétiquette i. Dans ce problème, le terme d'arbre désignera toujours un arbre enraciné non ordonné étiqueté. Les deux dessins ci-dessous sont deux représentations graphiques deun même arbre nommé A1. Leétiquette de la racine de A1 est 4 ; leensemble des étiquettes des fils de la racine est {1, 3, 6} ; leensemble des étiquettes des fils du noeud deétiquette 6 est {2, 5} ; le noeud deétiquette 3 possède un seul fils : le noeud deétiquette 0 ; les noeuds deétiquettes 0, 1, 2, 5 neont pas de fils. Les représentations graphiques deun arbre donné diffèrent par leordre dans lequel on dessine les fils deun même noeud. 4 1 4 6 2 3 3 0 0 5 Learbre A1, première représentation 1 6 5 2 Learbre A1, seconde représentation 1 Learbre A2 représenté différent de learbre A1. ci-contre est 0 6 2 4 3 5 Learbre A2 On dira queun arbre est un arbre étiqueté cunsécutivement seil seagit deun arbre étiqueté et que leensemble de ses étiquettes forme un intervalle deentiers de plus petite valeur 0 ; autrement dit, pour un arbre ayant n noeuds et étiqueté consécutivement, leensemble des étiquettes est {0, 1, 2, ..., n ­ 1}. Les arbres A1 et A2 sont des arbres étiquetés consécutivement. Page 4 sur 8 Épreuve deinformatique 2009 Première partie : d'un codage racine-fils-frères d'un arbre au codage de Prüfer 17 - Donner la liste des arbres possédant trois noeuds et étiquetés consécutivement. Soit A un arbre étiqueté consécutivement ayant n noeuds. Pour coder A, on définit un codage nommé cudage racine-fils-frères. Pour cela, on fixe une représentation graphique de A ; on code A à leaide de : · leétiquette de la racine (qui ne dépend pas de la représentation) ; · un tableau nommé fils ; pour i compris entre 0 et n ­ 1, la case deindice i du tableau fils contient la valeur ­1 si le noeud i est une feuille de learbre et, sinon, leétiquette du fils du noeud i se situant le plus à gauche dans la représentation graphique choisie ; · un tableau nommé freres ; pour i compris entre 0 et n ­ 1, la case deindice i du tableau freres contient la valeur ­1 si le noeud i nea aucun frère sur sa droite et, sinon, leétiquette de son frère qui se trouve le premier sur sa droite. Pour learbre A1, si on choisit la première représentation, on obtient le codage suivant : · la racine est le noeud 4 ; · pour le tableau fils : les cases deindices 0, 1, 2 et 5 contiennent la valeur ­1, la case deindice 3 contient 0, la case deindice 4 contient 1, la case deindice 6 contient 2 ; · pour le tableau freres : les cases deindices 0, 3, 4 et 5 contiennent la valeur ­1, la case deindice 1 contient 6, la case deindice 2 contient 5, la case deindice 6 contient 3. Ainsi, learbre A1 est représenté par la valeur 4 pour la racine et par les deux tableaux ci-dessous : indice 0 1 2 3 4 5 6 fils ­1 ­1 ­1 0 1 ­1 2 indice freres 0 ­1 1 6 2 5 3 ­1 4 ­1 5 ­1 6 3 On définit aussi deux tableaux qui peuvent être calculés à partir du codage racine-fils-frères : · un tableau nommé peres ; pour i compris entre 0 et n ­ 1, la case deindice i contient la valeur ­1 seil seagit de la racine de learbre et, dans les autres cas, leétiquette du père du noeud i ; pour learbre A1, la case deindice 4 contient la valeur ­1, la case deindice 0 contient 3, les cases deindices 1, 3 et 6 contiennent 4, les cases deindices 2 et 5 contiennent la valeur 6 ; · un tableau nommé arites ; pour i compris entre 0 et n ­ 1, la case deindice i de ce tableau contient learité du noeud i ; pour learbre A1, les cases deindices 0, 1, 2 et 5 contiennent la valeur 0, la case deindice 3 contient 1, la case deindice 4 contient 3, la case deindice 6 contient 2. Pour learbre A1, les tableaux peres et arites sont représentés ci-dessous : indice 0 1 2 3 4 5 6 peres 3 4 6 4 ­1 6 4 indice arites 0 0 1 0 2 0 3 1 4 3 5 0 6 2 Indications pour la programmation en Pascal On définit la constante et le type suivant : const MAX = 100; type Tableau = array[0 .. MAX - 1] of Integer; La constante MAX est un majorant du nombre de noeuds des arbres considérés. Fin des indications pour la programmation en Pascal 18 - Il seagit deécrire en langage de programmation une fonction nommée calculer_peres qui, à partir du codage racine-fils-frères deun arbre étiqueté consécutivement, calcule le tableau peres correspondant à cet arbre. Caml : Écrire en Caml une fonction calculer_peres telle que, si on considère un arbre A possédant n noeuds et étiqueté consécutivement et si : · racine est un entier qui contient leétiquette de la racine de A, · fils et freres sont deux vecteurs de longueur n qui représentent respectivement les tableaux fils et freres deun codage racine-fils-frères de A, Page 5 sur 8 Épreuve deinformatique 2009 alors calculer_peres racine fils freres renvoie un vecteur de longueur n correspondant au tableau peres défini plus haut. Pascal : Écrire en Pascal une fonction calculer_peres telle que, si on considère un arbre A étiqueté consécutivement et si : · racine est un entier qui contient leétiquette de la racine de A, · fils et freres sont de type Tableau et représentent respectivement les tableaux fils et freres deun codage racine-fils-frères de A, · n est un entier qui contient le nombre de noeuds de A, alors calculer_peres(racine, fils, freres, n) renvoie un tableau de type Tableau contenant, entre les indices 0 et n ­ 1, le tableau peres défini plus haut. 19 - Indiquer, en fonction du nombre de noeuds de learbre considéré, la complexité de la fonction calculer_peres. 20 - Il seagit deécrire en langage de programmation une fonction nommée calculer_arites qui, à partir du codage racine-fils-frères deun arbre étiqueté consécutivement, renvoie le tableau arites correspondant à cet arbre. Caml : Écrire en Caml une fonction calculer_arites telle que, pour un arbre A possédant n noeuds et étiqueté consécutivement, si fils et freres sont deux vecteurs de longueur n qui représentent respectivement les tableaux fils et freres deun codage racine-fils-frères de A, alors calculer_arites fils freres renvoie un vecteur correspondant au tableau arites défini plus haut. Pascal : Écrire en Pascal une fonction calculer_arites telle que, pour un arbre A étiqueté consécutivement, si : · fils et freres sont de type Tableau et représentent respectivement les tableaux fils et freres deun codage racine-fils-frères de A, · n est un entier qui contient le nombre de noeuds de A, alors calculer_arites(fils, freres, n) renvoie un tableau de type Tableau contenant entre les indices 0 et n ­ 1 les arités des noeuds de learbre. 21 - Indiquer, en fonction du nombre de noeuds de learbre considéré, la complexité de la fonction calculer_arites. 22 - Il seagit deécrire en langage de programmation une fonction inserer qui prend en arguments un tableau table deentiers non nécessairement distincts triés par valeurs décroissantes et un entier d ; cette fonction modifie le tableau table pour insérer leentier d en respectant leordre décroissant. Leentier d est inséré même seil figure déjà dans table. Caml : Écrire en Caml une fonction inserer telle que, si : · table est un vecteur deentiers, · nb est un entier positif ou nul ne dépassant pas la dimension du vecteur table diminuée de 1, · d est un entier, · on suppose que le vecteur table contient des entiers classés par valeurs décroissantes dans les cases deindices compris entre 0 et nb ­ 1, les autres cases du vecteur table étant ignorées, alors inserer table nb d insère la donnée d dans le vecteur table en respectant leordre décroissant. La fonction renvoie nb + 1, ceest-à-dire le nouveau nombre de données figurant dans table. Pascal : Écrire en Pascal une fonction inserer telle que, si : · table est de type Tableau, · nb est un entier positif ou nul ne dépassant pas MAX ­ 1, · d est un entier ; · on suppose que le tableau table contient entre les indices 0 et nb ­ 1 des entiers classés par valeurs décroissantes, les autres cases du tableau table étant ignorées, Page 6 sur 8 Épreuve deinformatique 2009 alors inserer(table, nb, d) insère la donnée d dans le tableau table en respectant leordre décroissant. La fonction renvoie nb + 1, ceest-à-dire le nouveau nombre de données figurant dans table. 23 - Indiquer, en fonction du nombre nb deentiers contenus dans un tableau trié table, la complexité de la fonction inserer quand elle insère un nouvel entier dans table. Soit A un arbre possédant n noeuds ; on note E(A) leensemble des étiquettes de A ; les étiquettes de A étant toutes distinctes, leensemble E(A) possède n éléments. Le codage de Prüfer deun arbre étiqueté ayant n noeuds est une suite de n ­ 1 entiers appartenant à E(A), suite notée Pr(A) ; ce codage est défini récursivement de la façon suivante. Si A est réduit à un noeud, sa racine, son codage de Prüfer est la suite vide. Sinon, soit f la feuille de A deétiquette minimum et soit p le père de f ; on note A learbre obtenu en enlevant de A la feuille f ; par définition, le codage de Prüfer de A est la suite dont le premier élément est leétiquette de p, ce premier élément étant suivi du codage de Prüfer de A. Ainsi, le codage de Prüfer de learbre A1 est : 3, 4, 6, 4, 6, 4 ; le codage de Prüfer de learbre A2 est : 1, 2, 2, 1, 6, 1. 24 - Indiquer le codage de Prüfer de learbre A3 ci-contre. 3 1 2 9 6 4 0 7 5 10 8 Learbre A3 25 - On considère un arbre A étiqueté consécutivement. Il seagit deécrire en langage de programmation une fonction qui calcule le codage de Prüfer de A. La fonction commencera par calculer les tableaux peres et arites ; puis elle construira un tableau contenant les feuilles de learbre initial classées par étiquettes décroissantes ; après cette partie préparatoire, la fonction calculera le codage de Prüfer. Caml : Écrire en Caml une fonction calculer_Prufer telle que, si on considère un arbre A étiqueté consécutivement et si : · racine est un entier qui contient leétiquette de la racine de A, · fils et freres sont deux vecteurs de longueur n qui représentent respectivement les tableaux fils et freres deun codage racine-fils-frères de A, alors calculer_Prufer racine fils freres renvoie un vecteur de longueur n ­ 1 contenant le codage de Prüfer de learbre A. Pascal : Écrire en Pascal une fonction calculer_Prufer telle que, si on considère un arbre A étiqueté consécutivement et si : · racine est un entier qui contient leétiquette de la racine de A, · fils et freres sont de type Tableau et représentent respectivement les tableaux fils et freres deun codage racine-fils-frères de A, · n est un entier qui contient le nombre de noeuds de A, alors calculer_Prufer(racine, fils, freres, n) renvoie un tableau, de type Tableau, contenant le codage de Prüfer de learbre A entre les indices 0 et n ­ 2. 26 - Indiquer la complexité du calcul du codage de Prüfer deun arbre A possédant n noeuds, étiqueté consécutivement et codé avec le codage racine-fils-frères. Page 7 sur 8 Épreuve deinformatique 2009 Seconde partie : d'un codage de Prüfer d'un arbre à un codage racine-fils-frères 27 - On suppose queon connaît le codage de Prüfer deun arbre A étiqueté consécutivement. Il seagit deécrire une fonction calculer_arites_par_Prufer qui calcule les arités des noeuds de learbre A à partir de ce codage. Caml : Écrire en Caml une fonction calculer_arites_par_Prufer telle que, pour un arbre A possédant n noeuds et étiqueté consécutivement, si Prufer est un vecteur de longueur n ­ 1 contenant le codage de Prüfer de A, alors calculer_arites_par_Prufer Prufer renvoie un vecteur de longueur n contenant les arités des noeuds de A. Avant deécrire la fonction calculer_arites_par_Prufer, on en donnera rapidement le principe. Pascal : Écrire en Pascal une fonction calculer_arites_par_Prufer telle que, pour un arbre A étiqueté consécutivement, si : · Prufer est de type Tableau et contient le codage de Prüfer de A, · n est un entier qui contient le nombre de noeuds de A, alors calculer_arites_par_Prufer(Prufer, n) renvoie un tableau, de type Tableau, contenant les arités des noeuds de A. Avant deécrire la fonction calculer_arites_par_Prufer, on en donnera rapidement le principe. 28 - Déterminer un arbre A étiqueté consécutivement dont le codage de Prüfer Pr(A) est : 2, 3, 0, 2, 2. On détaillera la démarche utilisée. 29 - On considère un arbre A ; on suppose que leensemble des étiquettes E(A) de A est {1, 3, 5, 6, 7, 9, 10, 12, 13} ; learbre A neest donc pas étiqueté consécutivement ; on suppose enfin que le codage de Prüfer Pr(A) de A est : 3, 10, 3, 7, 7, 5, 7, 5. Déterminer learbre A. On décrira succinctement la démarche utilisée. 30 - Il seagit deécrire en langage de programmation une fonction calculer_arbre qui, à partir du codage de Prüfer deun arbre A étiqueté consécutivement, calcule un codage racine-fils-frères de A. Caml : Écrire en Caml une fonction calculer_arbre telle que, pour un arbre A possédant n noeuds et étiqueté consécutivement, si : · Prufer est un vecteur de longueur n ­ 1 contenant le codage de Prüfer de A, · fils et freres sont deux vecteurs de longueur n, alors calculer_arbre Prufer fils freres modifie les vecteurs fils et freres pour queils correspondent respectivement aux tableaux fils et freres deun codage racine-fils-frères de A et renvoie leétiquette de la racine de A. Pascal : Écrire en Pascal une fonction calculer_arbre telle que, pour un arbre A possédant n noeuds et étiqueté consécutivement, si : · Prufer est de type Tableau et contient le codage de Prüfer de A, · fils et freres sont de type Tableau, · n est un entier qui contient le nombre de noeuds de A, alors calculer_arbre(Prufer, fils, freres, n) modifie les tableaux fils et freres pour queils correspondent respectivement aux tableaux fils et freres deun codage racine-fils-frères de A et renvoie leétiquette de la racine de A. Soit E un ensemble de n entiers distincts positifs ou nuls ; soit S (E) leensemble des suites de longueur n ­ 1 dont tous les éléments sont dans E, distincts ou non ; soit enfin A (E) leensemble des arbres enracinés non ordonnés, possédant n noeuds et étiquetés par les éléments de E. 31 - Montrer que leapplication Pr qui, à un arbre appartenant à A(E), associe son codage de Prüfer est une bijection entre A(E) et S (E). 32 - Déterminer le cardinal de A(E). Page 8 sur 8

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


 Mines Informatique MP 2009 -- Corrigé Ce corrigé est proposé par Olivier Levillain (École Polytechnique) ; il a été relu par Vincent Danjean (Enseignant-chercheur en école d'ingénieur) et Guillaume Batog (ENS Cachan). Ce sujet est composé de deux problèmes indépendants, de longueurs comparables. · Le premier traite de langages et d'automates ; il a pour thème une transformation sur les mots définis sur l'alphabet = {a, b}. Par extension on s'intéresse à (L) = {(u) | u L}, l'application de cette transformation à un langage. Le problème commence par six questions relativement indépendantes sur l'application de à certains langages, et sur la construction d'automates reconnaissant ces langages. Puis les questions 7 à 15 amènent à montrer que transforme un langage rationnel en un autre langage rationnel. Plusieurs de ces questions se basent sur la construction d'automates finis, qui permettent de montrer qu'un langage est rationnel. La dernière question concerne l'écriture de la fonction dans un langage de programmation (Pascal ou Caml). · Le second problème, intitulé « algorithmique », aborde deux représentations différentes des arbres enracinés, non ordonnés et étiquetés : le codage « racinefils-frères » et le codage de Prüfer. Ce problème est également composé de 16 questions distribuées en deux parties ; les questions 17 à 26 concernent le passage d'une représentation « racine-fils-frères » à une représentation de Prüfer, et les questions 27 à 30 traitent du problème inverse. Le premier problème est le plus difficile bien que les constructions demandées restent proches du cours, par exemple pour démontrer que la réunion de deux langages rationnels est un langage rationnel. Le second comporte plusieurs questions de programmation, souvent accompagnées de questions sur la complexité des algorithmes écrits. L'ensemble permet d'aborder une grande partie du programme d'informatique de prépa, ce qui fait de ce sujet une bonne planche de révision et d'entraînement. Les conseils du jury Le problème sur les automates demande de rédiger des démonstrations par doubles inclusions ou doubles implications. Les deux sens doivent être justifiés pleinement : le rapport du jury regrette « une ébauche de démonstration pour un autre sens [...] laissant au correcteur le soin de conclure » ou des tournures telles que c'est évident, c'est trivial, il est clair que... N'espérez pas « grapiller des points alors que [le jury] demande une justification bien réelle. » En programmation, le rapport du jury rappelle que la mauvaise indentation d'un programme rend sa lecture difficile (donc le risque est de perdre bêtement des points si le correcteur ne comprend pas dans les dix secondes où il lit le programme !) Il indique également que le choix d'une programmation itérative ou récursive n'est qu'une question de « préférence » personnelle, le tout étant, pour le problème sur les arbres, « de bien visualiser les déplacements effectués dans [un] arbre puis de les programmer à l'aide de la structure imposée. » Indications Premier problème 1 Considérer séparément les différents cas selon la parité de |u|. 5 Penser à décomposer L2 en éléments simples. On étudiera ensuite l'image par de ces éléments. 7 Écrire P(L) et I(L) chacun comme l'intersection de deux langages rationnels. 8 Si A possède une telle transition, il est possible d'exhiber deux mots acceptés par l'automate de parité différente, passant tous deux par q. 9 La technique à employer pour cette question est très proche de celle permettant de résoudre la question précédente. 11 Pour réussir cette question, il faut utiliser les questions 8, 9 et 10, en s'intéressant particulièrement aux états dont la « distance » à q0 est impaire. On pourra alors créer un automate équivalent à l'automate reconnaissant le langage P(L) en appliquant la transformation S(·, q) pour ces états, puis le modifier pour reconnaître (P(L)). 12 Il suffit de modifier l'ensemble des états finals de l'automate reconnaissant L pour obtenir un nouvel automate répondant à la question. 14 Les réponses aux questions 7, 11, 12 et 13 sont nécessaires à la résolution de cette question. 15 Que fait ? Second problème 18 Le tableau peres se calcule par un parcours en profondeur de l'arbre. 22 L'insertion d'un élément dans un tel tableau trié par ordre décroissant est plus simple à réaliser en partant de la fin du tableau : tant que l'on a pas trouvé l'emplacement où insérer l'élément, on décale les cases vers la droite. 25 Pour écrire le début de la fonction calculer_Prufer, l'énoncé donne de précieuses indications. La suite se fait en retirant de la liste des feuilles celle de plus petite étiquette. À chaque étape, cette liste pourra nécessiter une mise à jour : un père dont toutes les feuilles ont été retirées devra être inséré. 27 Dans le codage de Prüfer, à chaque fois qu'une feuille est retirée de l'arbre, on note son père dans un tableau, donc le nombre de fils d'un noeud donné correspond à son nombre d'apparitions dans le codage final. 28 ­ 30 Ces trois questions forment un tout concernant la transformation d'un codage de Prüfer en un codage racine-fils-frères : les deux premières proposent des exemples à traduire, alors que la troisième a pour objet la définition de l'algorithme générique. Cet algorithme utilise le tableau des arités précédemment calculé, et une liste des feuilles à rattacher. Cette liste pourra être calculée à partir de la liste des étiquettes E(A) et du tableau des arités. 31 Pour cette question, il faut trouver une fonction qui pourrait jouer le rôle d'inverse de Pr , une telle fonction ne devant pas se trouver bien loin. Montrer pour cela que toute suite de S(E) est un codage de Prüfer valide. I. Problème sur les automates Dans tout le problème, la notation usuelle |u| désigne la longueur du mot u. 1 On cherche à caractériser l'ensemble des mots u vérifiant la propriété suivante : v (uv) = (u)(v) Si u est un mot de longueur paire 2k, noté u1 · · · u2k , et si l'on considère v un mot quelconque de , que l'on note v1 v2 · · · vn , alors d'après la définition, ( u2 u1 · · · u2k u2k-1 v2 v1 · · · vn vn-1 si n est pair (uv) = u2 u1 · · · u2k u2k-1 v2 v1 · · · vn-1 vn-2 vn si n est impair Dans les deux cas, (uv) = (u)(v) : si |u| est pair, la propriété est vérifiée. À l'inverse, si u est de longueur impaire 2k + 1, considérons un mot constitué d'une unique lettre x 6= u2k+1 (ce qui est possible car l'alphabet contient au moins deux lettres). L'application de à u, x et ux donne alors : (u) = u2 u1 · · · u2k u2k-1 u2k+1 (x) = x (ux) = u2 u1 · · · u2k u2k-1 xu2k+1 L'égalité entre (ux) et (u)(x) n'est vérifiée que si u2k+1 x = xu2k+1 , ce qui est faux car x 6= u2k+1 . Il existe donc un mot x tel que (ux) 6= (u)(x). Ainsi, aucun mot de longueur impaire ne vérifie la propriété. Il est nécessaire et suffisant que u soit un mot de longueur paire pour obtenir la propriété demandée. 2 L'application de à un mot u consiste à échanger chaque lettre d'indice pair avec la lettre la précédant. Pour que (u) soit différent de u, il est donc nécessaire et suffisant qu'il existe une lettre d'indice pair qui soit différente de la lettre la précédant. (u L1 ) (k {1, . . . , |u|/2} u2k-1 6= u2k ) Soyez attentifs dans la lecture de l'énoncé, surtout pour les toutes premières questions : le rapport du jury signale que « beaucoup de candidats [...] traitent ici le cas d'égalité » (u) = u au lieu de (u) 6= u, ce qui a des répercussions dans les questions suivantes ! 3 On déduit de la question précédente qu'un mot de L1 contient un nombre pair de lettres quelconques, puis deux lettres distinctes l'une de l'autre (ab ou ba), et enfin un nombre quelconque de lettres. L1 est décrit par l'expression rationnelle (a + b) (a + b) (ab + ba) (a + b) . Un mot de L1 est caractérisé par l'existence d'un couple de lettres différentes précédé d'un nombre pair de lettres. En considérant le premier couple de lettres différentes au lieu d'un couple quelconque, on peut dire qu'un mot de L1 commence par un nombre arbitraire de couples de lettres identiques, suivi d'un couple de lettres différentes, terminé par des lettres arbitraires : L1 peut aussi être décrit par l'expression rationnelle (aa + bb) (ab + ba)(a + b) Le jury a observé que « la notion d'expression rationnelle semble parfois mal perçue » : les ensembles (, {a, b},...) et leurs opérations ( c , , ) ne doivent pas figurer dans une expression rationnelle. En outre, essayer de donner des écritures les plus simples possibles. Par exemple, pour , le jury préférait (a + b) à (a b ) . 4 L'automate A1 ci-dessous reconnaît le langage L1 : 4 a 2 a, b a, b 1 b b 5 a 3 a, b En considérant l'expression rationnelle alternative (aa + bb) (ab + ba)(a + b) de la remarque précédente, on obtient un automate avec 4 états seulement, qui est de plus déterministe : a a 1 3 b b a 4 2 b a, b 5 Afin de caractériser l'image par du langage L2 , commençons par distinguer les mots de L2 suivant la parité du nombre de lettres a ( désigne l'équivalence entre expressions rationnelles) : a b (aa) ( + a)b (aa) b + (aa) ab a b (aa) b + (aa) a + (aa) abb (car b + bb ) Puisque (aa) et (aa) ab représentent des ensembles de mots de longueur paire, le résultat de la question 1 permet d'écrire (a b ) (aa) (b ) + (aa) (a) + (aa) (ab)(b ) Pour une expression rationnelle E décrivant un langage L, on utilise le raccourci (E) pour désigner une expression rationnelle décrivant (L). Comme (aa) = (aa) , (b ) = b et (ab) = ba, on en déduit que (L2 ) est décrit par l'expression rationnelle (aa) b + (aa) a + (aa) bab .