Corrigé Mines-Ponts 2025 Informatique option MP — Partie 1 (Q1 à Q9) : Ordre lexicographique, dictionnaires, automates

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique option MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

L'alphabet est $Σ = {a, b}$ avec $a < b$ ; $ε$ est le mot vide et $Σ^{*}$ est muni de l'ordre lexicographique. Le sujet souligne les mots qui servent d'état. Types et dictionnaires fournis :


type letter = A | B
type word = letter list
(* module WordMap, dictionnaires persistants à clés de type word *)
WordMap.empty : 'a wordmap
WordMap.add   : word -> 'a -> 'a wordmap -> 'a wordmap
WordMap.find  : word -> 'a wordmap -> 'a

Un automate est toujours déterministe complet : $A = (Q, q_{0}, δ, 1_{F})$ , avec $δ : Q \times Σ \to Q$ et $1_{F} : Q \to {faux, vrai}$ l'indicatrice des états finals. Les états sont des mots :


type state = word
type automaton = { initial : state ;
                   transitions : state -> letter -> state ;
                   finals : state -> bool }

L'automate des questions 5 à 7 :

$δ^{*} (q, w)$ est l'état atteint depuis $q$ en lisant $w$ .

Q1. Écrire cmp_letter (x1:letter) (x2:letter) : int, nul si les lettres sont égales, négatif si $x_{1} < x_{2}$ , positif sinon.
Q2. Même chose pour cmp_word (w1:word) (w2:word) : int et l'ordre lexicographique, sans compare.
Q3. Décrire une structure de dictionnaire immuable à clés dans $Σ^{*}$ : nom classique, type OCaml, condition sur les clés, invariant.
Q4. Déclarer delta_a, delta_b (de type word wordmap) et un_a (de type bool wordmap) égaux à $δ_{a} = {ε \mapsto a, a \mapsto ε}$ , $δ_{b} = {ε \mapsto ε, a \mapsto a}$ et $1_{{a}} = {ε \mapsto faux, a \mapsto vrai}$ .
Q5. Décrire en français le langage de l'automate figuré et en donner une expression régulière.
Q6. Cet automate est-il l'automate de Glushkov d'une expression régulière ?
Q7. Définir automaton_example égal à l'automate figuré, en complétant le gabarit transitions = (fun q x -> WordMap.find q (...)).
Q8. Écrire delta_star (a:automaton) (q:state) (w:word) : state qui calcule $δ^{*} (q, w)$ .
Q9. Écrire accepts (a:automaton) (w:word) : bool à l'aide de Q8.

Corrigé

Q1. On filtre sur le couple des deux lettres ; les deux cas d'égalité sont regroupés dans le dernier motif.


let cmp_letter (x1:letter) (x2:letter) : int =
  match x1, x2 with
  | A, B -> -1
  | B, A -> 1
  | _ -> 0

Le filtrage est exhaustif : les couples (A, A) et (B, B) tombent dans le motif universel et renvoient $0$ . Ce que le correcteur attend : des constructeurs dans les motifs, et non des variables (un motif x1, x1 est refusé par OCaml, et un motif a, b lie deux variables qui filtrent tout).

Q2. Ordre lexicographique : le mot vide précède tout mot non vide ; deux mots non vides se comparent par leur première lettre, puis, en cas d'égalité, par leurs suffixes.


let rec cmp_word (w1:word) (w2:word) : int =
  match w1, w2 with
  | [], [] -> 0
  | [], _ :: _ -> -1
  | _ :: _, [] -> 1
  | x1 :: r1, x2 :: r2 ->
    let c = cmp_letter x1 x2 in
    if c <> 0 then c else cmp_word r1 r2

Terminaison : la longueur de w1 décroît strictement à chaque appel. Correction, par récurrence sur $∣ w_{1} ∣$ : si $x_{1} \neq = x_{2}$ , la première lettre décide ; sinon $x_{1} r_{1}$ et $x_{2} r_{2}$ se comparent comme $r_{1}$ et $r_{2}$ . Un préfixe strict précède le mot (cas [], _ :: _), ainsi $a < aa < ab < b$ . Le coût est $O (min (∣ w_{1} ∣, ∣ w_{2} ∣))$ . (Exécutée : le signe de cmp_word u v coïncide avec celui de compare u v sur les $16129$ couples de mots de longueur $⩽ 6$ .)

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →