Corrigé X-ENS 2025 Informatique A MP — Partie II (Q8 à Q11) : Arbre de décision optimal par énumération

Sujet officiel du concours X-ENS, session 2025, épreuve Informatique A MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Les arbres sont codés par le type suivant (avec les types et fonctions de la partie I) :


type noeud = {caractere: caractere; enfants: (float * arbre) array}
and arbre =
  | Noeud of noeud           (* On pose une question sur un caractère. *)
  | Feuille of etat          (* On a atteint une feuille, on donne l'état. *)
  | Impossible               (* On a atteint une feuille impossible :
                                aucune espèce ne correspond aux réponses données. *)

Une valeur $t$ est un arbre de décision pour un ensemble de caractères $C$ et un état $σ$ si : $t$ n'est pas Impossible ; si $t = Feuille σ^{'}$ , alors $σ^{'} = σ$ et ( $σ$ est une dirac ou $C = \emptyset$ ) ; si $t = Noeud {caractere=i;enfants=e}$ , alors $i \in C$ , e a num.(i) cases et chaque e.(v) vaut $(P^{σ} (C_{i} = v), t^{'})$ , où $t^{'} = Impossible$ si cette probabilité est nulle, et sinon $t^{'}$ est un arbre de décision pour $C ∖ {i}$ et $σ [i := v]$ . Exemple, pour ${0, 1}$ et l'état $σ_{0}$ de Q1 ( $p$ et $q$ non précisés) :

La hauteur moyenne vaut $h (t) = 0$ pour une feuille ou Impossible, et $h (t) = 1 + \sum_{0 \leq v < num.(i)} p_{v} h (t_{v})$ pour un nœud dont les enfants sont les $(p_{v}, t_{v})$ ; l'arbre dessiné a une hauteur moyenne de $2$ . Un arbre de décision est optimal pour $C$ et $σ$ si sa hauteur moyenne est minimale parmi les arbres de décision pour $C$ et $σ$ .

Q8. Énumérer les arbres de décision pour ${0, 1}$ et $σ_{0}$ , avec leur hauteur moyenne (pour l'arbre dessiné, donner $p$ et $q$ ) ; lequel minimise la hauteur moyenne ?
Q9. Écrire choix_possibles : 'x list array -> 'x array list, liste des tableaux obtenus en choisissant un élément dans chaque liste ; ainsi choix_possibles [| [1; 2]; [3; 4; 5] |] vaut [[|1; 3|]; [|1; 4|]; [|1; 5|]; [|2; 3|]; [|2; 4|]; [|2; 5|]].
Q10. Écrire enumere : etat -> arbre list, liste de tous les arbres de décision pour un état et l'ensemble de tous les caractères (la liste globale caracteres).
Q11. Écrire argmin : 'x list -> ('x -> float) -> 'x, qui renvoie un élément d'une liste non vide minimisant $f$ , puis arbre_optimal : etat -> arbre, arbre de décision optimal pour un état et tous les caractères.

Corrigé

Q8. À la racine, $σ_{0}$ n'est pas une dirac et $C = {0, 1} \neq = \emptyset$ : une feuille est interdite, la racine est un nœud de caractère $0$ ou $1$ . On calcule les états fils avec Q3 (et la partie I) ; un état dirac avec des caractères restants peut, lui, être soit une feuille, soit un nœud.

Racine 1. $P^{σ_{0}} (C_{1} = bleu) = 0, 3 \times 0, 8 + 0, 2 = 0, 44$ et $σ_{0} [1 := bleu] = {myosotis : 6/11, lin : 5/11}$ ; $P^{σ_{0}} (C_{1} = blanc) = 0, 56$ et $σ_{0} [1 := blanc] = {gaillet : 25/28, myosotis : 3/28}$ (Q1). Aucun de ces deux états n'est une dirac et il reste le caractère $0$ : chaque fils est forcément un nœud $0$ , dont les fils, sans caractère restant, sont forcément des feuilles (ou Impossible pour une probabilité nulle). Il y a donc un seul arbre de racine $1$ , celui de l'énoncé, que l'on note $T_{1}$ ; on y lit

$p = \frac{0 , 2}{0 , 44} = \frac{5}{11} \approx 0, 45, q = \frac{0 , 5}{0 , 56} = \frac{25}{28} \approx 0, 89.$

Chaque nœud $0$ a une hauteur moyenne $1 + p_{4} \times 0 + p_{5} \times 0 = 1$ , donc $h (T_{1}) = 1 + 0, 44 \times 1 + 0, 56 \times 1 = 2$ .

Racine 0. $P^{σ_{0}} (C_{0} = 4) = 0, 5$ et $σ_{0} [0 := 4] = δ_{gaillet}$ ; $P^{σ_{0}} (C_{0} = 5) = 0, 5$ et $σ_{0} [0 := 5] = {myosotis : 0, 6, lin : 0, 4}$ . Ce dernier état n'est pas une dirac : son fils est forcément un nœud $1$ , de branches $bleu$ (probabilité $0, 6 \times 0, 8 + 0, 4 = 0, 88$ , état ${myosotis : 6/11, lin : 5/11}$ ) et $blanc$ (probabilité $0, 12$ , état $δ_{myosotis}$ ), de hauteur moyenne $1$ . Le fils $δ_{gaillet}$ est une dirac avec le caractère $1$ restant : soit une feuille ( $h = 0$ ), soit un nœud $1$ de branches $bleu$ (0 %, Impossible) et $blanc$ (100 %, feuille $δ_{gaillet}$ ), de hauteur moyenne $1$ . D'où deux arbres :

$h (T_{2}) = 1 + 0, 5 \times 0 + 0, 5 \times 1 = \frac{3}{2}, h (T_{3}) = 1 + 0, 5 \times 1 + 0, 5 \times 1 = 2.$

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 →