Centrale Informatique MP 2003

Thème de l'épreuve Le problème du parenthésage
Principaux outils utilisés récurrences, arbres, langages rationnels

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


 n=>_ 99E ...DOF<ÊOEOmÊ 5265... «dam omäQ:OE - QOEÈOEU mÈPËQU Association de parenthèses Les candidats indiqueront clairement le langage de programmation choisi: Caml ou Pascal. Ce problème concerne les mots bien parenthésés : il s'agit (dans la première par-- tie) de déterminer si un mot donné est bien parenthésé (en un sens qui sera pré- cisé) et, le cas échéant, de trouver la parenthèse fermante associée à une parenthèse ouvrante donnée (deuxième partie). La troisième partie donne une extension de ce problème. Notes de programmation : ° Pour Caml : on rappelle qu'une chaîne de caractère w de longueur n a ses let- tres indexées de () a n -- 1 ; on a accès a celle d'indice le a l'aide de w. [k] . Par exemple, si w="informatique", on a w... [O] = 'i' et w.[ll] : 'e'. De même, un vecteur de taille n est indexé de () à n -- 1 . Pour les questions utilisant des piles, les candidats ont a leur disposition une structure de pile caractérisée par: ---- un type polymorphe 'a pile; ---- une fonction de création de pile vide creer_pile de signature unit -> ' a pile; -- une fonction empiler de signature ' a --> ' a pile --> unit permet- tant d'empiler un objet sur une pile; -- une fonction dépiler de signature ' & pile --> ' & permettant d'ex- traire un objet d'une pile ( le dernier empilé); -- une fonction est_vide de signature ' & pile --> bool testant si une pile est vide. Bien entendu, les fonctions empi ler et dépiler sont a effet de bord : elles modifient la pile donnée en argument. 0 Pour Pascal : pour les questions utilisant des piles, les candidats utiliseront une structure de pile d'entiers caractérisés par : -- un type défini par : type pile; -- une procédure de création de pile vide d'en-tête : procedure creer_pile (var p:pile); -- une procédure empi ler permettant d'empiler un entier sur une pile ; son en-tête est : procedure empiler(v:inteqer;var p:pile) ; -- une fonction depi ler permettant d'extraire un entier d'une pile ( le der-- nier empilé); son en-tête est : function depiler(var p:pile):integer; -- une fonction est_vide d'en-tête : function est_vide(p:pile):boolean; testant si une pile est vide. Bien entendu, la procédure empiler et la fonction depiler sont à effet de bord : elles modifient la pile donnée en argument. Il est précisé qu'en Caml comme en Pascal, les candidats n'ont ni à défi- nir le type pile ni à écrire les primitives associées données ci-dessus. Partie I - Mots bien parenthe'3és I.A - Le langage gp des mots bien parenthésés Dans cette partie, on s'intéresse au langage gp des mots bien parenthésés. Initialement, il s'agit de mots sur l'alphabet constitué des deux lettres "(" et ")", c'est-à-dire les parenthèses ouvrante et fermante. Les mots de 31) corres- pondent à la suite des parenthèses pouvant intervenir dans une expression mathématique syntaxiquement correcte. Par exemple, l'expression 2 + ((x + y)*((x + 2)>æ<2)) nous fournit le mot bien parenthésé (() (O)). Par contre, le mot ) ( n'est pas bien parenthésé, tout comme ()). / ;), On donne comme définition : « un mot est "bien parenthese si à toute paren- thèse ouvrante est associée une (unique) parenthèse fermante qui lui est posté- rieure ». Dans cette première partie, il sera question d'expressions rationnelles. Les parenthèses apparaissant naturellement dans de telles expressions, la définition de gp qui va suivre fait jouer à la lettre a le rôle de la parenthèse ouvrante "(" et a la lettre b le rôle de la parenthèse fermante ")" ; l'alphabet de travail est donc {a,b} . On définit successivement des ensembles Ln (n e ]N) en posant Lo : {a} (le langage constitué uniquement du mot vide) et, pour (n e ]N) : 2 Ln+l : LnULnUaLnb, Lî désignant l'ensemble de tous les concaténés possibles de deux mots quelcon- ques de Ln , et aLnb les mots de la forme a - w - b , pour w décrivant Ln . Enfin, on définit:ÏP : U Ln. nelN Pour we {a,b}*, lwl désigne la longueur de w, et lwla(resp.lwlb le nombre d'occurrences de la lettre a (resp.b) apparaissant dans w et, pour i entier, wi désigne la i-ème lettre de w. I.A.1) Montrer soigneusement que abaabb & gp. I.A.2) Montrer que pour tout w e $;», on a lwla : lwlb , et que si w ;: 8, alors il commence par un "a " et termine par un "(9 ". I.A.8) Montrer que lorsque w EUR gp , alors pour tout i tel que wi : a , il existe j>i tel que w[i...j]e gp, ou w[i...j] : wi...wj est le sous--mot de w constitué de ses lettres d'indices compris entre i et j . A-t--on unicité de j '? I.B - Caractère non reconnaissable de gp I.B.1) Montrer que le langage 3 : {anbnîn 5 IN} n'est pas reconnaissable par automate fini. I.B.2) Justifier le fait que l'intersection de deux langages reconnaissables par automates finis est elle-même reconnaissable par un automate fini. I.B.3) En décrivant 3 comme intersection de 3 p et d'un langage bien choisi, montrer que gp n'est pas reconnaissable par un automate fini. , I.C - Vérification du caractère "bien parenthèse" I.C.1) Montrer soigneusement que w e Èp si et seulement si lwla : 'wb| , et pour tout préfixe u de w, lala 2 lulb. 1.0.2) Écrire une fonction parenthese déterminant si oui ou non un mot donné est bien parenthésé. On demande une fonction dont la complexité (en terme d'opérations élémentaires) soit linéaire en la taille de la chaîne fournie (avec une justification rapide). Les candidats rédigeant en Caml écriront une fonction de signature : parenthese : string --> bool= et ceux qui rédigent en Pascal écriront une fonction d'en-tête : function parenthese (w:string):boolean; Partie II - Fermeture d'une parenthèse Dans cette partie, on cherche à associer à chaque parenthèse ouvrante la paren- thèse fermante associée. Pour des raisons de lisibilité on re rend comme al ha- ? bet de travail l'ensemble constitué des lettres "(" et ")". Par exemple, (())00 EUR 0% alors que (>) & £"P. On a vu que lorsque w EUR 3 p, alors pour tout i tel que w,- =(, il existe j >i tel que w[i...j] e gp : si j est minimal, on dit que wj est la fermante associée à l'ouvrante w,- , et réciproquement. Dans cette partie, l'objectif est d'obtenir tou- tes les associations ouvrantes/fermantes d'un mot bien parenthésé donné. II.A - Deux algorithmes élémentaires On propose ici deux algorithmes permettant de répondre au problème des associations : dans chaque cas, on demande de justifier et préciser l'algorithme, d'écrire une fonction (en Caml) ou une procédure (en Pascal) le mettant en oeuvre, et de calculer la complexité de cet algorithme en terme d'opérations élé- mentaires, en fonction de la longueur du mot pris en entrée. En particulier, on exhibera des « cas limites » atteignant les complexités dans le pire des cas. Notes de programmation : ° En Caml : les fonctions auront pour signature : associations:string --> int vect =  et prendront en entrée une chaîne de caractère supposée bien parenthésée. Si w a pour longueur n , on mettra en position i du vecteur résultat l'in- dice ( compris entre 0 et n -- 1 ) de l'ouvrante /fermante asSocie'e a w - [i] . Par exemple, associations "(()())()";; retournera [5;2;1;4;3;0;7;6] . ° En Pascal : on dispose d'un type tableau défini par type tableau=array[l 1000] of integer; on écrira donc des procédures d'en-tête : procedure association(w:string; var resultat:tableau); ces procédures assigneront resultat[i] pour l£iSiwl . Par exemple, l'exé- cation de association ("(()())()",t) ; affectera aux 8 premières cases du tableau t les valeurs 6, 3, 2, 5, 4, l, 8, 7 . II. A. 1) Premier algorithme: pour chaque i tel que 1 _<_ i S lwl , on cherche le plus petit j > L' tel que w[i. .j] est bien parenthésé. ll.A.2) Second algorithme : on utilise une structure de pile (LIFO : on dépile le dernier objet empilé). On part d'une pile vide et on lit les lettres suc- cessives de w & gp : lorsqu'on rencontre une parenthèse ouvrante w, = (, on empile sa position i , et lorsqu'on rencontre une parenthèse fermante w j =), on dépile un entier le de la pile, et la parenthèse ouvrante associée à w - est alors ] w ,, . II.B - Utilisation de l'arbre réduit Deux mots w1> w2 e {( ,)}* sont dits équivalents (et on note w] N w2) lorsqu'on peut obtenir l'un à partir de l'autre en faisant apparaître et disparaître des fac-- teurs () Par exemple : (() ()))) N (()))) N O)) N )) N )) () N Un mot de {( ,)}* sera dit irréductible s'il n'est équivalent à aucun mot de lon-- gueur strictement plus petite. H. B. 1) Montrer que tout mot tu de {( ,)}* est équivalent a un unique mot 1rré- ductible w' ,et que celui- -ci est dela forme ) ( ,avec 12, j 5 IN. On dit alors que w' est le représentant irréductible de w . II.B.2) En supposant w1 et w2 irréductibles, comment calculer la forme irré- ductible de leur concaténé LUle '? II.B.8) Comment caractériser les mots bien parenthésés en terme de représen- tant irréductible ? Justifier le résultat énoncé. Soit w & {( .)}* de longueur 210 ( pour simplifier l'exposé ; on maintient d'ailleurs cette hypothèse dans la suite de cette partie). On définit l'arbre réduit de w par la construction suivante : c'est un arbre binaire complet de hau- teur p dont les noeuds sont étiquetés par des mots de {( ,)}* .Les 2p feuilles sont étiquetées par les lettres de w , et chaque noeud interne a pour étiquette le repré- sentant irréductible du concaténé de ses deux fils ( cet arbre se remplit donc « étage par étage », des feuilles vers la racine} : )))))))( "/ \)))))( / \))\ / \) )))) \ )) EUR )()(\ )) /\ /\ /)((/\ /\ /\ /\ /\ /\ ( ) ( ) ) ) ) ) ) ) ( ) ) ( Exemple : arbre réduit de 000 : ()())())))))())( II.B.4) Évaluer (en fonction de !wl ) le temps nécessaire pour construire l'arbre réduit d'un mot w EUR {( ,)}* . II...B5) Construire l'arbre réduit de w1-- _ ((((()(())))))(), puis montrer que w1 EOCZP. II.B.6) Proposer un algorithme permettant de calculer la parenthèse fer- mante associée à une ouvrante donnée de w 5 gp en temps O(lnlwl) , une fois l'arbre réduit de w construit. On demande impérativement de le mettre en oeuvre dans la recherche de la fermante associée àla quatrième ouvrante du mot w1 défini plus haut. H.B.7) Pour obtenir l'ensemble des associations ouvrante/fermante d'un mot bien parenthésé, donner une évaluation du temps nécessaire si on utilise l'arbre réduit de w . Comparer avec les algorithmes élémentaires précédents. II.B.8) On suppose qu'on dispose d'une grande quantité de processeurs (de l'ordre de \wl ) capables de travailler en même temps. Expliquer informellement comment construire l'arbre réduit de W en temps O(lnlwl) ) avec O(lwt) proces- seurs. Partie III - Parenthésage hétérogène (ou colorie') On s'intéresse ici aux parenthésages hétérogènes, ou coloriés, pour lesquels on s'autorise différents types de « parenthésage », par exemple avec des parenthè- ses et crochets : on peut imbriquer différents parenthésages, sans les croiser : ([ ]) est bien parenthésé mais pas (D]. De même, ([[()]()[ ]]()) est bien parenthésé mais pas l(ll()l()l llll ]) III.A - Proposer une définition formelle du langage jf}; des mots bien paren- thésés avec les deux types de parenthèses précédents ; l'alphabet est constitué de quatre lettres : A = {( ,),[,]}. III.B - $}a est-il rationnel ? Écrire une fonction prenant en entrée une chaîne de caractère w sur l'alphabet A et retournant true ou false selon que w est dans 329 ou non. III.C - Écrire une fonction (en Caml) ou une procédure (en Pascal) nommée associations prenant en entrée une chaîne de caractère que l'on suppose bien parenthésée et calculant un vecteur (en Caml) ou un tableau (en Pascal) contenant les associations ouvrantes/fermantes avec les conventions de numé- rotation précisées dans la partie II du problème. Par exemple, si l'entrée est ([ ]([ ]))[ ], la liste retournée en Caml sera [7;2;1;6;5;4;3;0;9;8] et le tableau calculé en Pascal aura pour premières valeurs :8, 3, 2, 7, 6, 5,4, l, 10, 9. Évaluer la complexité de ce programme. 00. FIN ooo

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


 Centrale Informatique MP 2003 -- Corrigé Ce corrigé est proposé par Samuel Mimram (ENS Lyon) ; il a été relu par JeanBaptiste Rouquier (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE). Le sujet traite du problème classique qui consiste à déterminer si un mot est bien parenthésé : étant donné une suite de parenthèses, on cherche à savoir si chaque parenthèse fermante correspond à une parenthèse préalablement ouverte et si toutes les parenthèses ouvrantes sont bien fermées. Il comporte trois parties, qui ne sont pas indépendantes, dont les questions sont de difficulté progressive : · la première partie établit quelques propriétés des mots bien parenthésés, qui serviront par la suite ; · la deuxième présente différents algorithmes qui permettent de trouver la parenthèse ouvrante associée à une parenthèse fermante (et vice versa) dans un mot bien parenthésé ; · la troisième traite d'une extension du problème dans laquelle les mots sont constitués de parenthèses et de crochets. Ce sujet contient quelques questions difficiles, en particulier l'algorithme de la question II.B.6 (qui requiert de l'intuition), et demande d'être précis et méticuleux. Le raisonnement par récurrence forte est abondamment utilisé et des connaissances de cours sur les langages, les expressions régulières et les automates sont nécessaires. Des implémentations de la plupart des algorithmes proposés sont demandées. Ce problème permet ainsi de réviser certaines techniques et propriétés fondamentales pour l'épreuve d'informatique des concours. Indications I.A.1 Montrer que le mot appartient à L3 en utilisant la définition des Ln (en particulier montrer que aabb L2 ). I.A.2 Montrer la propriété sur les Ln par récurrence sur n. I.A.3 Montrer la propriété sur les Ln par récurrence sur n. Pour le contre-exemple, considérer le mot abaabb. I.B.1 Utiliser le lemme de l'étoile. I.B.2 Construire l'automate produit de deux automates. I.B.3 Utiliser le langage défini par l'expression régulière a b . I.C.1 Montrer le résultat par double implication. Le sens direct se montre sur les Ln par récurrence sur n, l'autre sens par récurrence sur la longueur de w. I.C.2 Lire w de gauche à droite et stocker le nombre de a et le nombre de b rencontrés depuis le début. Utiliser la caractérisation de la question précédente, pour conclure. II.B.1 Montrer par l'absurde l'existence d'un représentant irréductible, en construisant une suite infinie de mots de longueurs décroissantes, puis montrer son unicité en « coloriant » les lettres ajoutées au mot irréductible de départ. II.B.2 Enlever le plus possible de facteurs () au concaténé de w1 et w2 . II.B.3 Montrer qu'un mot est bien parenthésé si et seulement si son représentant irréductible est en prouvant les deux sens de l'équivalence par récurrence. II.B.4 Déterminer le nombre de noeuds de l'arbre réduit en fonction du nombre de ses feuilles. II.B.6 Faire un algorithme en deux étapes. La première vise à trouver un sous-mot de w commençant par la parenthèse ouvrante qui contient la parenthèse fermante correspondante. Ceci se fait en ajoutant des sous-arbres à une liste F de sousarbres de l'arbre réduit jusqu'à ce que le représentant irréductible du mot m(F) formé par les feuilles des arbres de F ne soit plus de la forme (i . On choisira F de façon à ce que ses éléments soient « consécutifs », c'est-à-dire que l'ensemble de toutes leurs feuilles forment un facteur de w. Dans une seconde étape, réduire le dernier sous-arbre de F (en enlevant des feuilles « à droite »), de sorte que le représentant irréductible de m(F) soit . II.B.8 Il faut calculer les étages de l'arbre en parallèle, chaque étage étant calculé en temps O(1). III.A S'inspirer de la définition de LP . III.B Raisonner comme à la question I.B.3. Pour la fonction, utiliser une pile comme à la question II.A.2 (on ne cherche pas à calculer la parenthèse fermante correspondante à une parenthèse ouvrante mais juste à vérifier qu'une parenthèse ouvrante n'est pas fermée par un crochet et vice versa). III.C Adapter la fonction de la question II.A.2. Même si l'énoncé ne le demande pas, il est très facile de fournir une implémentation des piles à l'aide de références sur des listes : type 'a pile == 'a list ref;; let creer_pile () = ref [];; let empiler x p = p := x :: !p;; let depiler p = let t::q = !p in p := q; t;; let est_vide p = !p = [];; Cela peut vous être utile pour tester vos fonctions. Caml génère une alerte lors de l'évaluation de la définition de la fonction depiler qui correspond au fait qu'on ne gère pas le cas où on essayerait de dépiler un élément d'une pile vide. La gestion de tels cas n'est pas exigible en concours. Pour les preuves, il faut utiliser la définition des mots bien parenthésés comme union des Ln et non la définition informelle de l'introduction. I. Mots bien parenthésés I.A.1 Montrons que le mot abaabb est dans LP . Le mot est dans L0 par définition. Or on a aL0 b L1 , donc ab = ab est dans L1 . Pour les mêmes raisons, aabb = a(ab)b est dans L2 car ab est dans L1 . Enfin, L1 L2 , donc ab L2 , et L2 2 L3 donc abaabb qui est le concaténé de ab et de aabb est dans L3 . Ainsi, abaabb LP I.A.2 Soit P(n) la propriété « pour tout mot w de Ln , on a |w|a = |w|b et si w 6= , alors w commence par un a et se termine par un b ». Montrons qu'elle est vraie pour tout n N. · P(0) : par définition, L0 = {} et la propriété est trivialement vérifiée. · P(n) = P(n + 1) : soit w Ln+1 . Par définition de Ln+1 , il y a trois possibilités (non exclusives). ­ w Ln : la propriété est vérifiée par hypothèse de récurrence. ­ w Ln 2 : il existe deux mots w1 et w2 dans Ln tels que w = w1 w2 . On peut supposer w1 et w2 différents du mot vide, sinon nous sommes dans le cas précédent. Par hypothèse de récurrence, on a |w1 |a = |w1 |b et |w2 |a = |w2 |b donc |w|a = |w1 |a + |w2 |a = |w1 |b + |w2 |b = |w|b Par hypothèse de récurrence, on sait aussi que w1 et w2 commencent par a et se terminent par b. Donc w commence lui aussi par a et se termine par b. ­ w aLn b : il existe un mot w de Ln tel que w = aw b. Par hypothèse de récurrence, on sait que |w |a = |w |b . On en déduit |w|a = |w |a + 1 = |w |b + 1 = |w|b Il est de plus immédiat de constater que w est distinct de , commence par a et se termine par b. La propriété P(n) est donc vérifiée pour tout entier n. [ Soit w un mot appartenant à LP = Ln . Il existe un entier n tel que w soit nN dans Ln . En appliquant la propriété précédente, on en déduit |w|a = |w|b et si w 6= alors w commence par un a et se termine par un b. Le langage LP est défini comme l'union des langages Ln . Pour montrer une propriété sur un langage défini de la sorte, il faut penser qu'il suffit de montrer la propriété sur tous les langages Ln . I.A.3 On suppose que l'indice de la première lettre d'un mot est 0 (pour être en accord avec les conventions utilisées par Caml). Soit P(n) la propriété « pour tout mot w de Ln , pour tout i tel que wi = a, il existe j > i tel que w[i . . . j] LP ». Montrons qu'elle est vraie pour tout entier n. · P(0) : on a L0 = {} et la propriété est trivialement vérifiée car si w L0 alors w = et il n'y a aucun entier i tel que wi = a. · P(n) = P(n + 1) : soient w un mot de Ln+1 et i un entier tel que wi = a. Par définition de Ln+1 , il y a trois possibilités (non exclusives). ­ w Ln : la propriété est vérifiée par hypothèse de récurrence. ­ w Ln 2 : il existe deux mots w1 et w2 , que l'on peut supposer différents de , dans Ln , tels que w = w1 w2 . Si i < |w1 | (wi est une lettre de w1 ), alors, par hypothèse de récurrence, il existe j > i tel que w1 [i . . . j] soit dans LP . Dans ce cas, w[i . . . j] = w1 [i . . . j] est un mot de LP . Sinon, on a i > |w1 | et wi est une lettre de w2 d'indice i - |w1 | dans w2 . Par hypothèse de récurrence, il existe j > i - |w1 | tel que w2 [i - |w1 | . . . j ] soit dans LP et, en posant j = j + |w1 |, on a w[i . . . j] = w2 [i - |w1 | . . . j ] qui est un mot de Lp . ­ w aLn b : il existe un mot w de Ln tel que w = aw b. Si i = 0 alors j = |w| - 1 convient, car le mot w[i . . . j], qui est égal à w, est dans Ln+1 donc dans LP . On ne peut avoir i = |w| - 1, car w|w|-1 = b. Sinon, on a 0 < i < |w| - 1 et wi est une lettre de w d'indice i - 1 dans w . Par hypothèse de récurrence, on sait qu'il existe j > i - 1 tel que w [i - 1 . . . j ] soit dans LP . Ce mot est aussi un sous-mot de w car, en posant j = j + 1, on a w[i . . . j] = w [i - 1 . . . j ]. La propriété P(n) est donc vérifiée pour tout[ entier n. Soient w un mot appartenant à LP = Ln et i un entier tel que wi = a. nN Il existe un entier n tel que w soit dans Ln . En appliquant la propriété précédente, on en déduit : Il existe j > i tel que w[i . . . j] soit dans LP .