Centrale Informatique MP 2010

Thème de l'épreuve Étude des langages polynomiaux
Principaux outils utilisés langages, automates, programmation dynamique, graphes
Mots clefs langage polynomial

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


- version du 9 mars 2010 15h12

Calculatrices autorisées

INFORMATIQUE

n N

[

k fois

Ln , avec L0 = {} et Ln+1 = {w1 w2 |(w1 , w2 )  Ln × L}, pour tout

Filière

MP

Partie I - Quelques exemples

Montrer que L0 et L0 sont polynomiaux.

n

Prouver que L1 est polynomial.
Donner en la justifiant la valeur de L1 .
L1 est-il reconnaissable ? polynomial ?

I.C.2)
I.C.3)
I.C.4)

Dans cette section I.C, l'alphabet est réduit à A = { a} et on note L1 = { a2 | 
n  N }.
I.C.1) L1 est-il reconnaissable ? Donner un automate reconnaissant L1 ou une 
preuve
de non-reconnaissabilité de L1 .

I.C - Un autre exemple

On écrira explicitement un programme Pascal ou Caml reconnaissant L0 (resp. L0 
).

I.B.2)

I.B - Le cas de L0 = { an bn | n  N }
I.B.1) Montrer que ni L0 ni L0 n'est reconnaissable.

I.A.3) Évaluer le coût en temps et espace de la construction choisie d'un 
automate
reconnaissant L à partir d'un automate reconnaissant L.

I.A.2) Soit L un langage reconnaissable. Montrer que L est également 
reconnaissable. On construira explicitement un automate sans transition 
instantanée (appelée aussi -transition) reconnaissant L .
Les deux questions précédentes prouvent le théorème dans le cas particulier 
d'un langage
reconnaissable.

Le caractère polynomial du temps d'exécution devra être justifié

On pourra supposer qu'on dispose d'un automate fini déterministe complet, d'état
initial qi , d'états finaux F, avec des transitions données par une fonction de 
transition  calculant chaque (q, ) en temps O(1).

I.A.1) Soit L un langage reconnaissable. Montrer qu'il est polynomial. On 
demande d'écrire un programme (pas forcément en Pascal ou Caml ; du pseudo-code
en langage naturel sera accepté) prenant en entrée un mot et évaluant son 
appartenance à L.

I.A - Cas des langages reconnaissables

Page 1/4

Lorsque le candidat devra écrire un programme testant l'appartenance d'un mot
à un langage donné, il pourra supposer que les mots donnés en entrée ont leurs
lettres dans le bon alphabet : il est inutile de le vérifier.

Un langage est déclaré reconnaissable lorsqu'il est le langage accepté par un 
automate fini.

Un « langage polynomial » est, par définition, un langage L tel qu'il existe un 
programme (Caml, ou Pascal...) prenant en entrée un mot m de A et retournant un
booléen indiquant l'appartenance ou non de m à L, en un temps majoré par P(|m|),
où P est un polynôme dépendant du programme, mais pas de l'entrée m. L'entier
|m| désigne la longueur de m, c'est-à-dire son nombre de lettres. On pourra 
admettre que si P est un polynôme réel tendant vers + en +, alors il existe un
autre polynôme réel Q tel que Q est croissant sur R + , P(t) 6 Q(t) pour tout t 
> 0,
avec de plus P(t)  Q(t) lorsque t tend vers +.

Si un langage L est « polynomial », alors L l'est aussi.

Les trois parties de ce problème tournent autour d'une même question, tout en
restant largement indépendantes. Le résultat abordé dans cette épreuve est :

n  N.

Ainsi L =

On considère dans tout le problème un alphabet A. Un langage L est un ensemble
de mots de A. On désigne par L l'ensemble des mots de A obtenus par 
concaténation de suites finies de mots de L, y compris le mot vide . Chaque mot 
entrant dans
. . m}.
la concaténation est appelé facteur. En particulier si m est un mot, mk = m
| .{z

Épreuve :

Concours Centrale - Supélec 2010

- version du 9 mars 2010 15h12

Calculatrices autorisées

INFORMATIQUE

n N

[

k fois

Ln , avec L0 = {} et Ln+1 = {w1 w2 |(w1 , w2 )  Ln × L}, pour tout

Filière

MP

Partie I - Quelques exemples

Montrer que L0 et L0 sont polynomiaux.

n

Prouver que L1 est polynomial.
Donner en la justifiant la valeur de L1 .
L1 est-il reconnaissable ? polynomial ?

I.C.2)
I.C.3)
I.C.4)

Dans cette section I.C, l'alphabet est réduit à A = { a} et on note L1 = { a2 | 
n  N }.
I.C.1) L1 est-il reconnaissable ? Donner un automate reconnaissant L1 ou une 
preuve
de non-reconnaissabilité de L1 .

I.C - Un autre exemple

On écrira explicitement un programme Pascal ou Caml reconnaissant L0 (resp. L0 
).

I.B.2)

I.B - Le cas de L0 = { an bn | n  N }
I.B.1) Montrer que ni L0 ni L0 n'est reconnaissable.

I.A.3) Évaluer le coût en temps et espace de la construction choisie d'un 
automate
reconnaissant L à partir d'un automate reconnaissant L.

