Mines Option Informatique MP 2022Sujet et rapport du jury

É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

Préliminaires

Présentation du sujet

Travail attendu

1 Une mesure des erreurs de saisie

1.1 Une fonction mystère

let rec mystere z = match z with
(* La fonction mystere calcule ... *)
    | [] -> max_int
    | [a] -> a
    | a::b::y -> mystere ((if a <=b then a else b)::y);;

1.2 Distance d'édition de Levenshtein

type mot = char list;;

• List.length, de type 'a list -> 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 i 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.

• Array.make_matrix, de type int -> int -> 'a -> 'a array array: une matrice de taille s × 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 ).

• 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 p1.
  ◻9 - Soit n_(max) 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) lc;; où ℓ_c est une liste de mots ciblés, chacun de longueur inférieure ou égale à n_(max), et où k est un entier naturel.

2 Fouille dans un trie

2.1 Représentation d'un corpus de mots par un trie

Figure 1 - Exemple de trie de taille 28 contenant 9 mots.

• 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 valeur de retour de CharMap.add xtd est un dictionnaire contenant les associations du dictionnaire d ainsi qu'une association supplémentaire entre la clé x et la valeur t. 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 ε.
  ◻14 - Écrire une fonction trie_singleton (x:char) : trie qui construit un trie contenant le mot formé d'un seul symbole x ∈ Σ∖{$}.

type 'a option =
| None
I Some of 'a;;

• 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.
  ◻15 - Écrire une fonction trie_mem (c:mot) (Node tcm:trie) : bool qui teste si le mot c ∈ (Σ∖{$})^∗ appartient au trie t = Node tcm.

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

• Q est un ensemble (fini ou non), dit ensemble des états,
  − q^ ∈ Q est un état, dit état initial,
• Δ ⊆ Q × Σ × Q est une relation, dite relation de transition.

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

Fin de l'épreuve