Corrigé Mines-Ponts 2025 Informatique option MP — Partie 3 (Q14 à Q21) : Arbres discriminants et criblage

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

Énoncé

Un arbre discriminant est un arbre de décision binaire dont les nœuds internes portent des discriminants et les feuilles des états deux à deux distincts :


type disctree = Node of disctree * disc * disctree
              | Leaf of state

L'arbre $T_{0}$ du sujet (cercles : nœuds internes ; rectangles : feuilles) :

Cribler $u$ à travers $T$ : partir de la racine ; en un nœud interne d'étiquette $v$ , descendre à gauche si $uv \in L$ , à droite sinon ; la feuille atteinte porte le criblat $⌊ u ⌋$ .

Exemple du sujet, pour $L = a b^{*} a$ : $⌊ abbba ⌋ = aa$ et $⌊ abb ⌋ = a$ . Un arbre est accessible si $⌊ w ⌋ = w$ pour toute étiquette de feuille $w$ ; il est démêlant s'il a au moins un nœud interne et si sa racine porte $ε$ .

Q14. Écrire states_of_disctree (t:disctree) : state list, liste des étiquettes des feuilles dans un ordre quelconque, en temps linéaire en le nombre de feuilles (à justifier).
Q15. Donner $⌊ ba ⌋$ dans l'exemple.
Q16. Écrire sift (t:disctree) (u:word) : state, qui renvoie $⌊ u ⌋$ .
Q17. Complexité dans le pire des cas de sift t u, en fonction de $∣ u ∣$ , du nombre $n$ de nœuds, de la hauteur $h$ , de $M = max_{v \in T} ∣ v ∣$ , du coût $μ (∣ w ∣)$ de Oracle.mem w et du coût $ν (∣ A ∣)$ de Oracle.equiv a.
Q18. Montrer, en exhibant un discriminant, que deux mots de criblats distincts sont séparables.
Q19. Montrer que deux mots inséparables ont le même criblat.
Q20. Montrer que le nombre de feuilles d'un arbre accessible est majoré par une constante ne dépendant que de $L$ .
Q21. Montrer que si $u_{1}, u_{2}$ ont le même criblat dans un arbre démêlant, alors $1_{L} (u_{1}) = 1_{L} (u_{2})$ .

Corrigé

Q14. On accumule les étiquettes dans un accumulateur, sans jamais concaténer de listes :


let states_of_disctree (t:disctree) : state list =
  (* ajoute t acc : les étiquettes des feuilles de t, placées devant acc *)
  let rec ajoute t acc =
    match t with
    | Leaf q -> q :: acc
    | Node (g, _, d) -> ajoute g (ajoute d acc)
  in
  ajoute t []

Correction, par induction structurelle : pour une feuille, on ajoute son étiquette devant acc ; pour un nœud, on place d'abord les feuilles de d devant acc, puis celles de g devant le tout. Complexité : un arbre discriminant est un arbre binaire strict (chaque nœud interne a exactement deux fils), donc s'il a $f$ feuilles il a $f - 1$ nœuds internes. En effet, par induction, une feuille a $1$ feuille et $0$ nœud interne, et si $g$ et $d$ ont $f_{g}$ et $f_{d}$ feuilles, Node (g, v, d) a $f_{g} + f_{d}$ feuilles et $(f_{g} - 1) + (f_{d} - 1) + 1 = f_{g} + f_{d} - 1$ nœuds internes. La fonction ajoute est appelée une fois par nœud, soit $2 f - 1$ appels, et chaque appel coûte $O (1)$ hors appels récursifs (un filtrage, au plus un ::). Le coût total est $O (f)$ , linéaire en le nombre de feuilles. Ce que le correcteur attend : pas de (states_of_disctree g) @ (states_of_disctree d), dont le coût est quadratique sur un peigne (le jury relève de nombreuses « preuves » de linéarité fausses). (Exécutée sur $T_{0}$ : [[A;A]; [A]; []; [B]], c'est-à-dire $[aa, a, ε, b]$ .)

Q15. Avec $L = a b^{*} a$ : à la racine $ε$ , $ba \in / L$ , on descend à droite ; en $bbbba$ , $babbbba \in / L$ , à droite ; en $aba$ , $baaba \in / L$ , à droite. Le chemin est $ε - bbbba - aba - b$ , donc

$⌊ ba ⌋ = b .$

(Aucun mot commençant par $b$ n'est dans $L$ : tous ces mots ont pour criblat $b$ .)

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 →