I.A.2) Soit L un langage reconnaissable. Montrer que L est également 
reconnaissable. On construira explicitement un automate sans transition 
instantanée (appelée aussi -transition) reconnaissant L .
Les deux questions précédentes prouvent le théorème dans le cas particulier 
d'un langage
reconnaissable.

Le caractère polynomial du temps d'exécution devra être justifié

On pourra supposer qu'on dispose d'un automate fini déterministe complet, d'état
initial qi , d'états finaux F, avec des transitions données par une fonction de 
transition  calculant chaque (q, ) en temps O(1).

I.A.1) Soit L un langage reconnaissable. Montrer qu'il est polynomial. On 
demande d'écrire un programme (pas forcément en Pascal ou Caml ; du pseudo-code
en langage naturel sera accepté) prenant en entrée un mot et évaluant son 
appartenance à L.

I.A - Cas des langages reconnaissables

Page 1/4

Lorsque le candidat devra écrire un programme testant l'appartenance d'un mot
à un langage donné, il pourra supposer que les mots donnés en entrée ont leurs
lettres dans le bon alphabet : il est inutile de le vérifier.

Un langage est déclaré reconnaissable lorsqu'il est le langage accepté par un 
automate fini.

Un « langage polynomial » est, par définition, un langage L tel qu'il existe un 
programme (Caml, ou Pascal...) prenant en entrée un mot m de A et retournant un
booléen indiquant l'appartenance ou non de m à L, en un temps majoré par P(|m|),
où P est un polynôme dépendant du programme, mais pas de l'entrée m. L'entier
|m| désigne la longueur de m, c'est-à-dire son nombre de lettres. On pourra 
admettre que si P est un polynôme réel tendant vers + en +, alors il existe un
autre polynôme réel Q tel que Q est croissant sur R + , P(t) 6 Q(t) pour tout t 
> 0,
avec de plus P(t)  Q(t) lorsque t tend vers +.

Si un langage L est « polynomial », alors L l'est aussi.

Les trois parties de ce problème tournent autour d'une même question, tout en
restant largement indépendantes. Le résultat abordé dans cette épreuve est :

n  N.

Ainsi L =

On considère dans tout le problème un alphabet A. Un langage L est un ensemble
de mots de A. On désigne par L l'ensemble des mots de A obtenus par 
concaténation de suites finies de mots de L, y compris le mot vide . Chaque mot 
entrant dans
. . m}.
la concaténation est appelé facteur. En particulier si m est un mot, mk = m
| .{z

Épreuve :

Concours Centrale - Supélec 2010

- version du 9 mars 2010 15h12

Calculatrices autorisées

INFORMATIQUE

n N

[

k fois

Ln , avec L0 = {} et Ln+1 = {w1 w2 |(w1 , w2 )  Ln × L}, pour tout

Filière

MP

Partie I - Quelques exemples

Montrer que L0 et L0 sont polynomiaux.

n

Prouver que L1 est polynomial.
Donner en la justifiant la valeur de L1 .
L1 est-il reconnaissable ? polynomial ?

I.C.2)
I.C.3)
I.C.4)

Dans cette section I.C, l'alphabet est réduit à A = { a} et on note L1 = { a2 | 
n  N }.
I.C.1) L1 est-il reconnaissable ? Donner un automate reconnaissant L1 ou une 
preuve
de non-reconnaissabilité de L1 .

I.C - Un autre exemple

On écrira explicitement un programme Pascal ou Caml reconnaissant L0 (resp. L0 
).

I.B.2)

I.B - Le cas de L0 = { an bn | n  N }
I.B.1) Montrer que ni L0 ni L0 n'est reconnaissable.

I.A.3) Évaluer le coût en temps et espace de la construction choisie d'un 
automate
reconnaissant L à partir d'un automate reconnaissant L.

I.A.2) Soit L un langage reconnaissable. Montrer que L est également 
reconnaissable. On construira explicitement un automate sans transition 
instantanée (appelée aussi -transition) reconnaissant L .
Les deux questions précédentes prouvent le théorème dans le cas particulier 
d'un langage
reconnaissable.

Le caractère polynomial du temps d'exécution devra être justifié

On pourra supposer qu'on dispose d'un automate fini déterministe complet, d'état
initial qi , d'états finaux F, avec des transitions données par une fonction de 
transition  calculant chaque (q, ) en temps O(1).

I.A.1) Soit L un langage reconnaissable. Montrer qu'il est polynomial. On 
demande d'écrire un programme (pas forcément en Pascal ou Caml ; du pseudo-code
en langage naturel sera accepté) prenant en entrée un mot et évaluant son 
appartenance à L.

I.A - Cas des langages reconnaissables

Page 1/4

Lorsque le candidat devra écrire un programme testant l'appartenance d'un mot
à un langage donné, il pourra supposer que les mots donnés en entrée ont leurs
lettres dans le bon alphabet : il est inutile de le vérifier.

Un langage est déclaré reconnaissable lorsqu'il est le langage accepté par un 
automate fini.

