Mines Informatique MP 2013

Thème de l'épreuve Recherche d'un motif dans un texte
Principaux outils utilisés tableaux, automates

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


A 2013 INFO. MP
ECOLE DES PONTS PARISTECH,

SUPAERO (ISAE), ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES DE SAINT-ETIENNE, MINES DE NANCY,
TELECOM BRETAGNE, ENSAE PARISTECH (EILIERE MP)
ECOLE POLYTECHNIQUE (EILIERE TSI)

CONCOURS 2013
EPREUVE d'INFORMATIQUE
Filière : MP
Durée de l'épreuve : 3 heures.
L'utilisation d'une calculatrice est autorisée.

Sujet mis àla disposition des concours :
CYCLE INTERNATIONAL, ECOLES DES MINES, TELECOM SUDPARIS, TPE--EIVP.

L'én0ncé de cette épreuve comporte 14 pages.

Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE - MP

Recommandations aux candidats

0 Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une 
erreur
d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.

0 Tout résultat fourni dans l'énoncé peut être utilisé pour les questions
ultérieures même s'il n'a pas été démontré.

0 Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents
même lorsque l'énoncé ne le demande pas explicitement.

Composition de l'épreuve
L'épreuve comporte un seul problème.

Page 1 sur 14

Épreuve d'informatique 2013

Préliminaire concernant la programmation. Il faudra écrire des fonctions ou des
procédures à l'aide d'un langage de programmation qui pourra être soit Caml, 
soit Pascal,
tout autre langage étant exclu. Indiquer en début de problème le langage de
programmation choisi; il est interdit de modifier ce choix au cours de 
l'épreuve.
Certaines questions du problème sont formulées différemment selon le langage de
programmation; cela est indiqué chaque fois que nécessaire. Par ailleurs, pour 
écrire une
fonction ou une procédure en langage de programmation, le candidat pourra 
définir des
fonctions ou des procédures auxiliaires qu'il explicitera, ou faire appel à 
d'autres fonctions ou
procédures définies dans les questions précédentes.

Dans l'énoncé du problème, un même identificateur écrit dans deux polices de 
caractères
différentes désigne la même entité, mais du point de vue mathématique pour la 
police écrite
en italique (par exemple : p) et du point de vue informatique pour celle écrite 
en romain (par
exemple : p).

Le but du sujet est d'étudier plusieurs algorithmes de recherche d'un mot, 
appelé motif, dans
un texte.

Un alphabet 2 est un ensemble fini d'éléments appelés lettres. Un mot sur 2 est 
une suite
finie, éventuellement vide, de lettres de 2 ; la longueur d'un mot u est le 
nombre de lettres
composant u ; le mot de longueur nulle est noté 8. L'ensemble des mots sur 2 
est noté Z*.
L'alphabet 2 utilisé est un sous-ensemble de l'alphabet usuel composé des 26 
lettres de a à z.
Si u est un mot, on note l(u) la longueur de u ; la notation u,-- désigne la (i 
+ 1)6 lettre de u. Le
mot u s'écrit donc : u : u0u1...ul(u) _ 1. On dit que la lettre u,-- est à la 
position i.

On dit qu'un mot f sur 2 est un facteur d'un mot u sur 2 s'il existe deux mots 
v et w sur 2
avec u : vfw, où vfw désigne le mot obtenu en concaténant v, f et w ; on 
appelle alors position
de f l'indice de u où f commence ; on dit que f figure dans u a la position 
l(v). Si v est le mot
de longueur nulle, on dit que f est un préfixe de u ; si w est le mot de 
longueur nulle, on dit
que f est un sufi'ixe de u. Il peut exister dans un mot plusieurs occurrences 
d'un même facteur.
Le mot de longueur nulle, 8, est considéré comme étant préfixe et suffixe de 
tout mot.

Dans tout l'énoncé, on considère deux mots tet rn sur un alphabet 2 de 
longueurs non nulles,

appelés respectivement texte et motif. On suppose que toute lettre de 
l'alphabet 2 apparaît au
moins une fois dans t.

On veut résoudre le problème (P) suivant :

(P) déterminer la position de chaque occurrence de m dans t.
On supposera toujours qu'on a: l(m) S l(t); on ne vérifiera pas cette condition 
dans la
programmation.
Par exemple, quand rn : abab et t : aaabababbbbalyalybbaa, rn est un facteur de 
t et figure
aux positions 2, 4 et 11.

Indications pour la programmation

Caml

Les mots sont codés en utilisant le type string de Caml.

Si u est de type string et si i est un entier correspondant à un indice d'une 
lettre de u,
string_length u renvoie le nombre de lettres de u et u . [i] est le caractère se
trouvant dans u à l'indice i.

Fin des indications pour Caml

Page 2 sur 14

Épreuve d'informatique 2013

Pascal

On utilise les définitions suivantes :
const MAX_LONGUEUR = 100;
const MAX_SIGMA = 26;

type tab_char = array[0 .. MAX_LONGUEUR -- 1] of char;
type tab_int_sigma = array[0 .. MAX_SIGMA -- 1] of integer;

type pile = RECORD

nb : integer;
table : array[0 .. MAX_LONGUEUR -- 1] of integer;
end;

La constante MAX_LONGUEUR donne la longueur maximum des mots considérés.
La constante MAX_S I GMA donne le nombre maximum de lettres de l'alphabet.

Les mots sont toujours codés en utilisant des tableaux de type tab_char ; les 
lettres du mot

