Mines Informatique optionnelle MP 2018

Thème de l'épreuve Recherche de motifs
Principaux outils utilisés algorithmes de textes, automates
Mots clefs knuth-morris-pratt, motifs

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


CONCOURS MINES
COMMUN... PONTS
..

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ETIENNE, MINES NANCY,
IMT Atlantique, ENSAE PARISTECH.

Concours Centrale-Supélec (Cycle International),
Concours Mines--Télécom, Concours Commun TPE / EIVP.

CONCOURS 2018
EPREUVE D'INFORMATIQUE MP

Durée de l'épreuve : 3 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement les candidats de la filière MP.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

INFORMATIQUE - MP

L'énoncé de cette épreuve comporte 8 pages de texte.

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.

L'épreuve est composée d'un unique problème, comportant 24 questions. Après un
préliminaire et des définitions générales, ce problème est divisé en 4 parties; 
la partie 2
est indépendante de la partie 1.

Le but du problème est d'étudier des algorithmes permettant de rechercher 
efficacement
des occurrences d'une ou plusieurs chaînes de caractères (appelées motifs) a 
l'intérieur
d'une longue chaîne de caractères.

Préliminaire concernant la programmation

Il faudra coder des fonctions a l'aide du langage de programmation Caml, tout 
autre
langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire 
appel a d'autres
fonctions définies dans les questions précédentes; il pourra aussi définir des 
fonctions
auxiliaires. Quand l'énoncé demande de coder une fonction, il n'est pas 
nécessaire de
justifier que celle--ci est correcte, sauf si l'énoncé le demande 
explicitement. Enfin, si les
paramètres d'une fonction a coder sont supposés vérifier certaines hypothèses, 
il ne sera
pas utile dans l'écriture de cette fonction de tester si les hypothèses sont 
bien vérifiées.

Dans les questions du problème, un même identificateur écrit dans deux polices 
de
caractères différentes désignera la même entité, mais du point de vue 
mathématique
pour la police en italique (par exemple 71) et du point de vue informatique 
pour celle en
romain avec espacement fixe (par exemple 11).

Définitions générales

On fixe un alphabet 2, c'est--à--dire un ensemble fini, dont les éléments sont 
appelés
symboles. On note A > 0 le nombre d'éléments de cet alphabet, et on suppose que 
cette
taille À est disponible depuis les fonctions Caml a implémenter sous la forme 
d'une
constante globale lambda. Par exemple :

let lambda = 5;;

On supposera que les éléments de E sont ordonnés, par exemple par ordre 
alphabétique,
et on les note dans l'ordre oz0 < < oz,\_1. On dit que le code d'un symbole oz 
de
l'alphabet est l'entier @ tel que a = oz,- (0 < 2' EUR À -- 1).

Une chaîne de caractères s est une suite finie non vide u1 . . . U,, de 
symboles de E. La
longueur de s est son nombre de symboles, c'est--à--dire, ici, lîî. On 
représentera en Caml
les chaînes de caractères par des listes d'entiers (int list), chaque entier 
étant le code
d'un symbole. Ainsi, si l'alphabet est 2 = {a, b, c}, dans cet ordre, la chaîne 
de caractères
<< abac >> sera représentée par la liste EO; 1; O; 2]. En particulier, on 
n'utilisera jamais
le type string de Caml.

1 Recherche naïve d'un motif

