Mines Informatique optionnelle MP 2018

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