Génération d'arbres de décision pour l'identification probabiliste des plantes
Afficher ou masquer la section
Le sujet porte sur la construction d'arbres de décision permettant d'identifier des espèces de plantes à partir de caractères morphologiques modélisés par des distributions de probabilité. Il part d'une modélisation bayésienne des espèces, propose un calcul exact de l'arbre optimal par énumération puis par une optimisation de type branch-and-bound, un algorithme glouton fondé sur l'entropie de Shannon, et enfin une extension logique permettant de représenter des observations plus complexes qu'un simple caractère.
1Partie I : description probabiliste des plantesModélisation bayésienne des espèces et calculs de probabilités conditionnelles, avec leur implémentation en OCaml.
2Partie II : arbre optimalÉnumération récursive de tous les arbres de décision possibles et sélection de celui de hauteur moyenne minimale.
3Partie III : algorithme gloutonConstruction d'un arbre de décision en choisissant à chaque étape le caractère minimisant l'entropie moyenne, et mise en évidence de sa non-optimalité.
4Partie IV : optimisation de l'algorithme naïfPreuve de correction d'une fonction à récursion ouverte puis optimisation par une approche branch-and-bound.
5Partie V : observations complexes et formules logiquesModèle logique pour des observations combinant plusieurs caractères, mise en forme normale disjonctive pour évaluer une formule efficacement.
Difficile. Le rapport montre que les taux de réussite complète chutent fortement au fil du sujet, par exemple 1% seulement pour la question 17 en filière MP et des pourcentages très faibles pour les questions 18 à 20 sur la preuve de programme et le branch-and-bound.
6 à l'admissibilité, porté à 10 pour le classement (MP option informatique)
Durée
4 h
Deux tiers des copies environ (moyenne ± écart-type)
Votre note sur 20 à ce sujet, en conditions de concours.
Source : document officiel du concours, épreuve du 15 avril 2025. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.
Ce qu'a observé le jury
5 erreurs relevées
Indépendance supposée à tort · Invariants de structures de données non respectés · Énumération récursive d'arbres mal maîtrisée
Afficher ou masquer la section
Le sujet a été globalement bien réussi sur les premières questions de probabilités, mais la difficulté augmente nettement à partir de l'énumération récursive des arbres puis surtout dans la partie IV consacrée à la preuve de programme, restée largement intouchée. Le jury insiste sur l'importance de la présentation de la copie, en particulier pour les questions de code, et sur la nécessité de bien lire l'énoncé pour respecter les invariants des structures de données.
Les erreurs les plus sanctionnées
1
Indépendance supposée à tortQ4
Il était tentant d'utiliser un argument d'indépendance entre deux caractères, mais ils ne sont indépendants qu'une fois conditionnés relativement à une espèce.
2
Invariants de structures de données non respectésQ5
Les candidats ont souvent lu rapidement le sujet sans faire attention à tous les invariants liés aux structures de données, ce qui conduit à des codes faux.
3
Énumération récursive d'arbres mal maîtriséeQ10
La principale difficulté est de combiner, pour chaque enfant, les différentes possibilités issues du choix d'une question initiale en utilisant la fonction choix_possibles.
4
Ambiguïté de la somme sur l'entropie moyenneQ13
Il faut expliciter dans le code que la somme ne porte que sur les valeurs de probabilité non nulle, sinon le calcul de l'état mis à jour lève une exception.
5
Partie preuve de programme peu abordéeQ17, Q18
La partie de preuve de programme, portant sur les pré-conditions et l'invariant de boucle de la fonction à récursion ouverte, est restée largement intouchée par les candidats.
Ce qui a été bien réussi
La question 1, simple application numérique de lois classiques de probabilité, a été bien réalisée dans son ensemble.
La question 6, simple application des questions précédentes, a été bien traitée avec 70 à 72% de réussite complète.
La question 22 sur la complexité a été plutôt bien réussie dans l'ensemble, même si la formule exacte est rarement trouvée.
Conseils du jury
Soigner la présentation des questions de code en expliquant chaque fonction intermédiaire.
Lire attentivement l'énoncé pour identifier tous les invariants des structures de données avant de coder.
Ne pas supposer l'indépendance de deux variables aléatoires sans vérifier les hypothèses de conditionnement.
Ne pas négliger les questions de preuve de programme, qui rapportent des points même partiellement traitées.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
Ces sujets peuvent vous intéresser
Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.
Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Cette composition ne concerne qu'une partie des candidats de la filière MP, les autres candidats effectuant simultanément la composition de Physique et Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.
Arbres de classification d'arbres
Le sujet comporte 12 pages.
Vue d'ensemble du sujet.
Ce sujet porte sur la réalisation d'arbres d'identification des plantes basés sur des observations morphologiques. À partir d'une base de connaissance botaniste, il s'agit de réaliser un arbre dont les feuilles sont des diagnostics (typiquement des noms d'espèce) et les nœuds des caractères morphologiques (par exemple la couleur des fleurs). Un nœud a autant de fils que le caractère a de valeurs possibles (jaune, bleue, etc.).
Étant donnée une base de connaissance, il s'agit de construire un arbre dont la hauteur moyenne est la plus petite possible, ce qui revient à minimiser le nombre moyen d'observations nécessaires pour identifier une plante. La difficulté revient donc à choisir à chaque étape le caractère le plus discriminant, c'est-à-dire celui qui va le mieux séparer l'espace de recherche.
Pour tenir compte de la diversité au sein d'une espèce, nous adoptons une approche probabiliste basée sur un raisonnement bayésien : la valeur d'un caractère morphologique pour une espèce donnée sera probabiliste. Par exemple, la couleur des fleurs d'une certaine espèce pourra être bleue ou jaune, avec certaines probabilités.
La partie I introduit les éléments de raisonnement bayésien nécessaires à la construction des arbres. La partie II propose une approche par énumération pour générer un arbre qui minimise la hauteur moyenne. La partie III propose une heuristique basée sur l'entropie de Shannon pour éviter la construction de tous les arbres. La partie IV revient sur le calcul exact en proposant une optimisation permettant de réduire l'espace de recherche. Les parties III et IV sont indépendantes l'une de l'autre. Enfin, la partie V propose une approche logique pour étendre la notion de caractère. Cette dernière partie ne dépend que de la première.
Rappels de probabilités
Une mesure sur un ensemble fini X est une fonction φ : X → ℝ^+. Sa masse est la quantité ∑_(x ∈ X)φ(x). Une mesure de masse 1 est appelée une distribution de probabilité, ou simplement distribution. On note D(X) l'ensemble des distributions sur l'ensemble fini X. Pour x ∈ X, la dirac en x, notée δ_x, est la distribution qui associe à x le poids 1 , et zéro à tous les autres éléments. Étant donnés une famille de distributions d_1, …, d_n ∈ D(X) et des poids p_1, …, p_n ∈ [0; 1] tels que ∑_(1 ≤ i ≤ n)p_i = 1 , on note p_1 ⋅ d_1 + … + p_n ⋅ d_n la distribution d ∈ D(X) telle que d(x) = p_1 × d_1(x) + ⋯ + p_n × d_n(x) pour tout x ∈ X.
Si X est un ensemble, on notera 𝒫(X) l'ensemble de ses parties.
Rappels d'OCaml
Dans le reste du sujet, on pourra utiliser les fonctions suivantes de la bibliothèque standard OCaml pour les listes:
List.hd [ e_1; …; e_n ] renvoie e_1, et List.hd [] lève une exception.
List.tl [ e_1; …; e_n ] renvoie [ e_2; …; e_n ], et List.tl [] lève une exception.
List. length 1 renvoie la longueur (nombre d'éléments) de la liste 1.
List.init nf renvoie la liste [ f0; …; f(n − 1) ] pour n positif.
List.assoc k[(k_1, v_1); …; (k_n, v_n)] renvoie le premier v_i tel que k = k_i s'il existe, et lève l'exception Not_found sinon.
List.find f[e_1; …; e_n] renvoie le premier e_i tel que fe_i = true s'il existe, et lève l'exception Not_found sinon.
On rappelle enfin que la fonction log : float − > f loat est disponible en OCaml pour calculer un logarithme naturel.
Partie I : Description probabiliste des plantes
On se donne un nombre de caractères N ∈ ℕ^∗. Un caractère sera un entier i ∈ {0, 1, …, N − 1}. Pour chaque caractère i, on se donne un ensemble fini V_i de valeurs possibles pour ce caractère.
Pour nos exemples, nous prendrons N = 2 et deux valeurs pour chaque caractère : V_0 = {4, 5} représentera le nombre de pétales des fleurs, et V_1 = { bleu, blanc } représentera leur couleur.
Nous utiliserons une représentation probabiliste des espèces pour modéliser la variabilité intraespèce, ainsi que la variabilité des interprétations lors des observations : on peut trouver au sein d'une même espèce des individus à fleurs bleues et d'autres à fleurs blanches; par ailleurs, une couleur bleue très claire pourra être interprétée comme bleue ou blanche en fonction de l'observateur. Ainsi, chaque espèce sera décrite par des valeurs possibles pour chaque caractère, organisées en distributions de probabilité : une espèce est un N-uplet s = (s_0, …, s_(N − 1)) où s_i ∈ D(V_i). Intuitivement, s_i(v) représente la probabilité que la valeur v soit observée pour le caractère i chez un individu de l'espèce. On suppose donné un ensemble fini d'espèces 𝒮.
Dans nos exemples, 𝒮 sera composé des trois espèces suivantes, décrites en utilisant des diracs δ :
On définit l'ensemble Ω suivant, dont les éléments modélisent des individus, décrits par leur espèce et les valeurs de leurs caractères :
Ω = ^(def){(s, v_0, …, v_(N − 1))|s ∈ 𝒮, v_i ∈ V_i pour tout i}
On considèrera l'espace probabilisable ( Ω, 𝒫(Ω) ) obtenu en munissant Ω de la tribu discrète. On utilisera plusieurs lois de probabilité sur cet espace, définies en fonction d'un état σ ∈ D(𝒮) : intuitivement, l'état indiquera la probabilité d'observer chaque espèce. La loi de probabilité P^σ induite par un état σ est définie comme l'unique loi satisfaisant l'équation suivante pour tout (s, v_0, …, v_(N − 1)) ∈ Ω :
P^σ({(s, v_0, …, v_(N − 1))}) = σ(s) × ∏_(0 ≤ i < N − 1)s_i(v_i)
On notera S la variable aléatoire qui à (s, v_0, …, v_(N − 1)) ∈ Ω associe s. Pour chaque caractère i, on notera C_i la variable aléatoire qui à (s, v_0, …, v_(N − 1)) ∈ Ω associe v_i. On pourra ainsi écrire, par exemple, P^σ(C_i = v|S = s), qui représente (dans l'état σ ) la probabilité (conditionnelle) que le caractère i prenne la valeur v chez un individu de l'espèce s.
Préliminaires probabilistes. On établit tout d'abord quelques résultats élémentaires sur lesquels s'appuiera notre méthode de classification.
Question 1. On considère l'état σ_0 = { gaillet : 50%, myosotis : 30%, lin : 20%} sur les espèces de notre exemple. Quelle est la probabilité P^(σ_0)(C_1 = blanc) d'observer des fleurs blanches dans cet état? Pour chaque espèce s, que vaut la probabilité P^(σ_0)(S = s|C_1 = blanc) d'observer un individu de l'espèce s sachant que celui-ci a des fleurs blanches? Aucune justification n'est attendue.
Question 2. Étant donnés un état σ ∈ D(𝒮), une espèce s ∈ 𝒮, un caractère i et une valeur v ∈ V_i, exprimer simplement les probabilités P^σ(S = s) et P^σ(C_i = v), ainsi que P^σ(C_i = v|S = s) quand elle est bien définie. Les réponses devront être justifiées.
Question 3. Étant donnés un état σ ∈ D(𝒮), un caractère i, une valeur v ∈ V_i et une espèce s ∈ 𝒮, exprimer P^σ(S = s|C_i = v). Sous quelle condition cette probabilité est-elle bien définie?
Pour un état σ, un caractère i et une valeur v ∈ V_i, on définit l'état mis à jour σ[i:=v] comme la distribution qui à chaque espèce s associe P^σ(S = s|C_i = v).
Question 4. Pour un état σ, deux caractères i ≠ j et des valeur v ∈ V_i et v^′ ∈ V_j, montrer que P^σ(S = s|C_i = v, C_j = v^′) = P^(σ[i:=v])(S = s|C_j = v^′) quand ces probabilités sont bien définies.
Le résultat précédent nous indique que, si l'on souhaite évaluer dans un état σ la probabilité d'observer une certaine espèce sachant que C_i = v et C_j = v^′, il nous suffit de calculer une probabilité conditionnée seulement par C_j = v^′ mais dans l'état σ[i:=v]. En allant plus loin, si l'on pose σ^′ = σ[i:=v] et σ^(′′) = σ^′[j:=v^′], on a P^σ(S = s|C_i = v, C_j = v^′) = σ^(′′)(s). On admettra que ce résultat se généralise à un nombre arbitraire d'observations. Ainsi, il est possible de procéder à la reconnaissance de plantes en calculant des états mis à jours par des observations successives, jusqu'à atteindre un état de la forme δ_s ou ne plus pouvoir faire de nouvelle observation.
Choix des représentations pour le code. Un caractère sera naturellement représenté par un entier OCaml. On représentera aussi les valeurs par des entiers, en supposant que chaque V_i est de la forme {0, 1, …, k_i − 1}, ce qui revient à numéroter les valeurs possibles. On pose ainsi :
type caractere = int
type valeur = int
On suppose donnés le nombre de valeurs pour chaque caractère sous la forme d'un tableau :
val num : int array (* num. (i) = k_i, i.e., }\mp@subsup{V}{-}{}i={0,1,\ldots,num.(i)-1}*
Enfin, on considèrera que la liste des caractères [0; 1; …; N − 1] est définie en variable globale à partir du tableau num :
let caracteres : caractere list = List.init (Array.length num) (fun i -> i)
Pour notre exemple avec deux caractères, on aura ainsi :
(* Nombre de valeurs possibles pour le nombre de pétales et pour leur couleur *)
let num = [|2; 2|]
(* Nombre de pétales *)
let nb_petales : caractere = 0
let quatre, cinq = 0, 1
(* Couleur *)
let couleur_petales : caractere = 1
let bleu, blanc = 0, 1
Une mesure μ sur X sera représentée par une liste de couples ( x, μ(x) ) avec x ∈ X et μ(x) > 0, sans doublons. En particulier, les éléments de poids nuls ne sont pas inclus dans la liste, et l'ordre n'a pas d'importance.
type 'x mesure = ('x * float) list
let dirac v = [(v, 1.)]
Enfin, on codera comme suit les espèces et états :
type espece = { name: string; mesures: valeur mesure array }
type etat = espece mesure
Pour notre exemple, on aura ainsi :
let myosotis : espece =
{ name = "myosotis";
mesures = [| dirac cinq; [(bleu, 0.8);(blanc, 0.2)] |] }
let lin : espece =
{ name = "lin";
mesures = [| dirac cinq; dirac bleu |] }
let gaillet : espece =
{ name = "gaillet";
mesures = [| dirac quatre; dirac blanc |] }
let sigma0 : etat = [(gaillet, 0.5);(myosotis, 0.3);(lin, 0.2)]
La première renvoie le poids d'un élément selon une mesure donnée. La seconde renvoie la somme d'une mesure μ pondérée par une fonction f : X → ℝ, définie par ∑_(x ∈ X)μ(x)f(x). La troisième repondère une mesure sur X par une fonction f : X → ℝ : le poids de x ∈ X passe de μ(x) à μ(x)f(x).
Question 6. Écrire deux fonctions
val proba_espece : espece -> caractere -> valeur -> float
val proba_etat : etat -> caractere -> valeur -> float
où proba_espece s i v renvoie la probabilité P^(δ_s)(C_i = v) et proba_etat σiv renvoie P^σ(C_i = v).
Question 7. Écrire une fonction
val reponse : etat -> caractere -> valeur -> etat
qui, étant donnés un état σ, un caractère i et une valeur v ∈ V_i, renvoie l'état σ[i:=v] si celui-ci est bien défini, et lève une exception sinon.
Partie II : Arbre optimal
Dans cette seconde partie, on définit la notion d'arbre de décision, et on s'intéresse au calcul d'un arbre de décision optimal en un certain sens. On introduit les types de données suivants pour coder nos arbres :
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. *)
Les valeurs de type arbre ne représentent pas toutes des arbres de décision. Une valeur t de type arbre est un arbre de décision pour un ensemble de caractères C et un état σ lorsque :
L'arbre t n'est pas Impossible.
Si t est de la forme Feuille σ^′, alors σ^′ = σ et (au moins) l'une des deux conditions suivantes est satisfaite :
σ est une distribution dirac (il n'y a plus qu'une seule espèce possible);
C = ∅ (il n'y a plus de caractère disponible pour discriminer).
Si t est de la forme Noeud {caractere=i;enfants=e} alors i est un élément de C, e est un tableau à num. (i) éléments, et pour chaque valeur possible 0 ≤ v < num. (i), e. (v) est de la forme ( P^σ(C_i = v), t^′ ) avec :
si P^σ(C_i = v) = 0, alors t^′ est Impossible;
sinon, t^′ est un arbre de décision pour l'ensemble de caractères C∖{i} et l'état σ[i:=v].
Dans le contexte de l'exemple de la partie I, on représente graphiquement ci-dessous un arbre de décision pour l'ensemble complet de caractères {0, 1} et l'état σ_0 de la question 1 (pour des valeurs de p et q non précisées) :
Les nœuds sont étiquetés par des caractères et les feuilles par des états; la notation ⊥ est utilisée pour représenter les cas impossibles où aucune espèce ne peut correspondre aux valeurs observées. Chaque arc est étiqueté par la valeur du caractère correspondant à l'enfant ainsi que la probabilité que cette valeur soit observée.
On définit la hauteur moyenne d'un arbre t, notée h(t), comme suit :
Si t est de la forme Feuille σ ou Impossible, alors h(t) = 0.
Si t est de la forme Noeud {caractere=i;enfants=e}, et si l'on note ( p_v, t_v ) = e. ( v ), alors :
h(t) = 1 + ∑_(0 ≤ v < num.(i))p_v × h(t_v)
La hauteur moyenne correspond au nombre moyen de questions avant d'atteindre une feuille. Sur l'exemple précédent, la hauteur moyenne est de deux.
Question 8. Sur l'exemple de la question 1, énumérer tous les arbres de décision possibles pour les caractères {0, 1} et l'état σ_0, et donner leur hauteur moyenne - pour l'arbre déjà représenté ci-dessus, on pourra se contenter de préciser les valeurs de p et q. Quel est l'arbre de décision avec la hauteur moyenne minimale?
Dans la suite de cette partie, on se propose de calculer naïvement un arbre de décision de hauteur moyenne minimale. On dira qu'un arbre t est optimal pour C et σ quand c'est un arbre de décision pour C et σ tel que h(t) est minimale parmi les hauteurs moyennes de tous les arbres de décision pour C et σ. Dans un contexte où C et σ sont clairs, on dira simplement que t est optimal.
Question 9. Écrire une fonction
val choix_possibles : 'x list array -> 'x array list
qui renvoie la liste des tableaux obtenus en choisissant un élément dans chaque liste du tableau d'entrée. Par exemple :
Question 10. Écrire une fonction qui, étant donné un état initial σ_0, renvoie la liste de tous les arbres de décision possibles pour σ_0 et l'ensemble de tous les caractères :
val enumere : etat -> arbre list
On rappelle que l'ensemble {0, 1, …, N − 1} de tous les caractères est représenté par la liste caracteres déclarée en variable globale.
Question 11. Écrire une fonction
val argmin : 'x list -> ('x -> float) -> 'x
telle que argmin l f renvoie un élément de l qui minimise f, si la liste est non-vide. En déduire une fonction qui, étant donné un état initial σ_0, renvoie un arbre de décision optimal pour σ_0 et l'ensemble de tous les caractères :
val arbre_optimal : etat -> arbre
Partie III : Algorithme glouton
Afin d'éviter l'énumération de tous les arbres de décision dans l'algorithme de la partie précédente, on cherche un algorithme glouton : l'idée générale est de décider localement du caractère à choisir en fonction de l'état courant, plutôt que d'envisager tous les choix possibles. Pour cela, on décide de prendre le caractère qui minimise l'entropie moyenne. Avant de définir cette quantité, on introduit l'entropie simple H(μ) d'une distribution μ ∈ D(X), qui est donnée par :
H(μ) = ^(def) − (∑_(x ∈ X, μ(x) ≠ 0)μ(x)ln(μ(x)))
Question 12. Soit X un ensemble de cardinal k ∈ ℕ. Donner (en justifiant) les valeurs minimale et maximale de H sur D(X) en fonction de k, ainsi que des distributions les atteignant.
Étant donnés un caractère i et un état σ, on définit l'entropie moyenne de i dans l'état σ, notée H_i(σ), comme l'espérance des entropies sur les distributions obtenues en faisant une observation sur le caractère i :
H_i(σ) = ^(def)∑_(v ∈ V_i)P^σ(C_i = v)H(σ[i:=v])
Question 13. Écrire une fonction qui renvoie l'entropie moyenne d'un caractère dans un état donné :
val score_caractere : etat -> caractere -> float
Question 14. Écrire une fonction qui calcule un arbre de décision en suivant l'algorithme glouton qui construit l'arbre en choisissant à la racine le caractère minimisant l'entropie moyenne, et procède récursivement de la même façon pour les sous-arbres :
val glouton : etat -> arbre
On se propose maintenant de montrer que l'algorithme glouton n'est pas optimal. On considère une situation avec deux caractères, V_0 = V_1 = { oui, non }, et trois espèces a, b et c :
L'espèce a est donc plus rare que les espèces b et c qui sont plus communes.
Question 15. Dessiner les arbres de décision possibles pour l'état σ_0 et les caractères {0, 1}, et déterminer l'arbre de décision optimal.
Question 16. Calculer les entropies moyennes H_0(σ_0) et H_1(σ_0). Que peut-on en conclure? On admettra que ln(5) < (12)/5ln(2).
Partie IV : Optimisation de l'algorithme naïf
On cherche à optimiser l'algorithme naïf de la partie II en évitant certains calculs inutiles. Pour permettre cela, on commence par changer la méthode de recherche d'un arbre optimal, en évitant de construire la liste de tous les arbres de décision possibles. La nouvelle méthode s'appuiera sur la fonction arbre_optimal_avec_oracle donnée en Figure 1. Le but de cette fonction est, étant donnés un état σ et une liste de caractères C, de renvoyer (t, h(t)) où t est un arbre optimal pour C et σ. Il faut bien noter que cette fonction n'est pas récursive, mais qu'elle dispose d'un argument supplémentaire oracle dont les appels pourront correspondre à des appels récursifs : il s'agit de récursion ouverte.
Question 17. Donner des hypothèses (pré-conditions) aussi précises que possible sur les arguments C, σ et oracle de la fonction arbre_optimal_avec_oracle, sous lesquelles la fonction termine toujours et renvoie bien (t, h(t)) où t est un arbre optimal pour C et σ. On veillera à répondre à cette question après avoir réfléchi aux deux suivantes, où il faudra démontrer puis exploiter la correction de la fonction par rapport à la spécification énoncée ici.
Question 18. Démontrer que la fonction satisfait bien cette spécification, en veillant notamment à énoncer clairement l'invariant de boucle.
Question 19. Écrire une fonction, récursive cette fois-ci, et basée sur arbre_optimal_avec_oracle, qui renvoie un arbre de décision optimal pour un état et une liste de caractères donnés :
val arbre_optimal : etat -> caractere list -> arbre * float
Donner sa spécification et montrer qu'elle la satisfait.
Question 20. On cherche maintenant à optimiser notre algorithme en interrompant la génération d'un arbre dès que son score dépasse celui de l'arbre_optimal courant. Pour cela, écrire une nouvelle fonction
val arbre_optimal_opt : etat -> caractere list -> float -> (arbre * float) option
qui prend un paramètre supplémentaire représentant le score à ne pas dépasser, et renvoie None si tous les arbres de décision possibles sont de hauteur moyenne supérieure au score maximal, ou bien un arbre optimal de hauteur moyenne inférieure s'il en existe un. La preuve de correction n'est pas demandée.
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
Figure 1 - Fonction arbre_optimal_avec_oracle.
Partie V : Observations complexes et formules logiques
Pour aller plus loin, on se propose de représenter des observations complexes sous forme de formules logiques construites à partir des caractères, par exemple "la fleur est bleue et a cinq pétales". La syntaxe de cette logique est la suivante :
φ::=c_i ∈ V|φ_1 ∧ … ∧ φ_m|φ_1 ∨ … ∨ φ_m (0 ≤ i < N, V ⊆ V_i, m ≥ 0)
Cela signifie que l'ensemble des formules est le plus petit ensemble contenant les formules atomiques de la forme c_i ∈ V où 0 ≤ i < N et V ⊆ V_i, et que si φ_1, …, φ_m sont des formules pour m ≥ 0, alors la conjonction φ_1 ∧ ⋯ ∧ φ_m et la disjonction φ_1 ∨ ⋯ ∨ φ_m sont aussi des formules. Une formule c_i ∈ V signifie intuitivement que le caractère i prend une valeur dans l'ensemble V ⊆ V_i. On définit la formule ⊥ (la formule fausse) comme la disjonction vide, et T (la formule vraie) comme la conjonction vide.
Par exemple, avec les ensembles V_0 et V_1 de l'exemple utilisé en partie I, c_1 ∈ { bleu } ∧ c_0 ∈ {5} est une formule, correspondant à l'énoncé "la fleur est bleue et a cinq pétales". Ou encore, si V_i = {0, 1, 2, 3, 4}, c_i ∈ {1} ∧ c_i ∈ {2, 3} est une formule, correspondant à l'énoncé contradictoire "le caractère i vaut 1 , et il vaut 2 ou 3 ".
On définit la taille d'une formule φ, notée |φ|, comme suit :
|c_i ∈ V|, = 1 + |V|; |φ_1 ∧ … ∧ φ_m|, = 1 + m + ∑_(1 ≤ i ≤ m)|φ_i|; |φ_1 ∨ … ∨ φ_m|, = 1 + m + ∑_(1 ≤ i ≤ m)|φ_i|
Dans un premier temps, nous définissons quand une situation certaine (dite déterministe) satisfait une certaine formule. On appelle modèles déterministes les éléments de V_0 × … × V_(N − 1). On notera v⃗ ∈ V⃗ pour signifier que v⃗ est un tel modèle, et dans ce cas on notera v_i la i-ème composante de v⃗, ce qui revient à dire que v⃗ = (v_0, …, v_(N − 1)). On définit une relation de satisfaction entre les modèles déterministes et les formules, notée v⃗⊨φ, comme suit :
v⃗|=c_i ∈ V, si et seulement si, v_i appartient à l'ensemble V; v⃗|=φ_1 ∧ ⋯ ∧ φ_m, si et seulement si, v⃗⊨φ_k pour tout k ∈ {1, …, m}; v⃗|=φ_1 ∨ ⋯ ∨ φ_m, si et seulement si, v⃗⊨φ_k pour un k ∈ {1, …, m}
On étend ensuite cette relation de satisfaction au cadre probabiliste de la manière suivante. Un modèle probabiliste est un élément de D(V_0) × … × D(V_(N − 1)). Un tel modèle associe une distribution de probabilité plutôt qu'une valeur déterminée à chaque caractère. On remarquera que cette modélisation suppose que les valeurs de deux caractères distincts sont probabilistes mais indépendantes l'une de l'autre. Étant donnés une formule φ et un modèle probabiliste ( d_0, …, d_(N − 1) ), on définit la probabilité que d⃗ = (d_0, …, d_(N − 1)) satisfasse φ, notée P(d⃗⊨φ), ainsi :
P(d⃗⊨φ) = ^(def)∑_(v⃗ ∈ V⃗, v⃗⊨φ)∏_(0 ≤ i < N)d_i(v_i)
Question 21. Pour deux formules φ et ψ, montrer l'équivalence entre ces deux propositions :
Pour tout modèle déterministe v⃗, v⃗⊨φ si et seulement si v⃗⊨ψ.
Pour tout modèle probabiliste d, →P(d⃗⊨φ) = P(d⃗⊨ψ).
On dira que φ et ψ sont équivalentes, noté φ ≡ ψ, quand l'une ou l'autre des propositions précédentes est vraie.
Dans les questions qui suivent, on reprend le codage OCaml des distributions, et on représente directement les formules via le type suivant :
type formule =
| Feuille of caractere * valeur list
| Conjonction of formule list
| Disjonction of formule list
On supposera de plus que les listes codant les ensembles de valeurs dans les formules atomiques sont sans doublons. On codera les modèles déterministes (resp. probabilistes) par des tableaux de N valeurs (resp. distributions). On notera enfin K le cardinal maximal des V_i :
K = ^(def)max_(0 ≤ i < N)|V_i|
Question 22. On considère l'algorithme qui, étant donnés un modèle probabiliste d⃗ et une formule φ, calcule P(d⃗|=φ) en suivant naïvement sa définition. Quelle est la complexité temporelle de cet algorithme, en fonction de N, K et |φ| ? Un programme OCaml détaillé n'est pas demandé, mais on veillera à en décrire les aspects nécessaires pour justifier l'analyse de complexité.
Dans la suite, nous allons élaborer une méthode de calcul de P(d⃗⊨φ) dont la complexité ne dépend pas de N. Cette méthode s'appuie sur des formes particulières de formules. Une clause est une conjonction de formules atomiques concernant des caractères différents. En reprenant les exemples précédents, c_1 ∈ { bleu } ∧ c_0 ∈ {5} est une clause mais pas c_i ∈ {1} ∧ c_i ∈ {2, 3}.
Question 23. Décrire un algorithme qui, étant donnés un modèle probabiliste d⃗ et une clause φ, calcule P(d⃗⊨φ) avec une complexité qui ne dépend que de K et |φ|, mais pas de N. Justifier la correction de l'algorithme et son analyse de complexité. Il n'est pas nécessaire de donner un programme OCaml détaillé.
Question 24. Étant données deux clauses φ et ψ, montrer que φ ∧ ψ est équivalente à une clause que l'on notera φ ∧ ¯ψ.
Question 25. Montrer que pour toute formule φ il existe m ≥ 0 et des clauses φ_1, …, φ_m telles que φ ≡ φ_1 ∨ … ∨ φ_m.
Question 26. Décrire un algorithme qui, étant donnés un modèle probabiliste d⃗ et une formule φ, calcule P(d⃗⊨φ) avec une complexité temporelle (potentiellement non-polynomiale) qui ne dépend que de K et |φ| mais pas de N.
En pratique, un tel algorithme est utile car on va avoir des modèles avec de nombreux caractères mais un nombre de valeurs possibles restreint pour chaque caractère, et l'on s'intéressera à des formules de taille limitée.
Fin du sujet.
Questions fréquentes
4 questions
Sur quels chapitres porte le sujet d'informatique A MP-MPI X-ENS 2025 ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet d'informatique A MP-MPI X-ENS 2025 ?
+
Le sujet porte sur les probabilités conditionnelles, les structures arborescentes récursives, l'entropie de Shannon, la preuve de programmes et la complexité algorithmique, à travers la construction d'arbres de décision pour identifier des plantes.
Le sujet X-ENS informatique MP-MPI 2025 sur les arbres de décision est-il difficile ?
+
Oui, le rapport montre une chute nette des taux de réussite après les premières questions de probabilités, la partie sur la preuve de programme et l'optimisation branch-and-bound étant restée largement intouchée.
Quelles erreurs le jury a-t-il le plus relevées sur ce sujet d'informatique X-ENS ?
+
Le jury relève un manque d'attention aux invariants des structures de données, une supposition erronée d'indépendance entre caractères, et une présentation du code parfois difficile à déchiffrer.
Le sujet X-ENS informatique 2025 est-il accessible en première année de prépa ?
+
Le sujet mobilise des notions de probabilités et d'algorithmique récursive qui demandent une bonne maîtrise du programme d'informatique, avec une difficulté croissante jusqu'à la preuve de programme en fin de sujet.
Pas de description pour le moment
Commentaires• X ENS Option Informatique MP MPI 2025
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Sujet proche avec corrigéCentrale Option Informatique MP 2024Centrale · 2024Corrigé
Même chapitre : Complexité algorithmique (+2)CCINP Option Informatique MP 2026CCINP · 2026Sujet seul
Sujet proche avec corrigéMines Informatique Commune MP PC PSI 2024Mines · 2024Corrigé