sont écrites consécutivement dans ce tableau à partir de l'indice 0.
Fin des indications pour Pascal

Première partie : algorithme simple

Cl 1-- Soit s un entier positif ou nul vérifiant la relation s + Km) 5 l(t). Il 
s'agit
d'écrire une fonction est_present qui permette de savoir si m figure dans t a 
la position
s. La fonction parcourt les lettres du motif m de la gauche vers la droite et 
arrête la
recherche des que possible.
Caml : Écrire en Caml une fonction nommée est_present telle que, si :

0 m et t, de type string, codent m et t,

0 s code l'entier s,
alors est_present m t s renvoie le booléen true si m figure dans t a la
position s et le booléen f al se dans le cas contraire.
Pascal : Écrire en Pascal une fonction nommée est_present telle que, si :

0 m et t, de type tab_char, contiennent m et t,

. lm, de type int ege r, contient la longueur de m,

0 s, de type integer, contient la valeur de s,
alors est_present (m, lm, t, s) renvoie le booléen true si m figure dans t
àla position s et le booléen f al se dans le cas contraire.

Cl 2 --Préciser la complexité de la fonction est_present dans le pire cas et le
meilleur cas.

Cl 3 -- Il s'agit d'écrire une fonction nommée positions qui résout le probléme 
(P) en
utilisant la fonction est_present.

Caml : Écrire en Caml la fonction positions telle que si m et t, de type string,
codent m et t, alors positions m t renvoie une liste contenant les positions de 
m
dans t.

Page 3 sur 14

Épreuve d'informatique 2013

Pascal : Écrire en Pascal la fonction pos it ions telle que si :

0 m et t, de type t ab_char, contiennent m et t,

. lm et lt, de type integer, contiennent les longueurs de m et t,
alors positions (m, lm, t , lt) renvoie un résultat de type pile contenant,
dans le champ (ou membre) nb, le nombre de positions de m dans t et, dans le 
champ
table, la liste des positions de m dans t.

