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 partie) 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 de longueur a ses lettres indexées de 0 à ; on a accès à celle d'indice à l'aide de W . [k]. Par exemple, si "informatique", on a 'i' et 'e'. De même, un vecteur de taille est indexé de 0 à . 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 vide creer_pile de signature unit ->'a pile;
une fonction empiler de signature 'a ->'a pile -> unit permettant d'empiler un objet sur une pile;
une fonction dépiler de signature 'a pile ->'a permettant d'extraire un objet d'une pile (le dernier empilé);
une fonction est_vide de signature 'a pile -> bool testant si une pile est vide.
Bien entendu, les fonctions empiler et dépiler sont à effet de bord : elles modifient la pile donnée en argument.
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);
Filière MP
une procédure empiler permettant d'empiler un entier sur une pile ; son en-tête est: procedure empiler(v:integer;var p:pile);
une fonction depiler permettant d'extraire un entier d'une pile (le dernier 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éfinir le type pile ni à écrire les primitives associées données ci-dessus.
Partie I - Mots bien parenthésés
I.A - Le langage des mots bien parenthésés
Dans cette partie, on s'intéresse au langage 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 correspondent à la suite des parenthèses pouvant intervenir dans une expression mathématique syntaxiquement correcte. Par exemple, l'expression
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 parenthè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 qui va suivre fait jouer à la lettre le rôle de la parenthèse ouvrante "(" et à la lettre le rôle de la parenthèse fermante ")" ; l'alphabet de travail est donc .
On définit successivement des ensembles en posant (le langage constitué uniquement du mot vide) et, pour ( ) :
désignant l'ensemble de tous les concaténés possibles de deux mots quelconques de , et les mots de la forme , pour décrivant .
Enfin, on définit: .
Pour désigne la longueur de , et (resp. le nombre d'occurrences de la lettre (resp. ) apparaissant dans et, pour entier, désigne la -ème lettre de .
I.A.1) Montrer soigneusement que .
I.A.2) Montrer que pour tout , on a , et que si , alors il commence par un " " et termine par un " ".
I.A.3) Montrer que lorsque , alors pour tout tel que , il existe tel que , ou est le sous-mot de constitué de ses lettres d'indices compris entre et . A-t-on unicité de ?
I.B - Caractère non reconnaissable de
I.B.1) Montrer que le langage 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 comme intersection de et d'un langage bien choisi, montrer que n'est pas reconnaissable par un automate fini.
I.C - Vérification du caractère "bien parenthésé"
I.C.1) Montrer soigneusement que si et seulement si , et pour tout préfixe de .
I.C.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=<fun>
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 parenthèse fermante associée. Pour des raisons de lisibilité, on reprend comme alphabet de travail l'ensemble constitué des lettres "(" et ")".
Par exemple, alors que ().
On a vu que lorsque , alors pour tout tel que , il existe tel que : si est minimal, on dit que est la fermante associée à l'ouvrante , et réciproquement. Dans cette partie, l'objectif est d'obtenir toutes 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 :
En Caml : les fonctions auront pour signature :
associations:string -> int vect = <fun>
et prendront en entrée une chaîne de caractère supposée bien parenthésée.
Si a pour longueur , on mettra en position du vecteur résultat l'indice (compris entre 0 et ) de l'ouvrante/fermante associée à . 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[1...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 . Par exemple, l'exécution de
association ("(()())()",t) ;
affectera aux 8 premières cases du tableau les valeurs .
II.A.1) Premier algorithme : pour chaque tel que , on cherche le plus petit tel que est bien parenthésé.
II.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 successives de : lorsqu'on rencontre une parenthèse ouvrante (, on empile sa position , et lorsqu'on rencontre une parenthèse fermante ), on dépile un entier de la pile, et la parenthèse ouvrante associée à est alors .
II.B - Utilisation de l'arbre réduit
Deux mots sont dits équivalents (et on note ) lorsqu'on peut obtenir l'un à partir de l'autre en faisant apparaître et disparaître des facteurs (). Par exemple : (() ()))) ~ ((()))) ~ ())) ~ )) ~ )) () ~ ...
Un mot de sera dit irréductible s'il n'est équivalent à aucun mot de longueur strictement plus petite.
II.B.1) Montrer que tout mot de est équivalent à un unique mot irréductible , et que celui-ci est de la forme , avec . On dit alors que est le représentant irréductible de .
II.B.2) En supposant et irréductibles, comment calculer la forme irréductible de leur concaténé ?
II.B.3) Comment caractériser les mots bien parenthésés en terme de représentant irréductible? Justifier le résultat énoncé.
Soit de longueur (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 par la construction suivante : c'est un arbre binaire complet de hauteur dont les nœuds sont étiquetés par des mots de . Les feuilles sont étiquetées par les lettres de , 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) :
II.B.4) Évaluer (en fonction de ) le temps nécessaire pour construire l'arbre réduit d'un mot .
II.B.5) Construire l'arbre réduit de , puis montrer que .
II.B.6) Proposer un algorithme permettant de calculer la parenthèse fermante associée à une ouvrante donnée de en temps , une fois l'arbre réduit de construit. On demande impérativement de le mettre en œuvre dans la recherche de la fermante associée à la quatrième ouvrante du mot défini plus haut.
II.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 . 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 ) capables de travailler en même temps. Expliquer informellement comment construire l'arbre réduit de en temps ) avec processeurs.
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 langage des mots bien parenthésés avec les deux types de parenthèses précédents; l'alphabet est constitué de quatre lettres : ,
III.B - est-il rationnel ? Écrire une fonction prenant en entrée une chaîne de caractère sur l'alphabet et retournant true ou false selon que est dans 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 et le tableau calculé en Pascal aura pour premières valeurs: .
Évaluer la complexité de ce programme.
Centrale Option Informatique MP 2003 - Version Web LaTeX | WikiPrépa | WikiPrépa
