//img.uscri.be/pth/57cfffd226fa1d421bcd93facb3f456f09892a9d
YouScribe est heureux de vous offrir cette publication
Lire

Informatique 2003 Classe Prepa MP Concours Centrale-Supélec

De
7 pages
Concours du Supérieur Concours Centrale-Supélec. Sujet de Informatique 2003. Retrouvez le corrigé Informatique 2003 sur Bankexam.fr.
Voir plus Voir moins
INFORMATIQUE
INFORMATIQUE
Association de parenthèses
Filière MP
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 : • PourCaml : on rappelle qu’une chaîne de caractèrewde longueurna ses let-tres indexées de0àn– 1; on a accès à celle d’indicek.à l’aide de[ ]. Par w k exemple, si="", on a.[ ]=′ ′et .[11]=′ ′. De même, w informatiquew 0i we un vecteur de taillenest indexé de0àn– 1. Pour les questions utilisant des piles, les candidats ont à leur disposition une structure de pile caractérisée par : — un type polymorphe Õa pile; — une fonction de création de pile videde signature creer_pile unit ->Õapile; — une fonctionde signaturepermet-empiler Õa->Õa pile ->unit tant d’empiler un objet sur une pile; — une fonctionde signaturepermettant d’ex-dÈpiler Õapile ->Õa traire un objet d’une pile (le dernier empilé); — une fonctionde signaturetestant si une est_vide Õapile -> bool pile est vide. Bien entendu, les fonctionset sontà effet de bord : elles empiler dÈpiler modifient la pile donnée en argument. • PourPascal : 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);
Concours Centrale-Supélec 2003
1/7
INFORMATIQUE
FiliËre MP
Filière MP
— une procédurepermettant d’empiler un entier sur une pile ; empiler son en-tête est : procedure empiler(v:integer;var p:pile); — une fonctionpermettant d’extraire un entier d’une pile (le der-depiler nier empilé); son en-tête est : function depiler(var p:pile):integer; — une fonctiond’en-tête : est_vide function est_vide(p:pile):boolean; testant si une pile est vide. Bien entendu, la procédureet la fonctionsont à effet de empiler depiler bord : elles modifient la pile donnée en argument.
Il est précisé qu’en Caml comme en Pascal, les candidats n’ontni à défi-nir le typeni à écrire les primitives associées données ci-dessus. pile
Partie I - Mots bien parenthésés
I.A - Le langageLPdes mots bien parenthésés Dans cette partie, on s’intéresse au langageLPdes 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 deLPcorres-pondent à la suite des parenthèses pouvant intervenir dans une expression mathématique syntaxiquement correcte. Par exemple, l’expression 2 +((x+y) ((x+ 2)z))* * nous fournit le mot bien parenthésé(() (())). Par contre, le mot) (n’est pas bien parenthésé, tout comme()). On donne comme définition : « un mot est “bien parenthésé” 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 LP définition dequi va suivre fait jouer à la lettreale rôle de la parenthèse ouvrante “(” et à la lettreble rôle de la parenthèse fermante “)” ; l’alphabet de travail est donc{a,b}.
Concours Centrale-Supélec 2003
2/7
INFORMATIQUE FilièreMP On définit successivement des ensemblesL(nIN)en posantL={ε(l}e n0 langage constitué uniquement du mot vide) et, pour(nIN): 2 L=LLba L, n+ 1nn n 2 Ldésignant l’ensemble de tous les concaténés possibles de deux mots quelcon-n ques deL, etba Lles mots de la formeawb, pourwdécrivantL. n nn Enfin, on définit :LP=L. n nIN Pourw{a,b},w, edésigne la longueur dewt (rwesp. lewnombre a b d’occurrences de la lettrea(resp.b) apparaissant danswet, pourientier,w i désigne laide-ème lettrew. I.A.1) Montrersoigneusement queabaabbLP. I.A.2) Montrerque pour toutwLP, on aa b, alors, et que si w=w w≠ ε il commence par un “a” et termine par un “b”. I.A.3) Montrerque lorsqueLP, alors pour toutitel quewi=a, il existe w j>itel quew[ij] ∈LP, ouw iwiwjest le sous-mot deconstitué [ …j]=w de ses lettres d’indices compris entrei?et .A-t-on unicité de I.B - Caractère non reconnaissable deLP n n I.B.1) Montrerque le langageL={a bnIN}n’est pas reconnaissable par automate fini. I.B.2) Justifierle fait que l’intersection de deux langages reconnaissables par automates finis est elle-même reconnaissable par un automate fini. I.B.3) Endécrivantcomme intersection deLePt d’un langage bien choisi, montrer queLPn’est pas reconnaissable par un automate fini. I.C - Vérification du caractère “bien parenthésé” I.C.1) Montrersoigneusement quewLPsi et seulement siwa=b, et w pour tout préfixeudew,uu. a b I.C.2) Écrireune fonctiondéterminant si oui ou non un mot parenthese 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=<fun> et ceux qui rédigent en Pascal écriront une fonction d’en-tête : function parenthese (w:string):boolean;
Concours Centrale-Supélec 2003
3/7
INFORMATIQUE FilièreMP 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 reprend comme alpha-bet de travail l’ensemble constitué des lettres “(” et “)”. LPLP Par exemple, (())()()alors que ()). LP i On a vu que lorsquew, alors pour toutitel quew(=, il existej>itel LP quew[ij] ∈est minimal, on dit que: siwest la fermante associée à j l’ouvrantew, et réciproquement. Dans cette partie, l’objectif est d’obtenir tou-i 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 œuvre, 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 :• EnCaml : les fonctions auront pour signature : associations:string -> int vect = <fun> et prendront en entrée une chaîne de caractèresupposée bien parenthésée. Siwa pour longueurnon mettra en positionidu vecteur résultat l’in- , dice (compris entre0etn– 1de l’ouvrante/fermante associée àw⋅ [i]  ). Par exemple, associations "(()())()";; retournera[5;2;1;4;3;0;7;6]  . En Pascal : on dispose d’un typedéfini par tableau [11000] type tableau=arrayof integer; on écrira donc des procédures d’en-tête : procedure association(w:string; var resultat:tableau); ces procédures assigneront[ ]pour1iwPar exemple, l’exé-resultat i. cution de association ("(()())()",t) ; affectera aux 8 premières cases du tableau t les valeurs6,3,2,5,4,1,8,7  .
Concours Centrale-Supélec 2003
4/7
INFORMATIQUE FilièreMP II.A.1)Premier algorithme: pour chaqueitel que1iw, on cherche le plus petitj>itel quew[ij]est bien parenthésé.
II.A.2)Second algorithmepiledeIFOe(Lnuesietcrutsur:noilutno: dépile le dernier objet empilé). On part d’une pile vide et on lit les lettres suc-Li cessives dew: lorsqu’on rencontre une parenthèse ouvrantew(=, on P empile sa positioni, et lorsqu’on rencontre une parenthèse fermantew=), on j dépile un entierkde la pile, et la parenthèse ouvrante associée àwest alors j w. k II.B - Utilisation de l’arbre réduit Deux mots1 2∈ {(,)}sont ditséquivalents(et on noteww) lorsqu’on ,w 1 2 peut obtenir l’un à partir de l’autre en faisant apparaître et disparaître des fac-teurs (). Par exemple : (() ()))) ~ (()))) ~ ())) ~ )) ~ )) () ~ … Un mot de{(,)}sera ditirréductibles’il n’est équivalent à aucun mot de lon-gueur strictement plus petite. II.B.1) Montrerque tout motwde{(,)}est équivalent à un unique mot irré-i j ductiblew, et que celui-ci est de la forme) (, aveci,jIN.On dit alors quewest le représentant irréductible dew. II.B.2) Ensupposantwetwirréductibles, comment calculer la forme irré-1 2 ductible de leur concaténéw w? 1 2 II.B.3) Commentcaractériserles mots bien parenthésés en terme de représen-tant irréductible ? Justifier le résultat énoncé.
p Soitw∈ {(,)}de longueur2(pour simplifier l’exposé;on maintient d’ailleurs cette hypothèse dans la suite de cette partie). On définitl’arbre réduit dewpar la construction suivante : c’est un arbre binaire complet de hau-p teurpdont les nœuds sont étiquetés par des mots de{(,)}.Les2feuilles sont étiquetées par les lettres dew, et chaque nœud 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) :
Concours Centrale-Supélec 2003
5/7
INFORMATIQUE
) )
))))))) (
))))) (
Filière MP
) )))) ( ε) ) ε ε)) )) )) (ε) ( ( )( )) () )) )) )( ))( Exemple :arbre réduit deω= ()())())))))())( 0
II.B.4) Évaluer(en fonction dew) le temps nécessaire pour construire l’arbre réduit d’un motw∈ {(,)}. II.B.5) Construirel’arbre réduit dew(((=(()(())))))(), puis montrer que 1 1L w. P II.B.6) Proposerun algorithme permettant de calculer la parenthèse fer-mante associée à une ouvrante donnée dewLPen tempsOlnw, une fois ( ) l’arbre réduit dewconstruit. On demande impérativement de le mettre en œuvre dans la recherche de la fermante associée à la quatrième ouvrante du mot wdéfini plus haut. 1 II.B.7) Pourobtenir 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 dew. Comparer avec les algorithmes élémentaires précédents. II.B.8) Onsuppose qu’on dispose d’une grande quantité de processeurs (de l’ordre dew) capables de travailler en même temps. Expliquer informellement comment construire l’arbre réduit dewen tempsO(lnw)) avecO(w)proces-seurs.
Concours Centrale-Supélec 2003
6/7
INFORMATIQUE FilièreMP Partie III - Parenthésage hétérogène(ou colorié) 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 ([)]. De même, ([[()]()[ ]]()) est bien parenthésé mais pas [([[()]()[ ]]][ ]) III.A -Proposer une définition formelle du langageLPdes mots bien paren-thésés avec les deux types de parenthèses précédents ; l’alphabet est constitué de quatre lettres :A={(,),[,]}. LP III.B -une chaîneest-il rationnel ? Écrire une fonction prenant en entrée de caractèrewsur l’alphabetAqueet retournantou selonwest true false dansLPou non. III.C -Écrire une fonction (en Caml) ou une procédure (en Pascal) nommée prenant en entrée une chaîne de caractèreque l’on suppose associations bien parenthéséeet 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 lapartie II du problème. Par exemple, si l’entrée est([ ]([ ]))[ ], laliste retournée en Caml sera [7;2;1;6;5;4;3;0;9;8] etle tableau calculé en Pascal aura pour premières valeurs:8,3,2,7,6,5,4,1,10,9. Évaluer la complexité de ce programme.
Concours Centrale-Supélec 2003
••• FIN •••
7/7