Mines Informatique optionnelle MP 2022

A2022 -- INFO MP

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARIS,
TÉLÉCOM PARIS, MINES PARIS,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT ATLANTIQUE, ENSAE PARIS,
CHIMIE PARISTECH - PSL.

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

CONCOURS 2022
ÉPREUVE 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 9 pages de texte.

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

Les sujets sont la propriété du GIP CCMP. Ils sont publiés sous les termes de 
la licence
Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de 
Modification 3.0 France.
Tout autre usage est soumis à une autorisation préalable du Concours commun 
Mines Ponts.

Épreuve d'option informatique MP 2022

Préliminaires

Présentation du sujet

L'épreuve est composée d'un problème unique, comportant 27 questions. Dans ce 
problème,
nous étudions un mécanisme pour lire un mot qui a été brouillé (par exemple 
corekte)
et proposer un mot ciblé comme correction de ce mot (par exemple correct). Ce 
type de
traitement est couramment utilisé dans le contexte de la vérification 
orthographique, de
la reconnaissance vocale, de la lecture optique ou encore de la conception de 
moteurs de
recherche tolérant aux requêtes mal formulées.

Après cette section de préliminaires, le problème est divisé en trois sections. 
Dans la
première section (page 1), nous étudions comment mesurer des erreurs commises à 
la saisie
d'un mot par une méthode de programmation dynamique. Dans la deuxième section 
(page 4),
nous étudions comment stocker un corpus de mots par une méthode arborescente et 
comment
fouiller ce corpus à l'aide d'un automate déjà construit. Dans la troisième 
section (page 7),
nous étudions comment construire un filtre de fouille par une méthode inspirée 
de la théorie
des automates.