Une occurrence d'une chaîne de caractères s = oq . . . ca, (aussi appelée un 
motif) dans
une autre chaîne de caractères t = & . . . fin est un entier naturel y avec 1 < 
@; < 71 tel que,
pour tout entier z' tel que 0 < 2' < [<: -- 1, ozk_i = By_i. En d'autres 
termes, l'occurrence
indique la position du dernier caractère du motif s au sein de la chaîne de 
caractères t
(les positions commençant a 1).

Par exemple, si 2 = {a, b,c, d,c}, s est le motif « abc » et t la chaîne de 
caractères
<< abcabcdababcdabcdabde >>, il y a quatre occurrences de s dans t, a savoir :

--3
--6
--12
--16

D 1 -- Soit s,t deux chaînes de caractères. Est--il possible d'avoir deux 
occur--
rences @; et y' de 3 dans t avec y < y' et y 2 y' -- k + 1 ? Si oui, donner un
exemple; sinon, le prouver.

D 2 * Quel est le nombre maximal d'occurrences d'un motif de longueur lc
dans une chaîne de caractères de longueur n > [EUR ? Prouver que cette borne
est toujours respectée, et que cette borne est atteinte.

D 3 -- Programmer en Caml une fonction longueur : 'a list --> int qui
prend en entrée une liste et qui renvoie la longueur de cette liste. Quelle est
la complexité de cette fonction, en terme du nombre 71 d'éléments de la liste ?

D 4 * Programmer en Caml une fonction int list --> int list --> bool
prenant en entrée deux listes d'entiers 3 et t codant des chaînes de caractères
et testant si 5 est un préfixe de t. Quelle est la complexité de cette fonction,
en terme des longueurs k et n de s et t?

D 5 = À l'aide des fonctions longueur et prefixe, programmer une fonction
recherche_naive : string --> string --> int list, la plus directe possible,
telle que si 3 est un motif et t une chaîne de caractères, recherche_naive s t
renvoie la liste des entiers @; qui sont des occurrences de s dans t, triés par
ordre croissant.

D 6 -- Quelle est la complexité de la fonction recherche_naive, en terme des
longueurs k et n de ses deux paramètres s et t?

2 Automates finis déterministes à repli

Un automate fini déterministe a repli (ou AFDR) sur l'alphabet E est un 
quadruplet
A= (k,F,ô,p) tel que:

-- k: E N est un entier strictement positif représentant le nombre d'états de A;
l'ensemble des états de A est QA = {O, 1, . . . , k -- 1} et 0 est appelé 
l'état initial.

-- F Ç QA est un ensemble d'états, appelés finale.

-- 5 : QA >< E --> QA est une fonction partielle de transition (c'est--à--dire, 
une fonction
dont le domaine de définition est un sous--ensemble de QA >< E) ; on impose que
5(0, oz) soit défini pour tout oz EUR X].

-- ,o : QA \ {O} --> QA est une application (c'est--à--dire, une fonction 
totale), appelée
fonction de repli, telle que pour tout q EUR 62,4 avec q # O, p(q) < q. On 
prolonge ,o
en convenant p(0) = 0.

Un AFDR est représenté en Caml par le type enregistrement suivant :

type afdr = {
final : bool vect;
transition : int vect vect;
repli: int vect;

}; ;

où :
-- final est un tableau de taille le de booléens tel que si q EUR 62,4, final. 
(q) contient

true si et seulement si q E F;

-- transition est un tableau de taille le de tableaux de taille À d'entiers, 
tel que si
q EUR QA et Oz,- E E de code i, transition. (q) . (i) contient --1 si ô(q, oa) 
n'est pas
défini, et contient 5 (q, a,) sinon;

-- repli est un tableau de taille le d'entiers tel que repli. (0) contient 0 et 
repli. (q)
pour q EUR 62,4 \ {0} contient p(q).

On observe que le type afdr ne code pas explicitement la valeur de le, mais le 
est par
exemple la longueur du tableau final.

On dessine un AFDR de manière similaire au dessin d'un automate fini 
déterministe
classique, en faisant figurer en pointillés une flèche indiquant les replis 
d'un état vers un
autre. Les états finals sont figurés par un double cercle.

Considérons par exemple l'automate A1 = (k1,F1,51, m) sur l'alphabet E = {a,b}
défini par lEUR1 = 4, F1 = {3}, et les fonctions 51 et p1 suivantes :

À L
q 51(q,a) 51(q,b) q [AM)
0 1 0 0

1 2 1 0
2 3 2 0
3 3 1

A1 peut être dessiné comme suit :

D 7 -- Soit A = (k,F, 5, p) un AFDR. Pour tout q EUR 62,4, on note pj(q)
pour j E N l'application répétée j fois de la fonction p a q, c'est--à--dire

p(p(. . . (p(q)) . .)) Par convention, pour tout état q, on note pO(q) = q.
\_,-/

j fois
Montrer que pour tout q EUR QA, pour tout Oz E E, il existe j > 0 tel que
5(pj(q), oz) est défini.

On dit qu'un AFDR A = (k, F, 5, p) accepte un mot u = 211 . . . up E 2* s'il 
existe une
suite finie q0,qî,q1,qê,q2, . . . ,qé,_1,qp_1,qê,qp d'états de A avec :

=qo=0;

-- pour tout 1 g i < p, q; = pÏ(q,-_1) avecj ; Ole plus petit entier tel que 
ô(pj(qi_1), u,)
est défini;

-- pour tout 1 < 2 < p, q,- = 5(q£,u,);
-- q,, E F.

Le langage accepté par un AFDR est l'ensemble des mots acceptés.
Ainsi, A1 accepte le mot << ababa >>, comme le montre la suite d'états parcourus

0, 0,1, 1,2, 2,3, 1,2, 2,3.

On remarque qu'un AFDR dont la fonction de transition 5 est définie partout 
peut être
vu comme un automate fini déterministe classique, et que cet automate fini 
déterministe
est complet (ce qui signifie précisément que sa fonction de transition est 
définie partout).
En effet, les puissances non nulles de la fonction de repli ,0 ne sont 
utilisées que si la

fonction de transition n'est pas définie. On appellera un tel automate fini 
déterministe
complet un AFDC.

I:] 8 -- Construire (sans justification) un AFDC sur l'alphabet {a, b} recon--
naissant le même langage que A1 et ayant le même nombre d'états que A1.