Un « langage polynomial » est, par définition, un langage L tel qu'il existe un 
programme (Caml, ou Pascal...) prenant en entrée un mot m de A et retournant un
booléen indiquant l'appartenance ou non de m à L, en un temps majoré par P(|m|),
où P est un polynôme dépendant du programme, mais pas de l'entrée m. L'entier
|m| désigne la longueur de m, c'est-à-dire son nombre de lettres. On pourra 
admettre que si P est un polynôme réel tendant vers + en +, alors il existe un
autre polynôme réel Q tel que Q est croissant sur R + , P(t) 6 Q(t) pour tout t 
> 0,
avec de plus P(t)  Q(t) lorsque t tend vers +.

Si un langage L est « polynomial », alors L l'est aussi.

Les trois parties de ce problème tournent autour d'une même question, tout en
restant largement indépendantes. Le résultat abordé dans cette épreuve est :

n  N.

Ainsi L =

On considère dans tout le problème un alphabet A. Un langage L est un ensemble
de mots de A. On désigne par L l'ensemble des mots de A obtenus par 
concaténation de suites finies de mots de L, y compris le mot vide . Chaque mot 
entrant dans
. . m}.
la concaténation est appelé facteur. En particulier si m est un mot, mk = m
| .{z

Épreuve :

Concours Centrale - Supélec 2010

L2 est-il reconnaissable ?

Partie II - Trois algorithmes

« L est polynomial » implique-t-il « ( L) est polynomial » ?
« L est reconnaissable » implique-t-il « ( L) est polynomial » ?

Filière MP

II.C.3) En déduire un algorithme pour calculer tous les Ti,j .
II.C.4) Programmer l'algorithme précédent, en écrivant un programme Pascal ou
Caml déterminant si m  L , en calculant tous les Ti,j .

k =i

Montrer que si 0 6 i < j 6 n - 1, alors :

-1
 _ j_
 Ti,k  Tk+1,j 
Ti,j = mi ...m j  L
( désigne le ou logique,  le et).

II.C.2)

Soit L un langage sur l'alphabet A. On considère un mot m de L formé de n 
lettres
de A, m = m0 ...mn-1 , avec mi  A pour tout i  [[0, n - 1]].
On définit, pour 0 6 i 6 j 6 n - 1, le booléen Ti,j valant true si le facteur 
mi ...m j
appartient à L , et false sinon. Ainsi, m  L si et seulement si T0,n-1 vaut 
true.
II.C.1) Soit i  [[0, n - 1]]. Que vaut Ti,i ?

II.C - Une programmation dynamique

II.B.3) Évaluer le nombre d'appels à Dans_L, dans le pire cas. On donnera un 
majorant, atteint dans un cas qu'on explicitera.

II.B.2) En utilisant la propriété précédente, écrire un programme Dans_L_Etoile2
testant l'appartenance d'un mot à L , avec les conventions de la question 
II.A.4.

II.B - Un algorithme récursif
II.B.1) Prouver la proposition suivante : « Si w0 , w1 , . . . , wn-1 sont des 
lettres de
l'alphabet A, alors le mot w = w0 ...wn-1 est dans L si et seulement si w  L ou
bien il existe k  [[0, n - 2]] tel que w0 ...wk  L et wk+1 ...wn-1  L ».

· en Caml, la fonction (dont on donnera le type) prendra en argument une 
fonction Dans_L testant l'appartenance d'un mot à L.
· en Pascal, on supposera qu'on dispose d'une fonction globale Dans_L prenant
en argument un mot (de type string) et retournant un booléen.
II.A.5) Quelle est la complexité temporelle de la fonction Dans_L_etoile ? On 
distinguera les appels à Dans_L, et les opérations arithmétiques standards 
(telles que
les divisions euclidiennes, supposées de complexité constante).
II.A.6) Si la longueur des mots est supérieure à quelques dizaines, la méthode
précédente fait intervenir de trop gros entiers. Comment l'adapter pour 
énumérer toutes les parties de [[0, n - 1]] sans manipuler des entiers de 
l'ordre de 2n ? La
complexité globale est-elle alors détériorée ?

II.A.4) Écrire une fonction Dans_L_etoile prenant en entrée un mot m et testant
l'appartenance de m à L :

Page 2/4

II.A.3) Expliquer comment associer à une partie non vide de [[0, p]] (p étant à 
préciser), une décomposition d'un mot en concaténation de mots non vides.
On traitera, pour illustrer l'explication, la décomposition :
centralesupelec=cent.rale.supelec

II.A.1) Écrire une fonction prenant en entrée deux entiers k et n, avec k 
compris
entre 0 et 2n - 1 et calculant un vecteur (ou un tableau) contenant la 
décomposition
en base 2 de k (l'ordre de placement des bits est laissé au candidat).
II.A.2) Expliquer comment utiliser la fonction précédente pour décrire toutes 
les
sous-parties de [[0, n - 1]].

II.A - Une énumération des parties de [[0, n - 1]]

I.E.4)

I.E.3)

Dans les trois questions suivantes, on demande une preuve ou un contre-exemple
rapidement justifié :
I.E.2) « L est reconnaissable » implique-t-il « ( L) est reconnaissable » ?

I.E.1) Montrer l'inclusion : ( L)  L . Donner un exemple de langage L pour
lequel cette inclusion est stricte.

( L) = {wn | w  L, et n  N }.

Si L est un langage, on lui associe un nouveau langage :

I.E - Une petite variation

I.D.2)

