Centrale Informatique MP 2011

Thème de l'épreuve Identification de sous-mots répétés dans un mot. Langages et automates.
Principaux outils utilisés piles, chaînes de caractères, lemme d'Arden

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


&, % Informatique

°--\«
--/ MP

EÜNE[IUHS EENÏHHLE-SHFËLEE 3 heures Calculatrices autorisées N

FI
1--l
©

Les candidats indiqueront en tête de leur copie le langage de programmation 
choisi (Pascal ou Caml}. Les
candidats ayant choisi Caml devront donner le type de chaque fonction écrite. 
Les candidats travaillant en
Pascal pourront écrire des fonctions ou des procédures.

Les deux parties sont indépendantes.

I Identification de sous--mots répétés dans un mot

Cette partie traite de l'identification de sous--mots répétés dans un mot formé 
sur un alphabet A donné. Ce
problème est particulièrement prégnant en génétique où il s'agit de repérer des 
répétitions dans des brins d'ADN,
ce qui permet de comprendre sa structure. Dans ce cas, on prend simplement A = 
{g, t, a, c}.

Soit A un alphabet et soit m : m0m1 . . . mn_1 un mot de longueur n formé sur A 
(m,» EUR A pour tout i).

Un mot sera représenté par une chaîne de caractères. Aussi bien en Caml qu'en 
Pascal, on extraira d'un mot m
le caractère de rang i a l'aide d'une fonction caractère(m,i), supposée 
fournie. Le rang du premier caractère
est 0.

LA -- Une famille de relations d'équivalence
Soit k: EUR {1, 2, . . .,n} et soient i,j EUR {O, 1, . . . ,n -- kr}. Les rangs 
z' et j sont dits k-équivalents si

OE1OE1+1 . . . oei+k--1 : OEjOEj+1 . . . OEj+k_1

c'est--à--dire si les sous--mots de longueur k commençant aux indices i et j 
sont identiques.

Ce fait est noté {i, Ek,j>.

I.A.1) Montrer que {i, Ea+b, j) peut se déduire de deux expressions simples 
construites sur El et E,.
I.A.2) Montrer que (i, Ea+b, j } peut se déduire de deux expressions simples 
construites sur E... lorsque 1) < a.

Ce résultat sera utilisé dans la suite.

I.B -- Manipulation de piles
En Caml, on définit le type pile (d'entiers) par :

type pile = {
mutable elements: int list;

};;

En Pascal, le type pile est défini par :

type
pmaillon - "maillon;
pile = pmaillon;

maillon - record
valeur: integer;
suivant: pmaillon;
end;

Le type pile possède trois opérations :

-- empile, qui ajoute un élément au sommet de la pile;

-- depile, qui rend l'élément situé au sommet de la pile et le retire de la 
pile;
-- vide, qui rend vrai si et seulement si la pile est vide.

Écrire les fonctions empile, depile et vide.

I.C -- Calcul des classes d'équivalence de El

On considère à partir de maintenant que A est composé des 26 lettres de 
l'alphabet. On suppose que l'on dispose
d'une fonction numero_lettre qui a chaque lettre (caractère) associe son rang, 
compris entre 0 et 25.

On rappelle que si l EUR {O, 1, . . . ,n -- 1}, la classe d'équivalence de i 
pour El est le sous--ensemble X,-- des entiers
j EUR {O, 1, . . . , n -- 1} tels que (i, E1,j). Une classe d'équivalence de E1 
est une partie X de {O, 1, . . . , n -- 1} pour
laquelle il existe t EUR {O, 1, . . . ,n -- 1} tel que X = X,.

I.C.1) Pour i,j EUR {O, 1, . . . ,n -- 1}, que signifie (i, E1,j) ?

