Centrale Informatique MP 2011

&, % 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