Par exemple, 3 × 4 = 12, donc 11#100#1100# L2 .
I.D.1) Montrer que L2 est polynomial.

L2 = { (n1 )#(n2 )#(n1 n2 )# | n1 , n2  N }.

Dans cette section I.D, l'alphabet est A = {0, 1, #} et on suppose qu'on dispose
d'une fonction  codant les entiers en des mots sur l'alphabet {0, 1} (leur 
décomposition en base 2, sans 0 en début de mot, sauf pour 0, de codage 0). Par 
exemple,
(10) =1010. On note cette fois

I.D - Un dernier exemple

INFORMATIQUE

L2 est-il reconnaissable ?

Partie II - Trois algorithmes

« L est polynomial » implique-t-il « ( L) est polynomial » ?
« L est reconnaissable » implique-t-il « ( L) est polynomial » ?

Filière MP

II.C.3) En déduire un algorithme pour calculer tous les Ti,j .
II.C.4) Programmer l'algorithme précédent, en écrivant un programme Pascal ou
Caml déterminant si m  L , en calculant tous les Ti,j .

k =i

Montrer que si 0 6 i < j 6 n - 1, alors :

-1
 _ j_
 Ti,k  Tk+1,j 
Ti,j = mi ...m j  L
( désigne le ou logique,  le et).

II.C.2)

Soit L un langage sur l'alphabet A. On considère un mot m de L formé de n 
lettres
de A, m = m0 ...mn-1 , avec mi  A pour tout i  [[0, n - 1]].
On définit, pour 0 6 i 6 j 6 n - 1, le booléen Ti,j valant true si le facteur 
mi ...m j
appartient à L , et false sinon. Ainsi, m  L si et seulement si T0,n-1 vaut 
true.
II.C.1) Soit i  [[0, n - 1]]. Que vaut Ti,i ?

II.C - Une programmation dynamique

II.B.3) Évaluer le nombre d'appels à Dans_L, dans le pire cas. On donnera un 
majorant, atteint dans un cas qu'on explicitera.

II.B.2) En utilisant la propriété précédente, écrire un programme Dans_L_Etoile2
testant l'appartenance d'un mot à L , avec les conventions de la question 
II.A.4.

II.B - Un algorithme récursif
II.B.1) Prouver la proposition suivante : « Si w0 , w1 , . . . , wn-1 sont des 
lettres de
l'alphabet A, alors le mot w = w0 ...wn-1 est dans L si et seulement si w  L ou
bien il existe k  [[0, n - 2]] tel que w0 ...wk  L et wk+1 ...wn-1  L ».

· en Caml, la fonction (dont on donnera le type) prendra en argument une 
fonction Dans_L testant l'appartenance d'un mot à L.
· en Pascal, on supposera qu'on dispose d'une fonction globale Dans_L prenant
en argument un mot (de type string) et retournant un booléen.
II.A.5) Quelle est la complexité temporelle de la fonction Dans_L_etoile ? On 
distinguera les appels à Dans_L, et les opérations arithmétiques standards 
(telles que
les divisions euclidiennes, supposées de complexité constante).
II.A.6) Si la longueur des mots est supérieure à quelques dizaines, la méthode
précédente fait intervenir de trop gros entiers. Comment l'adapter pour 
énumérer toutes les parties de [[0, n - 1]] sans manipuler des entiers de 
l'ordre de 2n ? La
complexité globale est-elle alors détériorée ?

II.A.4) Écrire une fonction Dans_L_etoile prenant en entrée un mot m et testant
l'appartenance de m à L :

Page 2/4

II.A.3) Expliquer comment associer à une partie non vide de [[0, p]] (p étant à 
préciser), une décomposition d'un mot en concaténation de mots non vides.
On traitera, pour illustrer l'explication, la décomposition :
centralesupelec=cent.rale.supelec

II.A.1) Écrire une fonction prenant en entrée deux entiers k et n, avec k 
compris
entre 0 et 2n - 1 et calculant un vecteur (ou un tableau) contenant la 
décomposition
en base 2 de k (l'ordre de placement des bits est laissé au candidat).
II.A.2) Expliquer comment utiliser la fonction précédente pour décrire toutes 
les
sous-parties de [[0, n - 1]].

II.A - Une énumération des parties de [[0, n - 1]]

I.E.4)

I.E.3)

Dans les trois questions suivantes, on demande une preuve ou un contre-exemple
rapidement justifié :
I.E.2) « L est reconnaissable » implique-t-il « ( L) est reconnaissable » ?

I.E.1) Montrer l'inclusion : ( L)  L . Donner un exemple de langage L pour
lequel cette inclusion est stricte.

( L) = {wn | w  L, et n  N }.

Si L est un langage, on lui associe un nouveau langage :

I.E - Une petite variation

I.D.2)

Par exemple, 3 × 4 = 12, donc 11#100#1100# L2 .
I.D.1) Montrer que L2 est polynomial.