I.C.2) On note p le nombre de classes d'équivalence de El ; les classes 
d'équivalence de E1 seront numérotées
par des entiers entre 0 et p -- 1. Elles seront représentées par un vecteur 
(Caml) ou tableau (Pascal) d'entiers,
de longueur n (indices numérotés de 0 a n -- 1), dans lequel l'élément de rang 
z' sera le numéro de la classe
d'équivalence de i.

Dans la suite, on utilisera le terme vecteur pour désigner aussi bien les 
vecteurs de Caml que les tableaux de
Pascal.

Exemple : pour le mot << abracadabra >>, le vecteur [O, 1, 2, O, 3, 0,4, 0, 1, 
2, 0] donne les classes d'équivalence de E1.

Ecrire une fonction construit_El qui pour un mot m donné en argument, construit 
le vecteur représentant
les classes d'équivalence de E1 ; cette fonction utilisera un seul vecteur de 
longueur n et aucune autre structure
annexe de type liste ou pile.

I.C.3) Donner la complexité de cette fonction en termes du nombre de lectures 
et d'écritures dans un vecteur.

I.C.4) On autorise maintenant la fonction construit_El a utiliser un vecteur 
supplémentaire. Réécrire
construit_El de sorte qu'elle ait une complexité en O(n).

I.D -- Classes d'équivalence des Ea+b

On cherche dans cette section à construire les classes d'équivalence de Ea+b, 
connaissant les classes d'équivalence
de Eu et sachant que b g a.

Comme précédemment, les p classes d'équivalence de E, sont numérotées de 0 a p 
-- 1.

Soit 1) le vecteur donnant les numéros des classes d'équivalence de EC,; on 
rappelle que 1} est un vecteur a n
composantes. Le but de cette section est de construire u) le vecteur a n 
composantes donnant les numéros des
classes d'équivalence de Ea+b.

Pour construire les classes d'équivalence de Ea+b, on commence par regrouper 
les indices des lettres de m en
sous-ensembles, de façon que deux éléments d, e quelconques d'un tel 
sous-ensemble vérifient (d + b, E... e + b).
On remarque que seuls sont concernés les indices d vérifiant d + b < n -- a.

I.D.1) Combien y aura--t-il de sous--ensembles au maximum '?

I.D.2) On souhaite construire ces différents sous-ensembles. On utilisera pour 
cela un vecteur de piles,
chaque pile correspondant a un sous--ensemble. Expliquer comment on peut 
simplement construire ce vecteur
de piles. On ne demande pas d'écrire de programme en Caml ou Pascal à ce stade. 
Certaines piles peuvent être
vides.

I.D.3) Une pile donnée contient donc des indices tels que deux valeurs 
successives d et e vérifient
(d + b, E...e + b). Si de plus ces deux valeurs successives vérifient 
(d,E...e), que peut-on en déduire d'utile
pour construire les classes de Ea+b ?

I.D.4) Cependant, a priori la méthode de construction des piles de la question 
I.D.2 ne garantit pas que tous
les éléments d'une pile qui appartiennent a une même classe d'équivalence de 
E,, seront placés successivement.
On cherche donc a modifier la solution de la question I.D.2 pour ajouter cette 
propriété.

Nous allons commencer par créer un premier vecteur de piles (intermédiaire), 
contenant tous les éléments de v, et
tel que si deux éléments d, e appartiennent a la même pile, alors (d, E... e). 
Ecrire une fonction empileClassesEa
qui fournit ce résultat, en fonction du vecteur v et du nombre p de classes 
d'équivalence de Ed.

I.D.5) À partir de ce vecteur de piles intermédiaire, modifier la méthode 
proposée à la question I.D.2 de
façon a obtenir un vecteur de piles final dans lequel les éléments d'une pile 
qui appartiennent a une même
classe d'équivalence de E,, sont placés successivement. La solution sera 
réalisée sous forme d'une fonction
sousEnsembles prenant en paramètre le vecteur u, vecteur de piles 
intermédiaire, et la valeur b.