D 9 -- Donner (sans justification) une description concise du langage reconnu
par l'AFDR A1.

D 10 = Programmer en Caml une fonction copie_afdr : afdr --> afdr qui
renvoie un nouvel AFDR identique a l'AFDR fourni en entrée7 mais ne
partageant aucune donnée avec lui. On pourra utiliser la fonction standard
copie_vect : 'a vect --> 'a vect qui renvoie un nouveau tableau contenant
les mêmes éléments que les éléments d'entrée et s'exécute en un temps
proportionnel au nombre d'éléments du tableau d'entrée.

D 11 f En s'inspirant de la réponse aux questions 7 et 8, et en utilisant la
fonction copie_afdr, programmer une fonction enleve_repli : afdr --> afdr
telle que, si A est un AFDR, enleve_repli A renvoie un AFDO reconnaissant
le même langage. On souhaite que cette fonction s'exécute en temps O(k >< À),
où k: est le nombre d'états de A et A est la taille de l'alphabet. Montrer que
la fonction proposée a bien cette complexité.

D 12 -- Étant donné un AFDC A et un mot u = ... . . .un sur E, proposer un
algorithme (pas un programme Caml) en 001) pour calculer la liste triée des
entiers z' avec 1 < 2' < n tels que le préfixe ... . . .ui de u est accepté par 
A.

D 13 * Implémenter en Caml l'algorithme de la question précédente : pro--
grammer une fonction occurrences : afdr --> int list --> int list telle
que, si A est un AFDC et liste une liste d'entiers j1, . . . ,jn codant des 
sym--
boles ozjl, . . . ,osz de l'alphabet î], occurrences A liste renvoie la liste 
des
entiers l' avec 1 < i < 71 tels que le mot 0431 . . . O[ji est reconnu par A. 
Quelle
est la complexité de cette fonction en terme de la longueur n de la liste
d'entiers, du nombre % d'états de l'automate A et de /\ ?