L2 = { (n1 )#(n2 )#(n1 n2 )# | n1 , n2  N }.

Dans cette section I.D, l'alphabet est A = {0, 1, #} et on suppose qu'on dispose
d'une fonction  codant les entiers en des mots sur l'alphabet {0, 1} (leur 
décomposition en base 2, sans 0 en début de mot, sauf pour 0, de codage 0). Par 
exemple,
(10) =1010. On note cette fois

I.D - Un dernier exemple

INFORMATIQUE

· en Caml, on suppose qu'on dispose d'une fonction de création de file

Filière MP

Les arêtes de ce graphe permettent de localiser les facteurs de w qui 
appartiennent
à L. L'appartenance de w à L est alors équivalente à l'existence d'un chemin de 
-1
vers n - 1 dans ce graphe (ce qui revient au problème de l'accessibilité d'un 
état
dans un automate fini, par exemple). On ne demande pas de justifier ce fait.

· T = {(i, j) | i < j et wi+1 . . . w j  L} comme ensemble d'arêtes.

· S = [[-1, n - 1]] comme ensemble de sommets ;

Pour savoir si un mot w = w0 w1 . . . wn-1 de A appartient à L , on va 
considérer le
graphe orienté G L (w) = (S, T ) défini par :

On appelle graphe orienté le couple (S, T ) d'un ensemble fini S d'éléments 
appelés sommets et d'un ensemble T d'arêtes qui sont des éléments de S × S. 
Dans un tel graphe, un chemin d'un sommet d vers un
sommet f est une suite finie de sommets s0 , s1 , . . . , sn telle que s0 = d,
sn = f et, pour tout k  {0, 1, . . . , n - 1}, (sk , sk+1 )  T.

III.B - Introduction d'un graphe orienté

III.A.2) Comment modifier les fonctions précédentes si on suppose que le nombre
d'éléments entrés dans la file peut dépasser la taille du tableau, mais qu'à 
chaque
instant, le nombre d'éléments restant dans la file (ceux qui sont entrés dans 
la file
et n'en sont pas sortis) reste inférieur à la taille du tableau ?

et d'une fonction testant si la file est vide (cet état est caractérisé par le 
fait que
l'indice de début a dépassé celui de fin) function est_vide(f:fifo):boolean.
III.A.1) Écrire des fonctions ou procédures put et get répondant aux 
spécifications données plus haut.

creer_file : int -> fifo, prenant en entrée la taille du vecteur ;
et d'une fonction testant si la file est vide (cet état est caractérisé par le 
fait que
l'indice de début a dépassé celui de fin) est_vide : fifo -> bool.
· en Pascal, on suppose qu'on dispose d'une procédure de création de file :
procedure creer_file(var f:fifo)) ;

Dans un premier temps, on pourra faire l'hypothèse que le nombre total d'entrées
dans la file reste inférieur à la taille du tableau.
Page 3/4

· en Caml fonction get de type fifo -> int,
· en Pascal fonction de signature : function get(var f:fifo):integer.

Pour enlever un élément de la file, on lit la valeur de la case indexée par 
debut, puis
on incrémente cet index :

· en Caml fonction put de type int -> fifo -> unit,
· en Pascal procédure de signature : procedure put(v:integer; var f:fifo)).

Les files ont une taille maximale imposée (à la création en Caml, globalement 
via
nmax en Pascal). Les éléments de la file sont tous les éléments du 
vecteur/tableau
dont les indices sont entre debut et fin (au sens large).
Quand on entre un élément dans la file, on incrémente la valeur de fin et on 
place
le nouvel élément dans la case indexée par fin dans le tableau :

const nmax=1000;
type
fifo = record
contenu : array[1..nmax] of integer;
debut, fin : integer ;
end;

· en Pascal

type fifo={contenu:int vect; mutable debut:int; mutable fin:int};;

III.A - Structure de file
Dans cette partie, nous aurons besoin d'une structure de données appelée file, 
ou
encore « structure FIFO (pour first in first out) » : on entre les éléments les 
uns après
les autres dans la file, et lorsqu'on les sort, le premier élément enlevé est 
le premier
qui avait été entré. On fait le choix de la structure de données suivante :
· en Caml

Partie III - Utilisation d'un graphe

II.C.6) Évaluer la complexité spatiale de cette solution. Comparer avec les deux
autres solutions proposées dans cette partie.

II.C.5) Évaluer la complexité temporelle de cet algorithme. On s'intéressera 
d'une
part au nombre d'accès à la fonction testant l'appartenance à L, et d'autre 
part au
nombre d'opérations élémentaires telles qu'un ou/et logique.

INFORMATIQUE

· en Caml, on suppose qu'on dispose d'une fonction de création de file

Filière MP

Les arêtes de ce graphe permettent de localiser les facteurs de w qui 
appartiennent
à L. L'appartenance de w à L est alors équivalente à l'existence d'un chemin de 
-1
vers n - 1 dans ce graphe (ce qui revient au problème de l'accessibilité d'un 
état
dans un automate fini, par exemple). On ne demande pas de justifier ce fait.

· T = {(i, j) | i < j et wi+1 . . . w j  L} comme ensemble d'arêtes.

· S = [[-1, n - 1]] comme ensemble de sommets ;

Pour savoir si un mot w = w0 w1 . . . wn-1 de A appartient à L , on va 
considérer le
graphe orienté G L (w) = (S, T ) défini par :