I.D.6) En utilisant la propriété remarquée dans la question I.D.3, écrire une 
fonction classesAplusB qui
calcule les classes d'équivalence de Ea+b. Cette fonction rendra le vecteur w 
et prendra en paramètre le vecteur
v, le vecteur (final) de piles issu de la fonction de la question précédente et 
la valeur b.

I.D.7) Ecrire finalement la fonction classesAversAplusB qui calcule le vecteur 
w a partir du vecteur 1).

LE -- Construction des classes d 'équivalence des E,, le > 1

I.E.1) Soit q un entier naturel tel que 21 soit inférieur ou égal à. n. Montrer 
que l'on peut construire les
classes d'équivalence de E2q en appliquant q fois classesAversAplusB.

I.E.2) Ecrire une fonction classesEq qui, a un mot m de longueur n et a un 
entier quelconque k < n,
associe les classes d'équivalence de B),.
I.F -- Sous-mots répétés

I.F.1) Expliquer comment classesEq permet d'obtenir la liste des sous--mots 
répétés d'une certaine lon--
gueur EUR.

On cherche maintenant à trouver l'entier EUR maximum pour lequel il y a des 
sous--mots répétés.

I.F.2) Quel test simple sur le résultat de classesEq permet de savoir si un mot 
m contient des sous--mots
répétés de longueur EUR ?

I.F.3) Nous avons vu en I.E.1 que E2q peut être construit avec q appels à 
classesAversAplusB. En vertu de
ce résultat et de la question précédente, on doit donc pouvoir déterminer le 
plus petit entier q tel qu'il n'existe
pas de sous--mots répétés de longueur 2q dans m.

Comment alors déterminer en un minimum d'opérations le plus grand entier EUR 
(EUR < 2'1 ) tel que m contienne des
sous-mots répétés de longueur EUR ?

On ne demande pas de programmer cette opération.

II Langages et automates

II.A -- Ensembles dénombmbles
Notation -- Pour tout ensemble A, on note P(A) l'ensemble des sous--ensembles 
de A. En particulier, A E P(A).

Définitions -- Deux ensembles A et B sont dits équipotents, s'il existe une 
bijection de A vers B. Un ensemble
A est dit dénombrable si A et N sont équipotents (N désigne l'ensemble des 
entiers naturels).

II.A.1) Si A est un ensemble fini, montrer que A et P(A) ne sont pas 
équipotents.

II.A.2) Si A est un ensemble quelconque, montrer que A et ?(A) ne sont pas 
équipotents.

Indication. On peut raisonner par l'absurde en supposant qu'il existe une 
bijection f : A --> P(A) ; on considérera
B = {a E A | a & f(a)} et b tel que f(b) = B, puis on examinera la véracité de 
b E B.

II.A.3) Soit E = {0}
Montrer que P(E*) n'est pas dénombrable.

II.A.4) On peut montrer que l'ensemble des langages rationnels est dénombrable. 
Cela implique qu'il existe
des langages sur {0} qui ne sont pas rationnels. En voici un :

Soit L p = {O' | i est premier}. Montrer que Lp n'est pas rationnel.

II.B -- Lemme d'Arden

Le lemme d'Arden permet de résoudre des équations du type : X = (A - X) U B où 
A. B et X sont des langages.
Soit E un alphabet.

Définition Soit A, B C 2* deux langages sur E. Le langage A - B est défini par

A--B={uEURîî*| "DGA, wEURB/u=vw}

Le langage A* est défini comme l'union U A' avec :

iEURN
AO = {EUR}
Ai+1 : A Ai
II.B.1) Soit [ un ensemble non vide et, pour chaque 72 EUR I , soit Ai un 
langage sur 2. Soit B un langage

sur 2. Montrer les propositions suivantes :

(U A.») . B = U(Ai . B) (11.1)

'le] iEURI
B- (U A.) = U(B . A.) (11.2)
ie] ie]

II.B.2) On désigne par (E) l'équation