3 Automate de Knuth--Morris--Pratt

L'automate de KnuthäWorm'æPmtt (ou automate KMP) associé à un motif 3 = u1 . . .

sur l'alphabet E est un AFDR AËMP = (k', F, 5, p) sur 2 avec :

H=k+L
F = {k}.

Pour tout 1 < 2' < k, 5(i--1,u,-) =i et, pour tout 04 EUR E\{u1}, 5(O,a) = O; 
aucune

autre transition n'est définie.

Pour tout 1 < 2' < k, p(z') est le plus grand entier 0 { j < z' tel que ... . . 
.Uj est un

sufiîæe de u1 . . . ui.

On peut ainsi vérifier que l'automate A1 de la question précédente est 
l'automate KMP
associé a « aba >>sur l'alphabet E = {a, 6}.

D 14 -- Construire (sans justification) l'automate KMP associé à << ababc >> sur
l'alphabet {a,b,c}.

D 15 -- Donner (sans justification) une description concise du langage reconnu
par l'AFDR AÏÎMP pour un motif s arbitraire.

D 16 * Montrer que si 5 = u1 . . .uk est un motif et (k + 1, F, 5, p) l'automate
KMP associé à 3, alors pour tout 1 < i < k, si j > 0 est le plus petit entier
tel que 5(p" (p(i -- 1)),u,) est défini (qui existe d'après la question 7), 
alors

...) = 6>,ui>.

D 17 -- En utilisant la caractérisation de la question 16, programmer une
fonction automate_kmp : int list --> afdr qui prend en entrée une liste
d'entiers s codant une chaîne de caractères s et qui renvoie l'AFDR AËMP .

D 18 -- Pour un motifs = 211 . . .uk et pour tout 1 < i < k, on note j,- le
plus petit entier tel que 5(pj(p(i -- 1)),u,-) est défini, comme a la question 
16.
Montrer que pour tout 1 < i EUR le, p(z') { p(z' -- 1) + 1 -- j,- et en déduire 
que
ZÏ=1ji est en O(kz)

D 19 -- Quelle est la complexité de la fonction automate_kmp en terme de la
longueur k: du motif s passé en argument et de À ? Prouver cette affirmation.

[' 20 -- En s'appuyant sur les fonctions Caml automate_kmp, enleve_repli
et occurrences, programmer une fonction Caml recherche_kmp : string -->
string --> int list telle que, si 5 est un motif de longueur k: et t une chaîne
de caractères, recherche_kmp s t renvoie la liste des occurrences y de s dans
t, triés par ordre croissant.

Quelle est la complexité de cette fonction en terme des longueurs [{ et n de s
et t et de À ? Comparer avec la complexité de la fonction recherche_naive
obtenue en question 6.

4 Ensemble de motifs et automates à repli arborescents

On considère maintenant l'AFDR A2 suivant, sur l'alphabet E = {a, b} :

D 21 * Donner (sans justification) une description concise du langage reconnu
par l'AFDR A2.

D 22 -- On considère l'alphabet E = {a, b, c}. Construire (sans justification)
un AFDR dont le langage reconnu est l'ensemble des mots dont un suffixe

est << baa >>, << bab » ou << bc ». Indication : on cherchera un AFDR tel que si
ô(q, &) est défini et q est non nul, alors 5(q, oz) > q.

On fixe maintenant un ensemble fini S de motifs. L'ensemble des occurrences de S

dans une chaîne de caractères t est l'ensemble des occurrences de chacun des 
motifs de S
dans t.

D 23 -- En utilisant la fonction recherche_kmp, programmer une fonction
recherche_dictionnaire_kmp : int list list --> int list --> int list qui
est telle que, si S est un ensemble fini de motifs codé comme une liste de 
motifs,
et t une chaîne de caractères, recherche_dictionnaire_kmp S t renvoie la
liste des occurrences @; d'un motif 3 E S dans t. On n'impose pas d'ordre
particulier sur cette liste, et on autorise les doublons.

Quelle est la complexité de cette fonction, en terme du nombre |S | de motifs,
de la longueur k maximale d'un motif, de A et de la longueur 71 de t?

E' 24 f En s'inspirant de l'automate A2, de la réponse a la question 22 et de
la partie 3, proposer une approche pour calculer efficacement les occurrences
d'un ensemble fini S de motifs dans une chaîne de caractères t. On ne demande

ni une formalisation complète de cette approche, ni une implémentation, mais
une stratégie générale et les grandes étapes nécessaires à la résolution du
problème. On pourra faire l'hypothèse, pour simplifier, que l'ensemble S ne
contient pas deux mots qui sont préfixes l'un de l'autre.

Quelles difficultés sont a prévoir dans l'implémentation ? Quelle complexité
peut--on espérer avec une telle approche, en terme du nombre |S | de motifs, de
la longueur [{ maximale d'un motif, de A et de la longueur 71 de t? Comparer
avec la complexité obtenue en réponse a la question précédente.

FIN DE L'ÉPREUVE

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



Mines Informatique optionnelle MP 2018 -- Corrigé
Ce corrigé est proposé par Martin Guy (ENS Lyon) ; il a été relu par Hugo Menet
(ENS Lyon) et Benjamin Monmege (enseignant-chercheur à l'université).

L'épreuve est divisée en quatre parties portant sur la recherche d'un motif s 
dans
une chaîne de caractères t.
· Le sujet commence par une introduction générale au problème et définit toutes
les notions nécessaires. Après avoir prouvé des propriétés basiques sur les 
motifs
et implémenté des fonctions Caml les manipulant (sous forme de liste), on étudie
un premier algorithme naïf de recherche de motif. Cette première partie permet
de vérifier que l'on maîtrise les bases de Caml et des études de complexité.
· La deuxième partie, indépendante de la première, présente les automates finis
déterministes à repli (AFDR). Les premières questions permettent de 
s'approprier la notion, qui se différencie subtilement des automates classiques 
au
programme. Il s'ensuit des implémentations en Caml, accompagnées de calculs
de complexité. C'est le moment de vérifier sa maîtrise des types en Caml.
· La troisième partie, la plus technique et la plus conséquente, introduit les 
automates de Knuth-Morris-Pratt, basés sur l'algorithme éponyme. On prouve
différentes propriétés utiles pour implémenter un algorithme de recherche de
motif plus efficace. Cette partie permet de vérifier les acquis en manipulation
de mots et en programmation.
· Enfin, on étend la recherche à un ensemble de motifs dans un dictionnaire S.
On utilise des AFDR reconnaissant plusieurs motifs, et on termine par une
nouvelle approche de reconnaissance pour un ensemble de motifs. La dernière
question, ouverte, est intéressante.
Ce sujet plutôt long propose un bon équilibre entre implémentation en Caml et
preuves sur les automates, ce qui en fait un très bon exercice technique.
Dans le corrigé, les codes sont écrits en OCaml plutôt qu'en Caml Light, comme
le demandait pourtant l'énoncé, car c'est le langage qui deviendra obligatoire 
aux
concours à partir de la session 2019.

Indications
Partie I
1 Trouver un contre-exemple où s apparaît deux fois dans t de sorte que les deux
occurrences se superposent dans t.
2 Sans se soucier des lettres dans s et dans t, quelles sont les positions où 
l'on peut
trouver le motif s dans t ?
4 Parcourir en même temps les deux listes s et t et comparer lettre par lettre.
Pour la complexité, séparer selon que k est plus petit ou plus grand que n.
5 Tester chaque position possible à l'aide de la fonction prefixe. Il y a une 
erreur
dans l'énoncé : les arguments en entrée sont de type int list et non string.
Partie II
7 Utiliser le fait que pour q  QA , on a (q) < q et qu'une suite d'entiers 
strictement
décroissante bornée devient stationnaire.
8 Commencer par redessiner les états et les transitions existantes. Ensuite, 
compléter l'automate avec les transitions manquantes en utilisant la 
caractérisation des
états de repli j (qi-1 ) avec j le plus petit entier tel que (j (qi-1 ), ui ) 
est défini.
10 Itérer sur chaque ligne pour copier la matrice de transitions.
11 Pour tout état q et tout symbole  où (q, ) n'est pas défini, utiliser la 
transition
depuis l'état de repli (q).
13 Utiliser une fonction auxiliaire récursive pour parcourir le motif u, en 
faisant
attention à l'ordre de reconstruction de la liste d'indices.
Partie III
14 Placer les états puis les transitions, et enfin calculer la fonction de 
repli  en
trouvant parmi les préfixes de s le plus grand suffixe possible étant aussi un 
préfixe.
On pourra faire un tableau où, pour chaque préfixe de s, on affiche le plus 
grand
suffixe possible.
16 Cette question comporte une erreur pour i = 1. Considérer i > 2. Remarquer 
que
le plus long suffixe u1 . . . uj de u1 . . . ui peut être vu comme le plus long 
suffixe
de u1 . . . ui-1 auquel on rajoute le symbole ui . Exhiber alors une récurrence.
17 Séparer le code en trois morceaux : définir les structures de données et 
initialiser
avec les bonnes valeurs ; calculer toutes les transitions ; puis calculer la 
fonction
de repli à l'aide de la caractérisation de la question 16.
18 Remarquer que pour j 6 i, j (i) 6 i - j et se servir du fait que (i - 1, ui 
) = i.
Pour la seconde partie de la question, faire apparaître une somme télescopique.
19 Calculer séparément la complexité de chaque morceau de code et utiliser le 
résultat de la question 18.
Partie IV
23 Il suffit d'appeler recherche_kmp sur chaque élément du dictionnaire et de 
rassembler les résultats dans une seule et même liste.
24 Plutôt que de traiter chaque motif indépendamment comme en question 23, créer
un automate à l'image de la question 22 pour ensuite y trouver les occurrences.

I. Recherche naïve d'un motif
1 Soient s et t deux chaînes de caractères sur l'alphabet  = {a, b}. En prenant
s = abba et t = abbabba, on trouve des occurrences de s dans t aux positions y 
= 4
et y  = 7. La chaîne s est de longueur k = 4, ce qui donne y  - k + 1 = 4. 
Ainsi,
Il est possible d'avoir deux occurrences y et y 
de s dans t avec y < y  et y > y  - k + 1.
2 Soient s = 1 . . . k et t = 1 . . . n deux chaînes de caractères sur un 
alphabet .
Par définition, une occurrence indique la position du dernier caractère du 
motif s
dans la chaîne t. Ce motif s étant de longueur k, la première occurrence de s 
ne peut
se trouver avant la position k. On peut trouver d'autres occurrences aux 
positions
k + 1, k + 2 . . . et ce jusqu'à la position n. Par conséquent, on peut en 
trouver
au maximum n - k + 1. Ainsi,
Le nombre maximal d'occurrences d'un motif de longueur k
dans une chaîne de longueur n > k est n - k + 1.
Cette borne est atteinte dans le cas où i = a pour tout i 6 k et j = a pour tout
j 6 n (on trouve alors une occurrence pour chaque position possible). Autrement 
dit,
La borne est atteinte si s et t ne sont constitués que du même symbole.
3 On calcule récursivement la taille de la liste en comptant 1 à chaque élément 
vu.
let rec longueur l = match l with
| [] -> 0
| t::q -> 1 + longueur q;;
Le nombre C(n) d'appels récursifs lors de l'appel de longueur avec une liste de
longueur n  N vérifie la définition par récurrence :

C(0) = 0
n  N , C(n) = 1 + C(n - 1)
On a donc C(n) = n, pour tout n  N. À chaque appel de longueur, on exécute
un nombre constant d'opérations élémentaires. Ainsi,
La fonction longueur a une complexité en O(n).
4 On parcourt récursivement les deux listes représentant les chaînes de 
caractères s
et t simultanément. On arrête le parcours dès que deux lettres de s et t sont 
différentes. On conclut également négativement dans le cas où le motif s est 
plus long
que la chaîne t, auquel cas s ne peut pas être un préfixe.
let
|
|
|

rec prefixe s t = match s,t with
[], _ -> true
si::q, [] -> false
si::q, ti::v -> (si = ti) && (prefixe q v);;

Séparons l'étude de la complexité de prefixe s t en deux cas, en notant k et n
les longueurs respectives de s et t. Si k > n, on parcourt chaque symbole de t, 
ce qui
fait n opérations. Si k 6 n, on fait au plus k opérations. Dans tous les cas,
La fonction prefixe a une complexité en O(min(k, n)).

5 La recherche la plus directe est de tester, pour chaque position possible i 
dans t,
si s est un préfixe de ti . . . tn . Si tel est le cas, on a trouvé une 
occurrence de s dans t
à la position i + k - 1. Ainsi, la première occurrence testée est celle en 
position k.
Pour cela, on implémente une fonction auxiliaire récursive parcourt, de type
int list -> int list -> int list, permettant de parcourir le texte t, tout en
maintenant la position i de la première lettre. Initialement, t est le texte 
complet
et i vaut k. Pour chaque position dans t, si s est un préfixe, on garde la 
position,
et dans tous les cas on appelle récursivement la fonction en incrémentant i. La 
liste
des occurrences est ainsi construite récursivement, dans l'ordre croissant.
let recherche_naive s t =
let k = longueur s in
let rec parcourt t i = match t with
| [] -> []
| _::q -> if prefixe s t then
i::(parcourt q (i+1))
else
parcourt q (i+1)
in parcourt t k;;
L'énoncé indique que recherche_naive est de type string -> string ->
int list, mais il doit s'agir d'une erreur étant donné qu'il est aussi indiqué
que le type string ne sera jamais utilisé.
6 Pour chaque position possible d'un motif dans t, c'est-à-dire {k, . . . , n}, 
on appelle
la fonction prefixe, ce qui fait n - k + 1 appels d'une complexité O( Min (k, 
n)). On
effectue de plus un appel à longueur de complexité O(k). Ainsi, en supposant k 
6 n,
La complexité de recherche_naive est en O((n - k + 1) × k).

II. Automates finis déterministes à
repli
7 Pour un état q  QA , la suite des (j (q))jN est une suite d'entiers naturels
strictement décroissante tant que j (q) 6= 0 (car (p) < p pour p 6= 0). Elle 
converge
donc vers l'état q = 0, où elle devient stationnaire car (0) = 0 par 
définition. Ainsi,
il existe un rang j à partir duquel i (q) = 0 pour tout i > j. De plus, par 
définition
des AFDR, on impose que pour tout   , (0, ) soit défini. On a donc que
Pour tout q  QA , pour tout   , il existe j > 0 tel que (j (q), ) est défini.
8 L'AFDC à construire doit avoir le même nombre d'états et reconnaître le même
langage. On commence donc par redessiner les mêmes états en ajoutant les 
transitions
déjà existantes. Enfin, il reste à compléter l'automate avec les transitions 
manquantes,
en posant pour tout état q, (q, ) = (j (q), ) avec j le plus petit entier tel 
que
la transition soit définie.
Prenons par exemple l'état 1. Il ne manque que la transition (1, a). On remarque
que pour j = 1, (1) = 0 et (0, a) = 1. On ajoute donc une transition de l'état 1