Cl 4 -- Préciser, pour une valeur de [(t) 2 1 quelconque et 1071) S l(t) 
quelconque, la
complexité dans le pire cas de la fonction positions ; on exprimera cette 
complexité en
fonction de [(t) et l(m). Donner un exemple de deux mots m et t pour lesquels 
cette
complexité est atteinte.

Deuxième partie : une amélioration de la méthode précédente

Dans la recherche simple, lorsque la recherche du motif m en position s est 
terminée, on
poursuit la recherche en position s + 1. On peut améliorer cet algorithme en 
poursuivant si
possible la recherche un peu plus loin dans le texte t ; pour cela, on suit la 
méthode décrite
plus bas nommée algorithme amélioré.

On note nb_2 le cardinal de 2. On numérote les lettres de 2 de () a nb_2 -- 1.
On suppose que l'on a défini en langage de programmation une fonction numero 
telle que :
0 en Caml, si x, de type char, code une lettre x de Z, numero x renvoie le 
numéro
de la lettre x dans 2 ;
0 en Pascal, si x, de type char, code une lettre x de Z, numero (x) renvoie une 
valeur
de type integer donnant le numéro de la lettre x dans 2.

On ne demande pas d'écrire en langage de programmation la fonction numero. On 
suppose
que cette fonction a une complexité constante.

On introduit un tableau D d'entiers défini comme suit. Si l'entier k vérifie 0 
5 k 5 nb_2 -- 1, la
case d'indice k du tableau D contient la position de la derniére occurrence de 
la lettre de
numéro k dans le motif m. Par convention, si cette lettre n'est pas présente 
dans le motif m,
cette position est égale à --1. Par exemple, pour 2 = {a, b, c} et pour le 
motif bboa, on a
nb_2 : 3, le numéro de la lettre a est 0, celui de la lettre la est 1, celui de 
la lettre c est 2 et le
tableau D contient :

0 dans la case d'indice 0, la valeur 3,

0 dans la case d'indice ], la valeur 1,

0 dans la case d'indice 2, la valeur --1.

Cl 5 -- Il s'agit de construire le tableau D en un temps linéaire en la 
longueur [(m) du
motif m. On justifiera la complexité linéaire de la construction du tableau D.
Caml : Écrire en Caml une fonction nommée calcul_D telle que, si :

0 m, de type string, code le motif m,

. an igma contient le nombre de lettres de l'alphabet 2,
alors cal cul_D m an igma renvoie un vecteur (ou tableau) codant le tableau D.
Pascal : Écrire en Pascal une fonction nommée calcul_D telle que, si :

0 m, de type tab_char, contient m,

. lm, de type integer, contient la longueur de m,

. anigma, de type int ege r, contient le nombre de lettres de l'alphabet Z,

Page 4 sur 14

Épreuve d'informatique 2013

alors calcul_D(m, lm, anigma) renvoie un tableau de

t ab_int_s igma codant le tableau D.

type

Pour décrire l'algorithme amélioré, on introduit la notion de fenêtre de 
recherche. Cette
fenêtre dépend d'un indice bvérifiant 0 $ $ S [(t) -- [(m) ; cette fenêtre 
contient les [(m) lettres
consécutives de t comprises entre les indices bet @+ [(m) -- 1 ; ces lettres 
sont mises en regard
avec les [(m) lettres du motif m. On dit alors que la fenêtre est à la position 
ei
Dans l'algorithme, la fenêtre se déplace toujours de la gauche vers la droite; 
le motif se
déplace avec la fenêtre alors que le texte ne bouge pas.
On considère l'exemple défini par :

Exemple] : tl : ababbaaacabbaab

ml : bbaa

Au départ de l'algorithme amélioré, $ : 0 et la fenêtre de recherche est en 
gris sur la figure 1.

Indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
tl a a b b a a a c a b b a a b
ml b b a a

Figure 1 : fenêtre de recherche àla position 0

On examine cette position de la fenêtre en comparant le facteur abab de tl qui 
est dans la
fenêtre avec le motif ml qui est en regard et on constate que ce facteur n'est 
pas une
occurrence de ml dans tl .

On considère alors la lettre de tl qui se trouve a droite de la fenêtre de 
recherche ; c'est la
lettre b à l'indice 4 de tl en gras sur la figure 1 ; on note cle" cette 
lettre. On remarque que si
on considère la fenêtre de recherche positionnée à l'indice 1 ou à l'indice 2, 
la lettre du motif
ml qui se trouve en regard de cle" n'est pas la lettre b, c'est la lettre a 
dans les deux cas :
l'examen de ces deux positions de la fenêtre ne permettrait pas de découvrir 
une occurrence
du motif dans le texte. C'est pourquoi on n'examine pas les positions 1 et 2 de 
la fenêtre. En
revanche, si on met la fenêtre en position 3, cle" est en regard de la dernière 
apparition de la
lettre b dans ml , en gras sur la figure 1 ; on retient cette position pour 
savoir si le motif figure
on non à l'indice 3 du texte.

La fenêtre de recherche est maintenant en gris sur la figure 2 :

Indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
tl a a b b a a a c a b b a a b
ml b b a a

Figure 2 : fenêtre de recherche àla position 3
On examine la fenêtre et on constate que tl contient une occurrence de ml àla 
position 3.

Maintenant, cle" est la lettre de tl qui se trouve à l'indice 7 en gras sur la 
figure 2 : il s'agit de
la lettre a. On déplace la fenêtre pour que cle" se trouve en regard de la 
derniére occurrence de
la lettre a dans ml , en gras sur la figure 2 ; on déplace en conséquence la 
fenêtre d'une seule
case, elle se trouve alors a la position 4 et est représentée sur la figure 3. 
On examine la
fenêtre et on constate que tl ne contient pas une occurrence de ml à l'indice 4.

Page 5 sur 14

Épreuve d'informatique 2013

Indices 0 1 2 3 4 5 6 7 9 10 11 12 13 14
tl a b a b b a a a a b b a a b
ml b b a a
Figure 3 : fenêtre de recherche àla position 4
On continue avec le même principe pour trouver d'autres éventuelles occurrences 
de ml dans

tl . Maintenant, cle" est la lettre de tl qui se trouve à l'indice 8, en gras 
sur la figure 3 : il s'agit
de la lettre c. Le déplacement suivant consistera à décaler la fenêtre vers la 
droite en
n'examinant pas les positions qui mettraient en regard de cle" une lettre de ml 
différente de la

lettre c.

Cl 6 -- Dans l'exemple de la figure 3, indiquer la prochaine position de la 
fenêtre de
recherche et dire si cette position correspond ou non a une occurrence de ml 
dans tl .

Cl 7 -- Décrire la suite du déroulement de l'algorithme appliqué à Exemple] 
jusqu'à ce
qu'on puisse conclure que toutes les occurrences de ml dans tl ont été 
déterminées.
On poursuivra les déplacements de la fenêtre vers la droite en utilisant le même
principe que précédemment.

Cl 8 -- On revient au déroulement de l'algorithme amélioré dans le cas général. 
On
suppose que la fenêtre est a la position $ et que l'on a l(t) > a) + 2l(m). En 
utilisant le
tableau D et la fonction numero décrits plus haut, indiquer la position 
suivante de la
fenêtre.

Cl 9 -- Il s'agit d'écrire une fonction positions2 qui résout le probléme (P) en
appliquant l'algorithme amélioré.
Caml : Écrire en Caml la fonction pos it ionsZ telle que si :

0 m et t, de type string, codent m et t,

. an igma contient le nombre de lettres de l'alphabet 2,
alors positionsZ m t anigma renvoie une liste contenant les positions de m
dans t déterminées selon l'algorithme amélioré.

Pascal : Écrire en Pascal la fonction po 5 it ions 2 telle que si :

0 m et t, de type tab_char, contiennent m et t,

. lm et lt, de type integer, contiennent les longueurs de m et t,

. anigma, de type integer, contient le nombre de lettres de l'alphabet 2,
alors positionsZ (m, lm, t , lt , anigma) renvoie un résultat de type
pile contenant, dans le champ nb, le nombre de positions de m dans t et, dans le
champ t able, la liste des positions de m dans t déterminées selon l'algorithme 
amélioré.

Cl 10 -- Préciser, en fonction de l(t) et l(m), la complexité dans le meilleur 
cas de la
fonction positions2. On ne prendra pas en compte la complexité du calcul du 
tableau
D. Donner un exemple qui atteint cette complexité.

Dans toute la suite, on se propose de résoudre le probléme (P) a l'aide 
d'automates.

Un automate A est décrit par un quintuplet (2, Q, ], F, 7), où :

Page 6

2 est un alphabet ;
Q est un ensemble fini et non vide appelé ensemble des états de A ;
I g Q est appelé ensemble des états initiaux de A ;

sur 14

Épreuve d'informatique 2013

. F g Q est appelé ensemble des états finals de A ;
0 T g Q >< 2 >< Q est appelé l'ensemble des transitions; étant donnée une 
transition
(p, X, a) E T, on dit qu'elle va de l'état p à l'état q et qu'elle est 
d'étiquette x; on

pourra la noter p % q ; on dit aussi que p est l'origine de la transition et a 
son
extrémité.

Un calcul de A est une suite de la forme po % p1 % 192 pk _ 1 % pk où,

pour 0 S i S k -- 1, p,-- x% p... est une transition ; po est l'origine du 
calcul, pk son
extrémité. L'étiquette du calcul est le mot x0x1x2. . .xk _ 1 formé par la 
suite des étiquettes des
transitions successives.

Un calcul de A est dit réussi si son origine est dans I et son extrémité dans 
F. Un mot m sur 2
est reconnu par A s'il est l'étiquette d'un calcul réussi. Le langage reconnu 
par A, noté L(A),
est l'ensemble des mots reconnus par A.

L'automate A est dit déterministe si 1 contient exactement un élément et si, 
pour tout p & Q et
tout x EUR 2, il existe au plus un état a & Q avec (p, X, a) E T.
L'automate A est dit complet si, pour tout p & Q et tout x EUR 2, il existe au 
moins un état a & Q
avec (p, X, a) E T.
Si A est un automate déterministe complet, on définit sa fonction de transition 
5 de
(Q >< E) dans Q par : 5(p, x) = a si et seulement si (p, X, a) E T. On définit 
alors,
récursivement, une fonction 5* de (Q >< 2 *) dans Q par :

' sipEUR Q, 5*(p, 8)=19.

. sip EUR Q, u EUR 2* etxe Z, 5*(p, ux) : 5(5*(p, u),x).
Dans tout le sujet, les automates considérés auront un seul état initial. On 
notera an le
nombre d'états d'un automate; les états seront numérotés de 0 a an -- 1. L'état 
initial
possédera toujours le numéro 0. Si p est le numéro d'un état, on dira qu'il 
s'agit de l'état p,
identifiant ainsi un état avec son numéro.

Un automate peut être représenté par un dessin comme il est fait ci-dessous 
pour représenter
l'automate Aex, qui est déterministe et non complet.

Aex possède trois états : O, 1 et 2.

L'état () est l'état initial. ° a ° b @
Aex possède un seul état final, l'état 2.

Aex possède trois transitions, les transitions @ .

(0, a, 1), (1, a, 1) et (1, b, 2)- Figure 4 : l'automate Aex

Troisième partie : implémentation d'un automate

L'automate Aex représenté sur la figure 4 sert d'exemple ci-dessous pour 
illustrer le codage
d'un automate en langage de programmation.

Indications pour Caml

On utilise une constante définie par :

let MAX_Q = 100 ;;

MAX_Q donne le nombre maximum d'états des automates considérés.

Page 7 sur 14

Épreuve d'informatique 2013

Pour représenter l'ensemble des états finals d'un automate, on utilise une 
liste, de type
int li st, qui contient les numéros des états finals.

Si p est un état d'un automate, une transition d'origine p est codée par un 
couple de type
(char * int) contenant l'étiquette de cette transition et le numéro de 
l'extrémité de cette
même transition.

Si p est un état d'un automate, on représente l'ensemble des transitions 
d'origine p par la liste
des transitions d'origine p ; cette liste est de type (char * int) list.

L'ensemble des transitions d'un automate A est codé par un vecteur ; si p 
vérifie les inégalités
() S p S an -- l, l'élément d'indice p de ce vecteur contient la liste des 
transitions d'origine p.
Ce vecteur est ainsi en Caml de type (char * int) list vect .

Pour définir un automate A, on utilise le type enregistrement (type produit) 
suivant :

type automate = {an : int;
F : int list;
T : (char * int) list vect;

};;
dans lequel les champs (ou membres) correspondent :
0 pour an, au nombre d'états de A,
0 pour F, a la liste des états finals de A,
0 pour T, à l'ensemble des transitions de A.

L'automate Aex de la figure 4 peut être défini par :
let T_Aex = make_vect 3 [];;
T_Aex. (0) <-- [ ('a' , l)];

T_Aex.(l) <-- [('a',1); ('b',2)];;

let Aex = {an = 3 ; F = [2]; T = T_Aex};;
Fin des indications pour Caml

Indications pour Pascal
On ajoute les définitions suivantes aux définitions données plus haut :

const MAX_Q = 100;

type transition = RECORD

etiquette : char;
extremite : integer;
end;
type tab_int_Q = array[0 .. MAX_Q -- 1] of integer;
type tab_transition = array[0 .. MAX_STGMA -- 1] of transition;
type tab_tab_transition = array[0 .. MAX_Q -- 1] of tab_transition;

type automate = RECORD
an : integer;
an : integer;
F : tab_int_Q;
an : tab_int_Q;
T : tab_tab_transition;
end;
La constante MAX_Q donne le nombre maximum d'états des automates considérés.

Page 8 sur 14

Épreuve d'informatique 2013

Si p est un état d'un automate, une transition d'origine p est codée par un 
enregistrement de
type transition, le champ (ou membre) etiquette contenant l'étiquette de cette
transition et le champ ext remite le numéro de l'extrémité de cette même 
transition.

Si p est un état d'un automate, on représente l'ensemble des transitions 
d'origine p en utilisant
un tableau de type tab_transition (on ne codera que des automates déterministes 
avec
le type automate).

L'ensemble des transitions d'un automate est codé par un tableau de type
tab_t ab_transition, la case d'indice p de ce tableau contenant la liste des 
transitions
d'origine p.

Un automate déterministe A sera codé par un enregistrement de type automate 
dans lequel
les champs (ou membres) correspondent :

0 pour an, au nombre d'états de A ;

0 pour an, au nombre d'états finals de A ;

0 pour F, a un tableau contenant la liste des états finals de A ;

0 pour an, a un tableau donnant les nombres de transitions issues de chaque 
état ; plus
précisément, si p est compris entre () et an -- 1, an [p] contient le nombre de
transitions d'origine p ;

0 pour T, à l'ensemble des transitions de A.

L'automate Aex de la figure 4 peut être défini par une variable Aex de type 
automate avec
les instructions :

Aex.an := 3;

Aex.an := 1;

Aex.F[0]:= 2;

Aex.an[0] = 1;
Aex.T[0][0].etiquette := 'a';
Aex.T[0][0].extremite := 1;
Aex.an[1] := 2;
Aex.T[1][0].etiquette := 'a';
Aex.T[1][0].extremite := 1;
Aex.T[1][1].etiquette .= 'b',
Aex.T[1][1].extremite := 2;

Aex.an[2] := 0;
Fin des indications pour Pascal

Soit A un automate déterministe sur un alphabet 2.

Cl 11 -- Il s'agit de savoir si un état est final ou non. On rappelle qu'un 
état est identifié
avec son numéro.
Caml : Écrire en Caml une fonction nommée est_f inal telle que si :

0 A, de type automate, code l'automate A,

0 p est un entier codant un état de A,
alors est_final A p renvoie le booléen true si p est un état final de A et false
sinon. Indiquer la complexité de cette fonction.
Pascal : Écrire en Pascal une fonction nommée est_f inal telle que si :

0 A, de type automate, code l'automate A,

0 p, de type integer, contient un état de A,
alors est_f inal (A, p) renvoie un booléen qui vaut true si p est un état final 
de A
et f al se dans le cas contraire. Indiquer la complexité de cette fonction.

Page 9 sur 14

Épreuve d'informatique 2013

Cl 12 -- On suppose que p est un état et x une lettre ; on veut connaître 
l'état q atteint à
partir de l'état p par la transition d'étiquette x si cette transition existe.
On rappelle que le cardinal de l'alphabet est majoré par une constante (égale à 
26).
Caml : Écrire en Caml une fonction nommée et at_suivant telle que si :

0 A, de type automate, code l'automate A,

0 p est un entier codant un état de A,

0 x est une lettre appartenant à 2,
alors et at_suivant A p x renvoie un entier codant l'état q tel que (p, x, q) 
soit
une transition de A si cette transition existe et -- 1 sinon. Indiquer la 
complexité de cette
fonction.
Pascal : Écrire en Pascal une fonction nommée et at_suivant telle que si :

0 A, de type automate, code l'automate A,

0 p, de type integer, contient le numéro d'un état de A,

0 x, de type char, contient une lettre appartenant à 2,
alors et at_suivant (A, p, x) renvoie une valeur de type integer contenant
l'état q tel que (p, x, q) soit une transition de A si cette transition existe 
et --1 sinon.
Indiquer la complexité de cette fonction.

CI 13 -- Il s'agit de déterminer l'état, s'il existe, qui est extrémité du 
calcul dont
l'origine est l'état initial et dont l'étiquette est un mot donné.
Caml : Écrire en Caml une fonction nommée execut ion telle que si :

0 A, de type automate, code l'automate A,

0 u, de type string, code un mot M sur 2,
alors exe cut ion A u renvoie un entier codant l'état q qui est l'extrémité du 
calcul
dont l'origine est l'état initial et dont l'étiquette est M, si q existe, et 
--1 sinon. Indiquer
la complexité de cette fonction.
Pascal : Écrire en Pascal une fonction nommée execut ion telle que si :

0 A, de type automate, code l'automate A,

0 u, de type tab_char, contient un mot M sur Z,

0 lu, de type integer, contient la longueur de u,
alors execution (A, u, lu) renvoie une valeur de type integer donnant l'état
q qui est extrémité du calcul dont l'origine est l'état initial et dont 
l'étiquette est M, si q
existe, et -- 1 sinon. Indiquer la complexité de cette fonction.

CI 14 -- Il s'agit de savoir si un mot est reconnu ou non par un automate.
Caml : Écrire en Caml une fonction nommée reconnait telle que si :
0 A, de type automate, code l'automate A,
0 u, de type string, code le mot M sur 2,
alors reconnait A u renvoie le booléen true si le mot u est reconnu par A et
f al 5 e sinon. Indiquer la complexité de cette fonction.
Pascal : Écrire en Pascal une fonction nommée reconnait telle que si :
0 A, de type automate, code l'automate A,
0 u, de type tab_char, contient le mot M sur Z,
0 lu, de type integer, contient la longueur de u,
alors reconnait (A, u, lu) renvoie le booléen true si le mot u est reconnu par
A et f al 5 e sinon. Indiquer la complexité de cette fonction.

Page 10 sur 14

Épreuve d'informatique 2013

CI 15 -- On considère un automate A déterministe complet sur un alphabet E, un 
état
p de A et une lettre x de 2. L'objectif de la question est de concevoir une 
fonction
permettant de modifier l'extrémité de la transition d'origine p et d'étiquette 
x.

Caml: On considère une liste, nommée trans, de type (char * int) list,
codant l'ensemble des transitions d'origine p. Écrire en Caml une fonction
remplace telle que, si :

0 x code la lettre x,

0 q code un état de A,

alors remplace x trans q renvoie une liste identique a trans sauf que le
couple contenant l'étiquette x est remplacé par le couple (x, q) . Indiquer la
complexité de cette fonction.

Pascal : On considère un tableau, nommé trans, de type tab_transition,
codant l'ensemble des transitions d'origine p. Écrire en Pascal une fonction
remplace telle que, si :

0 x, de type char, contient la lettre x,

0 q, de type intege r, contient un état de A,

alors remplace (x, trans, q) renvoie un tableau de type tab_transition
identique a trans sauf que le couple contenant l'étiquette x est remplacé par le
couple (x , q) . Indiquer la complexité de cette fonction.

Quatrième partie : utilisation d'automates.
On considère un mot m sur 2 : m : mOm1...ml(m) _ 1.

Cl 16 -- Dessiner un automate déterministe comportant [(m) + 1 états 
reconnaissant le
langage réduit au seul mot m. On note Am cet automate.

Cl 17 -- Il s'agit de construire l'automate Am en langage de programmation.

Caml : Écrire en Caml une fonction nommée aut omat e_de_mot telle que, si m, de
type string, code le mot m, alors aut omate_de_mot m renvoie un résultat de
type automate codant l'automate Am.
Pascal : Écrire en Pascal une fonction nommée aut omat e_de_mot telle que, si :

0 m, de type tab_char, contient le mot m,

. lm, de type intege r, contient la longueur de m,
alors aut omat e_de_mot (m, im) renvoie un résultat de type automate codant
l'automate Am.

El 18 -- Il s'agit d'utiliser l'automate Am pour déterminer si un mot M sur 2 
est préfixe
du mot m.

Caml : Écrire en Caml une fonction nommée est_prefixe telle que, si m et u, de
type string, codent les mots m et u, alors est_prefixe m il renvoie le booléen
t rue quand u est préfixe de m et f al se dans le cas contraire.

On utilisera les fonctions aut omat e_de_mot et execution.

Page 11 sur 14

Épreuve d'informatique 2013

Pascal : Écrire en Pascal une fonction nommée e st_pref ixe telle que, si :
0 m et u, de type tab_char, contiennent les mots m et u,
. lm et lu, de type integer, contiennent les longueurs de m et u,
alors est_prefixe (m, lm, u, lu) renvoie le booléen true quand u est
préfixe de m et f al se dans le cas contraire.
On utilisera les fonctions aut omat e_de_mot et execution.

CI 19 -- On s'intéresse à présent au langage composé des mots dont m est 
suffixe. On
le note LSm. Montrer que ce langage est rationnel.

CI 20 -- Expliquer comment on peut modifier l'ensemble des transitions de Am 
pour
obtenir un automate non déterministe reconnaissant LSm. On note ASm cet 
automate.
On considère le cas où 2 = {a, b} et m = ab. Dessiner l'automate ASab.

CI 21 -- Déterminiser l'automate ASab dessiné a la question précédente. On 
utilisera
pour cela un algorithme de déterminisation d'automate.

Soit t un texte et m un motif. On note DSm un automate déterministe complet 
reconnaissant
le langage LSm ; on suppose que DSm a un seul état final.

CI 22 -- Décrire les principes d'un algorithme utilisant l'automate DSm pour 
résoudre

le probléme (P). L'algorithme devra avoir une complexité de l'ordre de la 
longueur
de t. Justifier la validité de cet algorithme avec soin.

CI 23 -- Il s'agit de programmer l'algorithme précédent.
Caml: On suppose que l'on dispose d'une fonction DS telle que, si m est de type
string, alors DS m renvoie un résultat de type automate codant l'automate DS,".
En utilisant cette fonction, écrire en Caml une fonction nommée pos it ions 3 
telle que,
si m et t, de type string, codent le motif m et le texte t, alors positions3 m t
résout le probléme (P), c'est-à-dire renvoie une liste contenant les positions 
du motif
m dans le texte t.
Pascal : On suppose que l'on dispose d'une fonction DS telle que, si :
0 m, de type tab_char, contient le mot m,
. lm, de type integer, contient la longueur de m,
alors DS (m, im) renvoie un résultat de type automate codant l'automate DS,".
En utilisant cette fonction, écrire en Pascal une fonction nommée posit ions3 
telle
que, si :
0 m et t, de type tab_char, contiennent m et t,
. lm et lt, de type integer, contiennent les longueurs de m et t,
alors positions3 (m, lm, t, lt) résout le probléme (P), c'est-à-dire renvoie
un résultat de type pile contenant, dans le champ nb, le nombre de positions de 
m
dans tet, dans le champ table, la liste des positions du motif m dans le texte 
t.

Page 12 sur 14

Épreuve d'informatique 2013

Cinquième partie : automate des suffixes

Le but de cette la partie est d'écrire un automate déterministe complet, avec 
un seul état final,
reconnaissant le langage LSm.

On considère un alphabet 2 et un mot m : moml...ml(m) _1 sur 2.

On note Pref(m) l'ensemble des préfixes de m.
Soit hm l'application de 2* dans Pref(m) définie par : pour tout mot a sur 2 , 
hm(u) est le plus
long mot a la fois suffixe de a et préfixe de m.

Cl 24 -- Préciser hm(u) pour tout mot a quand m est réduit à une seule lettre x 
EUR 2.

On revient au cas général : m est un mot quelconque sur 2.

Cl 25 -- Soit a E E*. Montrer que a & LSm si et seulement si hm(u) : m.
CI 26 -- Préciser hm(8). Préciser hm(u) quand a est un préfixe de m.
Cl 27 -- Montrer que hm(ux) : hm(hm(u)x) pour tout mot a et toute lettre x.

On définit un automate déterministe et complet sur l'alphabet Z, noté Sm, de la 
façon
suivante :
0 les états de Sm sont les préfixes de m,

. l'état initial de Sm est 8,
. l'état final de Sm est m,
0 pour tout préfixe a de m et toute lettre x, (n, x, hm(ux)) est une transition 
de Sm et Sm
n'admet pas d'autres transitions que les transitions de cette forme.
Convention : on numérote les états de Sm ; l'état initial sest noté () et pour 
i compris entre l et
l(m), le préfixe moml...mi_1 est noté i.

Cl 28 -- On suppose que l'on a 2 = {a, b}. Dessiner l'automate Sg.
Indication : cet automate n'a qu'un seul état, noté 0.

El 29--On suppose que l'on a 2 = {a, b} et on considère le mot ab. Dessiner
l'automate S ab en représentant les états par leurs numéros.

Indication : cet automate a trois états, les états EUR, a, ab, numérotés O, 1 
et 2.

Cl 30-- On considère l'automate Sm et un mot a sur 2 ; on note 5 la fonction de
transition de Sm. Montrer l'égalité 5*(8, a) = hm(u).

CI 31 -- Montrer que Sm reconnait le même langage que DSm, c'est-à-dire LSm.

Page 13 sur 14

Épreuve d'informatique 2013

Soit m un mot sur 2 et x une lettre de 2. On pose m' = mx. On note h = hm et h' 
= hm'. On

admet les propriétés suivantes de la fonction h'.

Soit u' un préfixe de m' et y une lettre.
(i) Si u' est préfixe de m et u' 75 m : h'(u'y) = h(u'y).
(ii) Si u' = m : h'(my) = h(my) quand y 75 x et h'(mx) = mx.
(iii) Si u' = m' : h'(m'y) = h'(h(mx)y).

CI 32 -- Donner des règles simples de construction pour passer de Sm a Sm'.

Cl 33 -- On considère le cas 2 = {a, b} et le mot aba. Illustrer les règles 
énoncées à la
question précédente en traçant l'automate S abc, a partir de l'automate S ab 
obtenu à la

question CI 29.

Cl 34 -- Il s'agit de programmer la fonction DS pour l'alphabet 2 = {a, b}.
Caml : Écrire en Caml une fonction nommée DS telle que, si m, de type string,
code un mot m, alors DS m renvoie un résultat, de type automate, codant
l'automate S.... On supposera si nécessaire qu'on a défini une constante entière
MAX_LONGUEUR et que les mots considérés ont au plus MAX_LONGUEUR lettres.
Pascal : Écrire en Pascal une fonction nommée DS telle que, si :

0 m, de type tab_char, contient le mot m sur Z,

. lm, de type integer, contient la longueur de m,
alors DS (m, lm) renvoie un résultat, de type automate, codant l'automate S....

Cl 35 -- On revient a un alphabet 2 quelconque. Donner la complexité de la 
fonction
positions3.

Page 14 sur 14

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



Mines Informatique MP 2013 -- Corrigé
Ce corrigé est proposé par Charles-Pierre Astolfi (ENS Cachan) ; il a été relu 
par
Guillaume Batog (Professeur en CPGE) et Benjamin Monmege (ENS Cachan).

Ce sujet étudie divers algorithmes permettant de trouver toutes les positions 
d'une
chaîne de caractères dans un texte. Il est composé de cinq parties 
indépendantes, trois
axées sur la programmation et deux traitant d'automates.
· La première partie demande d'implémenter un algorithme naïf en programmation 
impérative. Les questions sont assez simples et de difficulté croissante.
· La deuxième partie est une amélioration de l'algorithme en supprimant 
certaines comparaisons inutiles. Cette partie est plutôt facile une fois que 
l'on a
compris l'amélioration proposée. Le sujet fait toujours travailler sur un 
exemple
avant d'aborder les questions plus difficiles.
· La troisième partie porte sur une implémentation des automates, exercice très
classique probablement déjà traité en cours.
· La quatrième partie fait programmer un nouvel algorithme basé sur l'automate
(déterministe et complet) reconnaissant le langage des mots de suffixe m.
· La cinquième partie propose une méthode pour construire efficacement 
l'automate des suffixes précédent. Cette partie comporte des questions 
théoriques.
C'est un sujet long où la programmation prend une place prépondérante. Il était
tout à fait possible de rester bloqué pendant les trois heures de l'épreuve sur 
les
questions de programmation. La complexité des fonctions programmées est 
systématiquement demandée.

Indications
Partie I
2 Il s'agit de donner la complexité en nombre de comparaisons de caractères.
3 Utiliser la question 1 pour toutes les positions s possibles.
Partie II
5 Parcourir m de gauche à droite en respectant l'invariant suivant : à la fin de
l'itération i, le tableau D est correct pour le préfixe de longueur i.
6 Noter que c n'apparaît pas dans le motif.
8 À quoi correspond D(numero(clé)) ?
10 De combien au maximum  peut-il augmenter à chaque étape ? Dans quel cas ?
Partie IV
19 Donner une expression rationnelle qui décrit LSm .
20 Il faut rajouter des transitions à l'état initial.
22 Que signifie passer par l'état final lorsqu'on exécute un mot sur l'automate 
DSm ?
Partie V
24 Les préfixes d'un mot x à une lettre sont  et x.
26 Le seul suffixe de  est .
27 Montrer d'abord que hm (hm (u)x) est à la fois un suffixe de ux et un 
préfixe de m,
puis montrer qu'il s'agit du plus long mot vérifiant cette propriété.
30 Raisonner par récurrence sur la longueur de u.
31 On peut raisonner par équivalence en utilisant les questions 25 et 30.
34 Construire successivement les automates DSm0 , DSm0 m1 , . . . , DSm dans la 
même
table de transition de taille l(m) en utilisant les règles de la question 32.

I. Algorithme simple
1 On compare lettre par lettre m à ts · · · ts+l(m)-1 (la sous-chaîne de t de 
longueur l(m) commençant en s). Si on rencontre un indice i tel que mi 6= ti , 
le motif
ne se trouve pas dans t à la position s et on peut renvoyer false tout de 
suite, sans
exécuter d'autre comparaison. Pour faire cela, on utilise une référence 
continue,
initialisée à true et qui devient fausse si et seulement s'il existe i tel que 
mi 6= ti .
let est_present m t s =
let continue = ref true
and i = ref 0 in
while (!continue && !i < string_length m) do
if m.[!i] != t.[s + !i] then continue := false;
incr i;
done;
!continue;;
En Caml, les fonctions incr et decr sont standard et définies par
let incr r = r := (!r) + 1 and decr r = r := (!r) - 1;;
2 Dans le pire des cas, m et ts · · · ts+l(m)-1 sont égaux et on doit effectuer 
l(m)
comparaisons pour s'en assurer. En revanche si m0 6= ts , on peut s'arrêter 
tout de
suite après cette première comparaison.
est_present effectue toujours au moins 1 et au plus l(m) comparaisons.
L'énoncé parle de la complexité sans la définir. Dans les problèmes sur les
chaînes de caractères, il est sous-entendu qu'il s'agit de complexité en nombre
de comparaisons de caractères.
3 On utilise une référence pos vers une liste pour stocker les positions de 
toutes les
occurrences de m dans t. Une position de m ne peut évidemment pas être 
strictement
supérieure à l(t) - l(m).
let positions m t =
let pos = ref [] in
for i=((string_length t) - (string_length m)) downto 0 do
if est_present m t i then pos := i :: (!pos);
done;
!pos;;
Il faut parcourir le texte de droite à gauche pour obtenir la liste des 
positions
dans l'ordre croissant.
4 Chacun des l(t) - l(m) + 1 passages dans la boucle peut effectuer dans le 
pire des
cas l(m) comparaisons.
Dans le pire des cas, positions effectue l(m) (l(t) - l(m) + 1) comparaisons.
Cette complexité est atteinte lorsque tous les indices entre 0 et l(t) - l(m) 
sont
des positions du motif, par exemple si le texte est au (a répété u fois) et le 
motif av
avec u > v.

II. Une amélioration de la méthode précédente
5 On parcourt le motif m de gauche à droite, et pour tout 0 6 i < l(m) on met
à jour D pour indiquer que m apparaît à la position i. On maintient l'invariant 
de
boucle suivant : à la fin de l'itération i, le tableau D est correct pour la 
sous-chaîne
m0 · · · mi .
let calcul_D m nbSigma =
let D = make_vect nbSigma (-1) in
for i=0 to (string_length m) - 1 do
D.(numero m.[i]) <- i
done;
D;;
On effectue l(m) itérations et chaque itération prend un temps constant (mettre
à jour un tableau), d'où
calcul_D est de complexité linéaire en l(m).
6 Puisque c n'apparaît pas dans m1 , alors pour toute position  telle que 5 6  
6 8,
le texte t1 ne contient pas d'occurrence de m1 à la position . Sinon, cela 
signifierait
qu'on a trouvé une occurrence de m1 qui contient c, ce qui est impossible.
La prochaine valeur de  est 9 qui n'est pas une position de m1 dans t1 .
7 Lorsque  = 9, la clé est la lettre de t1 qui se trouve à l'indice 13, 
c'est-à-dire a.
=9

9
a
b

10
b
b

11
b
a

12
a
a

13
a

14
b

Comme la dernière lettre de m1 est aussi un a, on avance  d'une lettre et donc
 = 10. C'est la position d'une occurrence de m1 dans t1 .
 = 10

10
b
b

11
b
b

12
a
a

13
a
a

14
b

Lorsque  = 10 la clé est la lettre de t1 en position 14. Étant donné que la 
dernière
occurrence de b dans m1 est en position 2 on devrait avancer la fenêtre de 3 
positions,
soit  = 13. Mais l'énoncé suppose que  6 l(t1 ) - l(m1 ) = 11, le décalage n'est
donc plus possible. Il n'y a aucune occurrence de m1 dans t1 après cette 
position.
8 Il faut avancer la fenêtre de recherche de sorte que la clé = t+l(m) soit 
directement en regard de la dernière occurrence de clé dans le motif, soit à la 
position
d = D(numero(clé)) dans le motif. Ainsi, les lettres du texte et du motif 
coïncident à
la position  + l(m) si on effectue un décalage de  + l(m) - ( + d) = l(m) - d. 
On remarque que ce décalage est possible si +l(m)-d 6 l(t)-l(m) soit +2l(m) 6 
l(t)+d,
ce qui est le cas lorsque  + 2l(m) < l(t) (d peut valoir -1.)
La position suivante de la fenêtre est  + l(m) - D(numero(t+l(m) )).