X=(A--X)UB

oùACE*etBCE*.
Démontrer que A* -- B est une solution de (E).
II.B.3) Démontrer que. pour l'inclusion. A* - B est la plus petite solution de 
(E).

II.B.4) Donner un exemple de valeurs de A et B pour lesquelles l'équation (E) 
admet plusieurs solutions.

II.B.5) Démontrer que si 5 EUR A alors A* -- B est l'unique solution de (E).

II.B.6) Un automate fini déterministe A est décrit par une structure (Q, 2, 6, 
q;, F) avec :

-- Q l'ensemble fini non--vide des états de A;

-- E l'alphabet;

-- 5 : Q >< E --> Q la fonction de transition;

-- q; l'état initial;

-- F C Q l'ensemble des états terminaux.

À chaque état q EUR Q on associe l'équation E(q) :

X'] = U ({a} ' X5(q,a)) Si q & F et
«162
Xq = (U (la} ' X5(q,a))) U {6} si q E F.
1162

Le système d'équations SE(A) associé à A est l'ensemble qui contient les 
équations E(q) pour q EUR Q.

On considère, et on représente ci-dessous, l'automate A = 
({q1,q2,q3},{a,b},ô,q1,{qg}) avec 5(q1,a) : q2,
5(q1, b) = «11, 5(q2,a) = % 5(q2,b) = (13, ô(qs,a) = 111 et 5(q3,b) = (13--

Écrire le système d'équations associé à A.
II.B.7) Calculer une solution de SE(.À).

II.B.8) Que représente le langage associé à (11 par la solution de SE(A) ?

oooFlNooo

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



Centrale Informatique MP 2011 -- Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été
relu par Charles-Pierre Astolfi (ENS Cachan) et Benjamin Monmege (ENS Cachan).

Le sujet d'informatique du concours Centrale/Supélec est cette année composé
(comme bien souvent) de deux problèmes indépendants.
· Le premier sujet présente une méthode pour déterminer les sous-mots répétés
au sein d'une chaîne de caractères. La clé pour effectuer ce travail consiste 
(question I.D) à écrire une fonction qui permet, connaissant les sous-mots 
répétés
de longueur a, de calculer ceux de longueur a + b pour n'importe quelle valeur
de b 6 a.
La plupart des questions sont plutôt abordables, la principale difficulté 
survenant à la question I.D. Celle-ci nécessite un usage délicat de la 
structure de
pile, plus précisément de tableaux de pile. Par ailleurs, le texte comporte deux
coquilles subtiles qui perturbent énormément si elles ne sont pas décelées.
Fort heureusement, le reste du problème est sans grande difficulté, et peut
même être abordé en admettant la question I.D.
· Le second est à la limite de la question de cours puisqu'il s'agit d'une 
application classique d'une méthode pour déterminer une expression rationnelle 
du
langage reconnu par un automate. Ce travail utilise le lemme d'Arden que,
vraisemblablement, une majorité des candidats avaient vu pendant l'année.
Pour conclure, il s'agit d'une épreuve intéressante, d'une difficulté 
raisonnable,
mais qui souffre de coquilles regrettables dans le premier problème. Il y a 
fort à parier
que les candidats qui avaient eu la bonne idée de sauter la question I.D (ou 
une partie
de cette question) avaient fait un choix très judicieux vu le peu de temps 
imparti.

Indications
Partie I
I.A.1 Remarquer que l'égalité de deux mots de longueur a + b peut se ramener à 
des
égalités entre quatre de leurs sous-mots.
I.C.1 Traduire la propriété en terme de lettres de la chaîne.
I.C.2 Parcourir le mot en associant à chaque caractère une nouvelle classe si 
on le rencontre la première fois, et la classe d'une de ses occurrences 
précédentes sinon.
I.C.4 Utiliser un tableau de longueur 26 pour stocker les classes associées à 
chaque
lettre de l'alphabet au fur et à mesure qu'on parcourt la chaîne.
I.D.1 Attention à l'erreur d'énoncé : v est un tableau de longueur n - a + 1. 
Justifier
que le nombre de sous-ensembles possibles est p.
I.D.2 Il s'agit de répartir simplement les indices des caractères de la chaîne 
en les
regroupant suivant la classe du b-ième caractère qui les suit.
I.D.4 Créer un tableau de piles de longueur p puis pour tout indice i, insérer 
i dans
la pile dont l'indice est la classe de i pour Ea .
I.D.5 Il y a une coquille de rédaction : on peut se permettre trois arguments 
dont le
tableau v représentant Ea et le résultat de la question précédente. Il faut 
alors
faire le même travail qu'en I.D.2 sauf que cette fois, on traite les éléments 
dans
l'ordre des piles du tableau de la question précédente.
I.D.6 Écrire un programme qui dépile tous les éléments du tableau obtenu par la
fonction précédente, en attribuant au passage une classe à chaque élément.
Il faut faire ce travail en donnant la même classe uniquement aux éléments
successifs d'une même pile et ayant la même classe pour Ea .
I.E.1 Remarquer que classesAversAplusB permet de calculer E2a à partir de Ea .
I.E.2 Calculer de proche en proche les E2q tant que 2q 6 k, puis faire un 
dernier
calcul à l'aide de classesAversAplusB.
I.F.1 Le mot xi · · · xi+-1 est répété si et seulement si la classe de i 
apparaît au
moins deux fois dans le tableau classesEq m k.
I.F.2 S'il n'y a aucun mot répété, toutes les classes de Ek doivent être 
distinctes.
I.F.3 Il suffit d'effectuer une recherche par dichotomie sur k.
Partie II
II.A.1
II.A.3
II.A.4
II.B.1
II.B.2
II.B.3
II.B.4
II.B.5
II.B.7
II.B.8

Noter n le cardinal de A et comparer les cardinaux de A et P(A).
Remarquer que  est en bijection avec N puis utiliser la question précédente.
Raisonner par l'absurde et utiliser le lemme de l'étoile.
Procéder méthodiquement par double inclusion.
Utiliser l'associativité et la distributivité sur  de (A, B) - A · B pour
déterminer A · (A B)  B.
Montrer par récurrence sur i que Ai · B est inclus dans X si X est solution.
Prendre le premier exemple venu du moment que  appartient à A.
Montrer l'inclusion X  A · B en raisonnant par récurrence sur la taille n
d'un élément w de X.
À l'aide de la question II.B.5, exprimer Xq1 en fonction de Xq2 , puis Xq2 en
fonction de Xq3 . Utiliser la dernière équation pour calculer Xq3 et conclure.
Montrer que Xq1 est le langage reconnu par A.

I. Identification de sous-mots
répétés dans un mot
Le choix de l'auteur de fournir une fonction caractère alourdit l'écriture
des codes. Rappelons qu'en Caml, il suffit d'écrire m.[i] pour récupérer
le i-ième caractère d'un élément du type string. Pour simplifier, c'est cette
écriture qui sera utilisée dans ce corrigé.
À noter que le jour de l'écrit, rien ne vous empêche de faire usage de
cette syntaxe, sous réserve de le préciser quelque part sur la copie afin de
ne pas « froisser » le correcteur. En revanche, il est fortement déconseillé
d'utiliser une abréviation pour la fonction numero_lettre fournie (qui cette
fois n'existe pas en Caml) sous prétexte que le nom choisi par l'énoncé est
trop long à écrire.
I.A.1 Les sous-mots xi · · · xi+a+b-1 et xj · · · xj+a+b-1 sont égaux si et 
seulement
si les sous-mots xi · · · xi+a-1 et xj · · · xj+a-1 sont égaux ainsi que xi+a · 
· · xi+a+b-1
et xj+a · · · xj+a+b-1 . En d'autres termes,
hi, Ea+b , ji  hi, Ea , ji et hi + a, Eb , j + ai
À noter que le vocabulaire de l'auteur est peu précis. Il aurait été sans doute
plus rigoureux de parler de prédicat sur i, j et k que de « fait » et « 
d'expressions simples ».
I.A.2 Lorsque b est inférieur ou égal à a, on a égalité des sous-mots xi · · · 
xi+a+b-1
et xj · · · xj+a+b-1 si et seulement si les sous-mots xi · · · xi+a-1 et xj · · 
· xj+a-1 sont
égaux ainsi que xi+b · · · xi+a+b-1 et xj+b · · · xj+a+b-1 . En d'autres termes,
Pour b 6 a, hi, Ea+b , ji  hi, Ea , ji et hi + b, Ea , j + bi.
Pour b > a, la propriété n'est plus vérifiée car si le prédicat de droite est
vérifié, on ne sait rien sur les sous-mots xi+a · · · xi+b-1 et yj+a · · · 
yj+b-1 .
I.B Les trois fonctions s'écrivent de la manière suivante
let empile p a =
p.elements <- a::p.elements;;
let depile p =
let a = hd p.elements in
p.elements <- tl p.elements;
a;;
let vide p = p.elements = [];;
Les types respectifs sont donc pile -> int -> unit pour la fonction empile,
pile -> int pour depile et enfin pile -> bool pour la fonction vide.

Le type de la fonction empile dépend bien entendu de l'ordre dans lequel
ses arguments sont fournis. De plus, la version ci-dessus est curryfiée, ce
qui n'est pas a priori nécessaire. On aurait donc pu avoir également une
fonction de type int -> pile -> unit, ou encore (pile * int) -> unit.
En revanche, il vaut mieux ne pas renvoyer la pile modifiée à la fin du 
programme, car la plupart du temps, on a seulement besoin de faire une 
modification de la mémoire du compilateur (l'énoncé aurait pu être plus précis
à ce sujet).
I.C.1 Pour deux entiers i et j, la propriété hi, E1 , ji signifie que les 
sous-mots xi
et xj sont égaux. En d'autres termes,
hi, E1 , ji signifie que les lettres xi et xj sont égales.
I.C.2 Le principe est simple : on parcourt la chaîne à l'aide d'un compteur c 
initialisé à 0. Pour chaque lettre x, on vérifie si elle apparaît parmi celles 
qui la précède.
Si ce n'est pas le cas, on incrémente le compteur c puis on attribue à x la 
classe c.
Sinon, on lui attribue la valeur attribuée à l'une des occurrences qui la 
précède.
let construit_E1 m =
let n = string_length m in
let t = make_vect n 0 in
let c = ref 0 in
for i=1 to (n-1) do
(* recherche d'une précédente occurrence *)
let j = ref 0 in
while (!j < i) && (m.[i] <> m.[!j]) do
incr j;
done;
(* attribution de la classe *)
if !j < i then t.(i) <- t.(!j)
else (incr c; t.(i) <- !c;);
done;
t;;
Le type de cette fonction est ainsi string -> int vect.
La fonction numero_lettre n'a pas servi à cette question, mais elle servira
pour la version suivante de construit_E1. Elle peut s'écrire ainsi :
let numero_lettre x = int_of_char x - int_of_char ` a` ; ;
I.C.3 Dans le pire des cas, les lettres de la chaîne sont deux à deux 
distinctes.
Chaque boucle while s'exécute i fois. Dans chacune des boucles, on fait 
exactement
deux lectures de la chaîne s. Après cette boucle, on effectue une écriture dans 
le
vecteur t. Au final, il y a donc dans le pire cas un nombre de 
lectures/écritures égal à
n
P
(2i + 1) = n(n + 2) = O(n2 )
i=1

Ainsi,

Cette version de construit_E1 a une complexité en O(n2 ).