Centrale Informatique MP 2003

 

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