Dans tout l'énoncé, un même identificateur écrit dans deux polices de caractère 
différentes
désignera la même entité, mais du point de vue mathématique pour la police en 
italique (par
exemple n ou n') et du point de vue informatique pour celle en romain avec 
espacement fixe
(par exemple n ou nprime).

Travail attendu

Pour répondre à une question, il sera permis de réutiliser le résultat d'une 
question
antérieure, même sans avoir réussi à établir ce résultat.

Il faudra coder des fonctions à l'aide du langage de programmation OCaml, en 
reprenant
l'en-tête de fonction fourni par le sujet, sans nécessairement recopier la 
déclaration des types.
Quand l'énoncé demande de coder une fonction, sauf demande explicite de 
l'énoncé, il n'est
pas nécessaire de justifier que celle-ci est correcte ou que des préconditions 
sont satisfaites.

Le barème tient compte de la clarté des programmes : nous recommandons de 
choisir des
noms de variables intelligibles ou encore de structurer de longs codes par des 
blocs ou par
des fonctions auxiliaires dont on décrit le rôle.

1 Une mesure des erreurs de saisie

1.1 Une fonction mystère

La constante entière max_int désigne le plus grand entier représentable par 
OCaml. Nous
nous donnons la fonction mystere suivante.

let rec mystere z = match z with
(* La fonction mystere calcule ... *)
| [] -> max int
| [al -> a
| a::b::y -> mystere ((if a <=b then a else b)::y);; CT 1 -- Donner la signature de la fonction mystere. Justifier brièvement. Page 1 sur 9 Épreuve d'option informatique MP 2022 CT 2 -- Dire si, quelle que soit l'entrée z respectant le typage, le calcul de mystere z se termine et le démontrer. Préciser, le cas échéant, le nombre d'appels à la fonction mystere. CT] 3 --- Compléter sommairement le commentaire de la ligne 2. Enoncer une propriété qui caractérise exactement la valeur de retour de la fonction mystere. Démontrer cette propriété. Dans la question suivante, le terme complexité en espace désigne un ordre de grandeur asymptotique de l'espace utilisé en mémoire lors de l'exécution d'un algorithme pour stocker tant l'entrée que des résultats intermédiaires et la valeur de retour. [] 4 -- Quelle est la complexité en espace de l'appel mystere z? Est-elle optimale ? 1.2 Distance d'édition de Levenshtein Nous fixons un alphabet de 27 symboles Y -- {a,b,...,y,z,$} qui se représentent par le type char. L'ensemble des mots sur l'alphabet Y se note X*: la longueur d'un mot w EUR > *
se note |[w|. Dans toute cette sous-section, nous fixons deux mots : le mot b 
-- b:...b,, dit
brouillé, de longueur m et le mot EUR = EUR...c,, dit ciblé, de longueur n.

Définition : Nous appelons distance entre un mot brouillé b EUR Y* et un mot 
ciblé c EUR »*,
et nous notons dist(b,c), le nombre minimum de symboles qu'il faut supprimer, 
insérer ou
substituer à un autre symbole pour transformer le mot brouillé b en le mot 
ciblé EUR. On
remarque que dist(b,c) = dist(c, b).

Par exemple, la distance entre le mot brouillé b = corekte et le mot ciblé EUR 
= correct
vaut 3 : en effet, on peut insérer un r, substituer un c au k et supprimer le e 
final pour passer
du mot b au mot c; par ailleurs, on peut vérifier que cette transformation est 
impossible en
effectuant deux opérations ou moins.

Nous notons préf,(b) le préfixe de longueur à du mot b, c'est-à-dire le mot des 
à premiers
symboles de b. Pour ? = 0, il s'agit du mot vide EUR. Pour tous les indices ? 
compris entre 0
et m et pour j compris entre 0 et n, nous notons d;; = dist (préf,(b), 
préf,(c)) la distance
entre les préfixes préf,(b) et préf;(c).

CT 5 -- Pour tous les entiers à compris entre 0 et m et j compris entre 0 et n, 
déterminer les

distances d;o et do.

CT] 6 -- Pour tous les entiers à compris entre 0 et m -- 1 et j compris entre 0 
et n -- 1, exprimer

la distance d;,1,+1 en fonction des distances (dir ;r)oc int : la longueur d'une liste £ est 
List.length 1:

-- Array.make, de type int -> 'a -> 'a array : un tableau de longueur n dont 
chaque
case est initialisée avec la valeur v s'obtient par Array.make n v. Dans un 
tableau,
les indices sont numérotés à partir de 0. On accède au coefficient en position 
? du
tableau a par l'expression a.(i), on le modifie par l'instruction a.(i) <- v. [] 7 - Écrire une fonction array _ of mot (w:mot) : char array dont la valeur de retour est un tableau formé des symboles du mot w écrits dans le même ordre. Indication Ocamil : Nous rappelons la syntaxe de la fonction suivante : -- Array.make matrix, de type int -> int -> ?'a -> ?'a array array : une matrice
de taille s x t dont toutes les cases sont initialisées avec la valeur v 
s'obtient par
Array.make matrix s t v. Dans une matrice, les indices sont numérotés à partir
de 0. On accède au coefficient en position (i,j) de la matrice a par 
l'expression
a.(i).(j), on le modifie par l'instruction a.(i).(j) <- v. [] 8 - Écrire une fonction distance (b:mot) (c:mot) : int qui calcule par mémoïsation la distance dist(b, c). Indication Ocamil : Nous rappelons la syntaxe de la fonction suivante : -- List.filter, de type ('a -> bool) -> 'a list -> 'a list : la sous-liste des 
élé-
ments x de la liste { tels que le prédicat p(x) vaut true s'obtient par filter 
p 1.

CT 9 -- Soit nmA+ un entier. Exprimer la complexité en temps de la fonction 
distance b c
en fonction des longueurs m et n des mots b et c. En déduire la complexité de 
l'instruction
List.filter (fun c -> (distance b c) <= k) 1c;; où /. est une liste de mots ciblés, chacun de longueur inférieure ou égale à nnax, et où k est un entier naturel. [1 10 -- Soit k la distance dist(b, c). Montrer qu'il existe un entier r, des mots bo, b1, ..., b, appartenant chacun à 2, des mots Cp, EUR1,..., EUR appartenant chacun à X* et des symboles xo, T1,..., Tr_1 appartenant chacun à » tels que b -- botob: .. .Tr_107 et Cc-- CoToC1 : - - Lr_1Cr et . k = max(|lbl,|c;|). i=0 Page 3 sur 9 Épreuve d'option informatique MP 2022 2 Fouille dans un trie 2.1 Représentation d'un corpus de mots par un trie Définition : Un trie est un type particulier d'arbre dont chaque arête est orientée de la racine vers les feuilles et est étiquetée par un symbole de Y. Le trie vide est formé d'un seul sommet et de zéro arête. Lorsqu'une arête est étiquetée par le symbole $, son extrémité finale doit être le trie vide. La taille d'un trie t, notée |t|, est le nombre de ses arêtes. On dit qu'un mot ce = &...cn EUR (D X {$}) appartient à un trie s'il existe un chemin, constitué de n + 1 arêtes, issu de la racine et dont les arêtes successives ont pour étiquettes respectives les symboles EUR1, &, ..., &, et $. Le symbole $ indique la présence d'un mot et joue le rôle de symbole terminateur. Dans cette partie, les tries sont utilisés afin de représenter un corpus de mots ciblés. FIGURE 1 - Exemple de trie de taille 28 contenant 9 mots. O gr / O O sl " SL Y EX O O 0" Oo o 'o e e| | e O O © o TRS 8 |S le O0 © o O © o s) | fe O0 oO ÿ \e O0 oO sl O [] 11 -- Donner l'ensemble des mots du trie représenté à la figure 1. Dans ce sujet, le terme dictionnaire désigne en général un type de données abstrait qui contient des associations entre une clé et une valeur. [] 12 --- Nommer deux structures de données concrètes, qui réalisent le type abstrait diction- naîire. Pour chacune d'entre elles, rappeler sans justifier la complexité en temps de l'opération insertion. Page 4 sur 9 Épreuve d'option informatique MP 2022 Indication Ocamil : Nous définissons un type polymorphe 'a char map qui réalise une structure de données persistante de dictionnaire associant des clés de type char à des valeurs de type quelconque 'a. Nous disposons de la constante et de la fonction suivante : -- CharMap.empty, de type 'a char map, qui désigne le dictionnaire vide. -- CharMap.add, de type char -> ?'a -> ?'a char map -> 'a char map, telle que 
la va-
leur de retour de CharMap.add x t d est un dictionnaire contenant les 
associations
du dictionnaire d ainsi qu'une association supplémentaire entre la clé x et la 
valeur #.
Si la clé x était déjà associée dans le dictionnaire d, l'ancienne association 
de x
disparaît.

Pour représenter les tries, nous définissons le type

type trie -- Node of trie char _ map ;;

[] 13 -- Définir deux constantes trie vide et trie motvide, de type trie, qui 
réalisent
respectivement le trie vide et le trie contenant le mot vide EUR.

[CT 14 - Écrire une fonction trie singleton (x:char) : trie qui construit un 
trie contenant
le mot formé d'un seul symbole x EUR XX {$}.

Indication Ocamil : Nous utilisons un type polymorphe 'a option défini par
type 'a option --
| None
| Some of 'a;;

qui permet de représenter des valeurs de type 'a parfois non définies. Nous 
complétons le
type 'a char map par la fonction suivante :

-- CharMap.find, de type char -> 'a char map -> 'a option, telle que l'appel de
CharMap.find x d renvoie, en temps constant, Some t si la clé x est associée à 
la
valeur t dans le dictionnaire d et renvoie None s'il n'existe pas d'association 
de clé x
dans le dictionnaire d.

[1 15 - Écrire une fonction trie mem (c:mot) (Node tem:trie) : bool qui teste 
si le mot
ce (S <{$}) appartient au trie { = Node tom. [1 16 -- Écrire une fonction trie add (c:mot) (Node tem:trie) : trie dont la valeur de retour est un trie contenant les mêmes mots que le trie { -- Node tcm ainsi que le mot c EUR CES {8h CT 17 -- Nous construisons le trie représenté à la figure 1 en déclarant d'abord la constante trie vide (question 13), puis en appliquant neuf fois la fonction trie_add (question 16). Compte tenu du caractère persistant du type 'a char map, combien d'exemplaires de trie_ vide coexiste-t-il une fois la construction terminée ? Expliquer. Page 5 sur 9 Épreuve d'option informatique MP 2022 Définition : Un trie est dit élagué si toute feuille est précédée d'une arête d'étiquette $. Indication Ocamil : Nous complétons le type 'a char _ map par les fonctions suivantes : -- CharMap.is empty, de type 'a char map -> bool, qui teste si un dictionnaire 
est le
dictionnaire vide.

-- CharMap.filter map, de type (char -> ?'a -> ?a option) -> ?'a char map ->
a char map, telle que CharMap.filter map f d renvoie le dictionnaire d' 
restreint
aux associations entre la clé x et la valeur {' où, d'une part, il existe dans 
le dic-
tionnaire d une association entre la clé x et la valeur t et, d'autre part, 
f(t) vaut
Some tprime. Si le dictionnaire d contient un couple clé et valeur (x,t) mais 
que
f(t) vaut None, alors le dictionnaire d' ne contient pas d'association de clé 
x. En

voici une illustration :
Fr = Fr ù
d d'

A Ti À f(t1) = Some tiprime

T2 9 to f(t2) = None

T3 + 3 T3 À f(t3) = Some t3prime
L | | _ V | | 7

CT 18 -- Compléter le code suivant afin que la valeur de retour de trie trim t 
soit un trie
élagué contenant les mêmes mots que le trie { = Node tem.

let rec trie trim (Node tcm:trie) : trie =
let filtre (x:char) (y:trie) : trie option =
(* a completer *)
in
Node(CharMap.filter map filtre tcm);;

2.2 Filtrage dans un trie

[CT 19 - Soient b EUR (ZX K {$})° un mot brouillé, & un trie contenant un 
ensemble de mots ciblés
et # un entier naturel. On suppose avoir engendré la liste {, des mots de (5 K 
{$})° à distance

inférieure ou égale à # du mot b. Montrer que la liste {, compte © (IbI*) 
éléments. En déduire
la complexité en temps de l'instruction List.filter (fun bb -> trie mem bb t) 
1lb;;.

Définition : Nous appelons système de transitions sur l'alphabet Y la donnée 
d'un triplet
(Q, 4, À) où

-- Q est un ensemble (fini ou non), dit ensemble des états,

-- ÿ EUR Q est un état, dit état initial,

-- ACQ XX Q est une relation, dite relation de transition.

Un mot c=c...c, EUR X" est accepté par le système de transitions (Q, à, À) s'il 
existe une
suite d'états (q;)o<;en telle que l'état qo égale l'état initial 4 et, pour tout j compris entre 0 et n --1, le triplet (q;,C;+1,q;+1) appartient à la relation de transition A. Page 6 sur 9 Épreuve d'option informatique MP 2022 On peut voir un système de transitions comme un automate éventuellement infini dont tous les états sont finals. [] 20 -- Dessiner, sans justifier, un système de transitions fini qui accepte les mots w EUR Y* n'ayant pas le mot ccmp comme facteur (c'est-à-dire que le mot w n'est pas accepté si et seulement s'il contient quatre symboles consécutifs valant c, c, m et p). Nous disons qu'un système de transitions (Q, 4, À) est déterministe s'il existe une fonction partiellement définie 0 : Q x 5 -- Q telle que l'on ait A ={(q,x,0(q,x)); (q,x) EUR Q XX et Ô(q,x) est défini} . Nous notons alors (Q, 4, ô) ce système. Indication Ocaml : Afin de représenter des systèmes de transitions déterministes, nous convenons de nous appuyer sur un type etat pour représenter l'ensemble des états Q. Ce type sera explicité ultérieurement. Nous déclarons type syst _ trans = etat -> char -> etat option;;
pour représenter la fonction de transition 0. Pour tout couple (q,x) EUR Q x 
Y,, si delta est
de type syst_trans, on accède à l'état image q' = Ô(q,x) par l'expression delta 
q x qui
vaut alors Some qprime si la transition est bien définie ou bien None si la 
transition n'est
pas définie.

[] 21 -- Écrire une fonction trie filter (qchapeau:etat)  (delta:syst trans)
(Node tcm:trie) : trie qui renvoie un trie contenant les mots du trie { -- Node 
tcm
acceptés par le système de transitions déterministe (Q, 4, à). Il n'est pas 
demandé de renvoyer
un trie élagué.

[1 22 -- Un système de transitions déterministe (Q, 4, 0) étant fixé, quelle 
est la complexité
en temps du calcul trie filter qchapeau delta t en fonction du trie t{ ? On 
suppose que
l'exécution de la fonction de transition à s'effectue en temps constant.

3 Système de transitions des voisins d'un mot brouillé

Dans toutes les questions restantes, les lettres b et c désignent 
systématiquement deux
mots de longueur m et n de (5 K {$})°. La lettre 4 désigne un entier naturel. 
L'écriture c$
désigne la concaténation du mot EUR et du symbole $ : nous parlons alors de mot 
prolongé.

L'objectif de cette section est de construire un système de transitions non 
déterministe qui,
à partir d'un entier naturel k et d'un mot brouillé b, accepte n'importe quel 
préfixe du mot
prolongé EUR' = c$ où c est un mot de (Z X {$})" tel que dist(b,c) < Æ et aucun autre mot n'est accepté. Page 7 sur 9 Épreuve d'option informatique MP 2022 Définition : Nous appelons transformations élémentaires les (k +3) appellations suppr, subs et h-ins-puis-id, avec 0 < h < k; nous notons 7 leur ensemble. Soient EUR' = «...c, EUR X* un mot de longueur n et b' EUR X* un mot de longueur m. Nous disons qu'une suite T = (71,72,...,7) de n transformations élémentaires est un script de transformation du mot c' en le mot b" s'il existe une factorisation 81/82... 6, du mot b' telle que pour tout entier 7? compris entre 1 et n, (1) B; est un mot de »*, (2) lorsque 7; = suppr, alors le mot B; est le mot vide EUR, 3) lorsque 7; = subs, alors le mot B; est de longueur 1 et, en l'identifiant à un symbole, il j j est distinct du symbole c;;, 4) lorsque 7; = h-ins-puis-id, alors le mot 8; est de longueur À + 1 et le dernier symbole j j de B; vaut le symbole c. Nous observons que la factorisation du mot b' en B:162...{8, est unique et ne dépend que du script 7. Voici un exemple de script de transformation entre le mot EUR' = correct$ et le mot b' -- incorektef. / (Ch1