On appelle graphe orienté le couple (S, T ) d'un ensemble fini S d'éléments 
appelés sommets et d'un ensemble T d'arêtes qui sont des éléments de S × S. 
Dans un tel graphe, un chemin d'un sommet d vers un
sommet f est une suite finie de sommets s0 , s1 , . . . , sn telle que s0 = d,
sn = f et, pour tout k  {0, 1, . . . , n - 1}, (sk , sk+1 )  T.

III.B - Introduction d'un graphe orienté

III.A.2) Comment modifier les fonctions précédentes si on suppose que le nombre
d'éléments entrés dans la file peut dépasser la taille du tableau, mais qu'à 
chaque
instant, le nombre d'éléments restant dans la file (ceux qui sont entrés dans 
la file
et n'en sont pas sortis) reste inférieur à la taille du tableau ?

et d'une fonction testant si la file est vide (cet état est caractérisé par le 
fait que
l'indice de début a dépassé celui de fin) function est_vide(f:fifo):boolean.
III.A.1) Écrire des fonctions ou procédures put et get répondant aux 
spécifications données plus haut.

creer_file : int -> fifo, prenant en entrée la taille du vecteur ;
et d'une fonction testant si la file est vide (cet état est caractérisé par le 
fait que
l'indice de début a dépassé celui de fin) est_vide : fifo -> bool.
· en Pascal, on suppose qu'on dispose d'une procédure de création de file :
procedure creer_file(var f:fifo)) ;

Dans un premier temps, on pourra faire l'hypothèse que le nombre total d'entrées
dans la file reste inférieur à la taille du tableau.
Page 3/4

· en Caml fonction get de type fifo -> int,
· en Pascal fonction de signature : function get(var f:fifo):integer.

Pour enlever un élément de la file, on lit la valeur de la case indexée par 
debut, puis
on incrémente cet index :

· en Caml fonction put de type int -> fifo -> unit,
· en Pascal procédure de signature : procedure put(v:integer; var f:fifo)).

Les files ont une taille maximale imposée (à la création en Caml, globalement 
via
nmax en Pascal). Les éléments de la file sont tous les éléments du 
vecteur/tableau
dont les indices sont entre debut et fin (au sens large).
Quand on entre un élément dans la file, on incrémente la valeur de fin et on 
place
le nouvel élément dans la case indexée par fin dans le tableau :

const nmax=1000;
type
fifo = record
contenu : array[1..nmax] of integer;
debut, fin : integer ;
end;

· en Pascal

type fifo={contenu:int vect; mutable debut:int; mutable fin:int};;

III.A - Structure de file
Dans cette partie, nous aurons besoin d'une structure de données appelée file, 
ou
encore « structure FIFO (pour first in first out) » : on entre les éléments les 
uns après
les autres dans la file, et lorsqu'on les sort, le premier élément enlevé est 
le premier
qui avait été entré. On fait le choix de la structure de données suivante :
· en Caml

Partie III - Utilisation d'un graphe

II.C.6) Évaluer la complexité spatiale de cette solution. Comparer avec les deux
autres solutions proposées dans cette partie.

II.C.5) Évaluer la complexité temporelle de cet algorithme. On s'intéressera 
d'une
part au nombre d'accès à la fonction testant l'appartenance à L, et d'autre 
part au
nombre d'opérations élémentaires telles qu'un ou/et logique.

INFORMATIQUE

a

0

ab

b

1

a

2

aa

a

3

b
4

a
5

· · · FIN · · ·
Page 4/4

III.B.3) Évaluer la complexité de ce programme dans le pire des cas (accès à la
fonction d'appartenance, et opérations élémentaires).
III.B.4) Faire le bilan comparé des quatre algorithmes présentés dans ce 
problème.
On ira si possible au delà de « celui-ci est plus rapide que celui-là »...

Représenter le graphe G L0 ( aabbaba).
On revient au cas général.
Pour déterminer l'accessibilité de n - 1 depuis -1, on peut effectuer un 
parcours en
largeur du graphe : une file contient les sommets déjà détectés comme 
accessibles
mais non encore traités ; dans un vecteur/tableau global, on tient à jour les 
états
que l'on sait accessibles. Le pseudo-code suivant décrit l'algorithme :
entrer -1 dans la file
TANT QUE la file n'est pas vide et que n-1 n'a pas été vu :
enlever un sommet s de la file
POUR i allant de s+1 jusqu'à n-1 :
SI (i n'a pas déjà été vu) et (w[s+1..i] appartient à L)
ALORS
vus[i]<-true
entrer i dans la file
FIN de si
FIN de pour
FIN de tant que
On admet qu'à la fin de cette boucle, vus[n-1] vaut true si et seulement si n - 
1
est effectivement accessible depuis -1 dans le graphe.
III.B.2) Écrire une nouvelle fonction testant l'appartenance d'un mot à l'étoile
d'un langage, en appliquant l'algorithme précédent.

Chaque arête  = (i, j) est indexée par le facteur wi+1 . . . w j  L justifiant
la présence de  dans le graphe.

-1

aab

III.B.1) Exemple : Soit A = { a, b} et L = { a} {b} = { ai b j | (i, j)  N2 }. 
Dans ces
conditions le graphe orienté G L ( abaaba) est représenté par

INFORMATIQUE

Filière MP

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



