Corrigé X-ENS 2025 Informatique A MP — Partie IV (Q17 à Q20) : Récursion ouverte, preuve par invariant et séparation-évaluation

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

Énoncé

On ne construit plus la liste de tous les arbres. La fonction de la figure 1 doit, pour un état $σ$ et une liste de caractères $C$ , renvoyer $(t, h (t))$ avec $t$ optimal pour $C$ et $σ$ . Elle n'est pas récursive : l'argument oracle tient lieu d'appel récursif (récursion ouverte).


let arbre_optimal_avec_oracle
      (oracle : etat -> caractere list -> arbre * float)
      (etat : etat)
      (caracteres : caractere list) : arbre * float =
  if caracteres = [] then
    (Feuille etat, 0.)
  else
    let caracteres_a_tester = ref caracteres in
    let score_optimal = ref infinity in
    let arbre_optimal = ref None in
    while !caracteres_a_tester <> [] do
      let caractere = List.hd !caracteres_a_tester in
      let score_total = ref 1. in
      let enfants : (float * arbre) array =
         Array.init num.(caractere) (fun valeur ->
           let p_valeur = proba_etat etat caractere valeur in
           let sous_arbre, score_sous_arbre =
             if p_valeur = 0. then Impossible,0. else
               let etat' = reponse etat caractere valeur in
               let caracteres_restants =
                  List.filter (fun c -> c <> caractere) caracteres
               in
               oracle etat' caracteres_restants
          in
          score_total := !score_total +. p_valeur *. score_sous_arbre;
          (p_valeur, sous_arbre))
      in
      if !score_total < !score_optimal then
         (arbre_optimal := Some (Noeud {caractere=caractere;enfants=enfants});
          score_optimal := !score_total);
      caracteres_a_tester := List.tl !caracteres_a_tester
    done;
    match !arbre_optimal with
    | Some a -> a, !score_optimal
    | None -> assert false

Q17. Donner des préconditions aussi précises que possible sur $C$ , $σ$ et oracle sous lesquelles cette fonction termine et renvoie $(t, h (t))$ avec $t$ optimal pour $C$ et $σ$ (après avoir réfléchi à Q18 et Q19).
Q18. Démontrer qu'elle satisfait cette spécification, en énonçant l'invariant de boucle.
Q19. Écrire une fonction récursive arbre_optimal : etat -> caractere list -> arbre * float, fondée sur la précédente, qui renvoie un arbre optimal ; donner sa spécification et la prouver.
Q20. Écrire arbre_optimal_opt : etat -> caractere list -> float -> (arbre * float) option, qui interrompt la construction d'un arbre dès que son score dépasse le meilleur courant : elle renvoie None si tous les arbres de décision ont une hauteur moyenne supérieure au score maximal donné, et sinon un arbre optimal (preuve non demandée).

Corrigé

Dans toute la partie, on raisonne en arithmétique exacte, comme l'énoncé : les flottants sont vus comme des réels. On note $h^{*} (C, σ)$ la hauteur moyenne d'un arbre optimal pour $C$ et $σ$ . Deux remarques servent partout.

(R1) Si $C = \emptyset$ , le seul arbre de décision est Feuille $σ$ (un nœud exige un caractère de $C$ ), de hauteur $0$ . Si $σ$ est une dirac, Feuille $σ$ est un arbre de décision de hauteur $0$ , donc optimal, alors que tout nœud a une hauteur moyenne $\geq 1$ . Si $σ$ n'est pas une dirac et $C \neq = \emptyset$ , les arbres de décision sont exactement des nœuds dont le caractère est dans $C$ .
(R2) Pour un caractère $i \in C$ fixé, les arbres de décision de racine $i$ sont les Noeud dont l'enfant de rang $v$ vaut $(p_{v}, Impossible)$ si $p_{v} = P^{σ} (C_{i} = v) = 0$ , et $(p_{v}, t_{v})$ sinon, avec $t_{v}$ arbre de décision quelconque pour $C ∖ {i}$ et $σ [i := v]$ , ces choix étant indépendants. Comme $h = 1 + \sum_{v} p_{v} h (t_{v})$ avec $p_{v} \geq 0$ , la plus petite hauteur moyenne d'un arbre de racine $i$ est $1 + \sum_{v, p_{v} > 0} p_{v} h^{*} (C ∖ {i}, σ [i := v])$ , atteinte en prenant chaque $t_{v}$ optimal.

Q17. Préconditions :

(P1) $σ$ est un état valide : une distribution sur $S$ codée selon l'invariant (poids $> 0$ , sans doublons, de somme 1), dont les espèces ont $N$ mesures, la $i$ -ième étant une distribution sur ${0, \dots, num.(i) - 1}$ ;
(P2) $C$ est une liste sans doublons de caractères de ${0, \dots, N - 1}$ ;
(P3) $C = []$ ou $σ$ n'est pas une dirac ;
(P4) pour tout $i \in C$ et toute valeur $v$ telle que $P^{σ} (C_{i} = v) > 0$ , l'appel oracle $(σ [i := v])$ $(C ∖ {i})$ , où $C ∖ {i}$ est la liste obtenue par List.filter, termine et renvoie $(t^{'}, h (t^{'}))$ avec $t^{'}$ optimal pour $C ∖ {i}$ et $σ [i := v]$ .

(P4) ne porte que sur les appels effectivement faits : rien n'est demandé à l'oracle sur d'autres arguments. (P3) est indispensable : si $σ = δ_{s}$ et $C = [0]$ , la fonction renvoie un Noeud, de hauteur moyenne $\geq 1$ , alors que Feuille $δ_{s}$ , de hauteur $0$ , est optimal (R1). En revanche, (P4) exige que l'oracle soit correct aussi sur les états dirac qu'il peut recevoir : ce sera le rôle du test de dirac en Q19.

Q18. Les numéros de ligne sont ceux de la figure 1. Cas $C = []$ (lignes 5-6) : la fonction renvoie $(Feuille σ, 0)$ , optimal d'après (R1).

Cas $C = [c_{1}; \dots; c_{m}]$ avec $m \geq 1$ . Corps de boucle, pour le caractère $c = c_{k + 1}$ : pour chaque valeur $v$ , si $p_{v} = 0$ l'enfant est $(0, Impossible)$ et contribue $0$ ; sinon reponse est définie (Q7) et, d'après (P4), l'oracle termine et renvoie $(t_{v}, h (t_{v}))$ avec $t_{v}$ optimal pour $C ∖ {c}$ et $σ [c := v]$ . À la fin de l'Array.init (lignes 14-27), $score_total = 1 + \sum_{v} p_{v} h (t_{v})$ : c'est la hauteur moyenne de $T_{c} = Noeud {caractere=c;enfants}$ , qui est un arbre de décision (les enfants ont la forme exigée), et d'après (R2) $h (T_{c})$ est la plus petite hauteur moyenne d'un arbre de décision de racine $c$ .

Invariant de la boucle while (ligne 11). Après $k$ tours ( $0 \leq k \leq m$ ) :

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 →