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 .