Centrale Informatique MP 2010 -- Corrigé
Ce corrigé est proposé par Olivier Levillain (École Polytechnique) ; il a été 
relu
par Benjamin Monmege (ENS Cachan) et Guillaume Batog (ENS Cachan).

Ce sujet étudie les langages qui peuvent être reconnus par un algorithme dont
le temps d'exécution est majoré par un polynôme en la longueur du mot testé.
Ces langages sont appelés polynomiaux. En particulier, on cherche à montrer que
si un langage L est polynomial, il en est de même du langage L .
· La première partie propose des exemples mettant en oeuvre des langages 
reconnus par un automate fini : les langages reconnaissables. Cette partie 
utilise la
théorie des automates : on y montre que la propriété d'être reconnaissable est
préservée en passant à l'étoile, et on emploie le lemme de l'étoile. Elle fait 
aussi
intervenir de la programmation et des calculs de complexité.
· La deuxième partie propose trois algorithmes différents pour construire un
programme reconnaissant L à partir d'un programme reconnaissant L. Les
questions consistent essentiellement à écrire des fonctions et à en évaluer la
complexité. Les connaissances mises en jeu sont notamment la récursivité et la
programmation dynamique.
· Enfin, la troisième partie expose un quatrième algorithme utilisant les 
graphes.
Cette partie, plus courte que les deux autres, se termine par une comparaison
des algorithmes étudiés.
Cette épreuve aborde de nombreux domaines : langages, automates, graphes,
programmation dynamique, calculs de complexité. Il s'agit donc d'un sujet très
complet, bien adapté aux révisions de fin d'année.

Indications
Partie I
I.A.1 Pour manipuler un automate fini hA, Q, , qi , Fi en Caml, on commence par
utiliser le type char pour représenter A. On considère ensuite Q comme un
sous-ensemble [[ 1 ; n ]] des entiers int ; l'état initial qi est alors un 
entier, et F
une liste d'entiers. En Caml, on peut supposer que l'on dispose d'une fonction
delta comme indiquée dans l'énoncé, ainsi que d'une fonction appartient_a
pour décider de l'appartenance d'un élément à une liste.
I.A.2 Pour construire un automate reconnaissant L à partir d'un automate A
reconnaissant L, ajouter des transitions issues d'un état final de A et 
d'extrémité un successeur d'un état initial de A.
I.B.1 Afin de démontrer ce résultat, on peut utiliser le lemme de l'étoile. 
Comme
celui-ci admet plusieurs variantes, on choisira celle qui permet d'avoir |xy| < 
p
dans la décomposition d'un mot assez long en xyz.
I.C.1 Utiliser le lemme de l'étoile pour montrer que L1 n'est pas 
reconnaissable.
I.C.3 Il faut se souvenir que l'alphabet considéré se réduit à la lettre a.
I.D.2 Tout comme pour la question I.C.1, on utilisera le lemme de l'étoile pour
prouver que le langage n'est pas reconnaissable.
I.E.2 Utiliser le lemme de l'étoile pour montrer que la propriété est fausse.
Partie II
II.A.3 On considérera différemment d'une part les indices des lettres des 
sous-mots
pairs et d'autre part les indices des lettres des sous-mots impairs.
II.B.3 Établir une relation de récurrence sur Cn . Puis poser Dn = Cn + 1.
II.C.2 On pourra utiliser le résultat de la question II.B.1.
II.C.3 La programmation dynamique repose sur l'idée de considérer les sous-mots
des plus courts aux plus longs. On se sert en effet des résultats calculés pour
les mots les plus petits afin de construire les valeurs pour les mots plus 
longs.
Partie III
III.A.2 Cette implémentation des files FIFO se nomme « tampon circulaire ». . .
III.B.3 Attention à bien ajuster la taille des structures de données utilisées.

Les conseils du jury
Le jury attend des candidats des « démonstrations claires et concises » au
lieu de « pages » de quantificateurs ou d'opérations ensemblistes. En outre,
il juge « aberrant de voir des raisonnements sur les automates sans le moindre
dessin », rappelant qu'un dessin n'est qu'un support pour faciliter la 
compréhension d'un raisonnement. Concernant la programmation, il s'avère que
« le style impératif est parfois mieux adapté » que le style récursif en Caml.
Enfin, le jury rappelle quelques rudiments sur l'écriture des programmes :
une bonne indentation, des noms de variable explicites et l'emploi du type
bool pour simuler les booléens.

I. Quelques exemples
I.A.1 Soit L un langage reconnaissable. Par définition, il existe un automate
acceptant L. Supposons, sans perte de généralité, que cet automate est 
déterministe complet et notons-le comme un quintuplet hA, Q, , qi , Fi, où A 
est l'alphabet,
Q l'ensemble d'états,  la fonction de transition, qi l'état initial et F la 
liste des
états finaux. Supposons de plus que , la fonction de transition décrite dans 
l'énoncé,
se calcule en temps O(1).
Il est important de se rappeler que tout automate fini non déterministe
(et possédant éventuellement des -transitions) peut être transformé en un
automate fini déterministe et complet équivalent. Cette transformation peut
mener à une explosion exponentielle du nombre d'états.
Ainsi, la supposition faite au début de la question n'est pas restrictive,
mais rend l'implémentation plus simple car on ne conserve qu'un état en
mémoire, pas un ensemble d'états ; de plus, le caractère complet permet
d'avoir une fonction de transition qui soit une application.
Montrons qu'il existe un algorithme vérifiant l'appartenance d'un mot m à L en
un temps linéaire en sa longueur |m|. Pour cela, appelons delta la fonction 
Caml correspondant à la fonction de transition . Supposons de plus que F est 
codé comme une
liste F d'états, et que l'on dispose de l'état initial q_i et d'une fonction 
appartient_a
telle que appartient_a E x renvoie un booléen indiquant si x appartient à la 
liste E.
let reconnait_L m =
let n = string_length m in
let q = ref q_i in
for i = 0 to n - 1 do
q := delta !q m.[i]
done;
appartient_a F !q;;
Le parcours d'un mot m consiste en |m| appels à la fonction de transition delta,
suivis d'un appel à appartient_a F x (qui consiste au pire en un parcours de la
liste F, donc est en O(1)). Ainsi, la complexité de reconnait_L est linéaire en 
|m|.
Tout langage reconnaissable est polynomial.
La fonction appartient_a peut s'écrire simplement ainsi :
let rec appartient_a e x =
match e with
| [] -> false
| y::r -> y=x or (appartient_a r x);;
On aurait également pu représenter F par un tableau de |Q| booléens
indiquant si un état donné est final ou non. Cette représentation, 
potentiellement plus gourmande en espace, permet de vérifier qu'un état est 
final en
une opération élémentaire.
Comme l'indique l'énoncé, le rapport du jury rappelle qu'un « pseudo
programme » pouvait suffire pour répondre à la question.

I.A.2 Soit L un langage reconnaissable. Il existe un automate fini déterministe 
A
acceptant L. Supposons que l'automate soit de la forme hA, Q, , qi , Fi, avec  
un
sous-ensemble de Q × A × Q tel que, si (q1 , a, q2 ) appartient à , alors il 
existe une
transition étiquetée par a entre q1 et q2 .
Cette représentation ensembliste des transitions permet d'ajouter simplement
des transitions pouvant rendre l'automate non déterministe, ce qui n'est pas
interdit par l'énoncé. On notera - la succession d'un nombre quelconque
(potentiellement nul) de transitions.
Pour construire un automate A reconnaissant L sans
ajouter de transition vide, commençons par ajouter un
deuxième état initial q  , qui sera également final, de telle
sorte que le mot vide soit accepté. Ensuite, afin de gérer
l'enchaînement de plusieurs mots de L dans le nouvel automate, on ajoute les 
transitions suivantes, entre tous les états
finaux et tous les successeurs de l'état initial original qi :
 = {(qf , a, q) | qf  F  (qi , a, q)   }

A

A

On obtient l'automate A = hA, Q  {q  } ,    , {qi , q  } , F  {q  }i non 
déterministe, mais ne contenant pas de transition vide.
Le rapport du jury signale que « moins de dix pour cent des candidats clonent
l'état initial et ses transitions sortantes. » Il ne suffit pas de déclarer 
final
l'état initial au risque d'accepter des mots n'appartenant pas à L .
Soit m un mot de L , montrons qu'il est reconnu par l'automate A . Si m est 
vide,
il est reconnu par l'automate puisque q  est à la fois initial et final. Sinon, 
il est composé de k mots non vides w1 à wk appartenant à L. En notant aj la 
première lettre
du mot wj = aj xj , il existe k chemins reconnaissant chacun des wj dans A de la
aj

(j)

xj

(j)

forme qi - q1 - qf . Pour les mots w2 à wk , on remplace la première transition
(j-1)

par une transition qf
acceptant m dans A :
a

(1)

x1

aj

(j)

- q1
(1)

a

présente dans  , pour obtenir le chemin suivant,
(2)

x2

(2)

1
2
qi -
q1 - qf -
q1 - qf

···

a

(k)

k
-
q1

xk

(k)

- qf

Inversement, soit m un mot reconnu par A , montrons qu'il appartient à L .
Si m est vide, il appartient trivialement à L . Dans le cas contraire, il est 
accepté par
un chemin non vide dans A qu'on peut décomposer de la façon suivante :
a

(1)

x1

(1)

a

(2)

x2

(2)

1
2
qi -
q1 - qf -
q1 - qf

(j-1)

où les transitions de la forme qf

aj

(j)

- q1

···

a

(k)

k
-
q1

xk

(k)

- qf

sont exactement celles appartenant

(j)
qf

à  . Nécessairement, les états
appartiennent à F, soit en tant qu'origine d'une
transition de  , soit en tant qu'état acceptant le mot.
Considérons séparément les chemins étiquetés par les mots aj xj . Par 
construction,
a

(1)

x1

(1)

1
le premier chemin qi -
q1 - qf

ne contient que des transitions qui appartien(1)

nent à , part de l'état initial qi et arrive à un état final qf , donc w1 = a1 
x1 appar(j-1)

tient à L. De manière similaire, les chemins qf

qu'une transition appartenant à  de la forme

aj

(j)

xj

(j)

- q1 - qf
(j-1)
qf

aj

-

(j)
q1 .

ne contiennent

Or, il existe par
aj

(j)

construction une transition équivalente dans , de la forme qi - q1 . Le mot