Informatique A
X-ENSMP2025
# Corrigé — X-ENS 2025, Informatique A, filière MP
- **Concours** : École polytechnique / ENS (X-ULM-Lyon-Saclay-Rennes)
- **Épreuve** : Informatique A (XULSR), filières MP-MPI — durée 4 h
- **Année** : 2025
- **Titre** : *Arbres de classification d'arbres*
## Thème et fil directeur
Le sujet construit des **arbres de décision** pour identifier une plante à partir d'observations morphologiques probabilistes (couleur, nombre de pétales…), décrites par un **raisonnement bayésien**. On cherche l'arbre qui **minimise la hauteur moyenne**, c'est-à-dire le nombre moyen de questions avant d'identifier l'espèce. La partie I pose le cadre probabiliste (états, mise à jour bayésienne). La partie II calcule l'arbre optimal par **énumération** exhaustive. La partie III propose une **heuristique gloutonne** fondée sur l'entropie de Shannon — et démontre qu'elle n'est **pas** optimale. La partie IV accélère l'énumération par **récursion ouverte** puis **branch-and-bound**, avec preuves de programmes. La partie V représente des observations complexes par des **formules logiques** et évalue leur probabilité via une mise en **forme normale disjonctive**.
## Carte stratégique (tirée du rapport du jury)
Le rapport donne, par question, `[MP : % traité, % totalité des points]`. Points saillants :
- **Vivier de points sûrs** : Q1 (84 %), Q2 (79 %), Q6 (70 %), Q11, Q15 (27 %) — calculs directs et code d'application. À sécuriser intégralement.
- **Pièges à points** : Q3 (23 % : *l'explication informelle manque souvent*), Q4 (8 % : *piège d'indépendance*), Q5 (8 % : *invariant « pas de poids nul »*), Q13 (2 % : *somme restreinte aux `v` de proba non nulle*).
- **Questions clivantes difficiles** : Q9-Q10 (énumération récursive, produit cartésien), Q12 (Jensen), Q14, Q16.
- **Terrain quasi vierge = fort différenciateur** : toute la **partie IV** (Q17 : 3 %, Q18 : 1 %, Q19 : 2 %, Q20 : 1 %) « est restée largement intouchée ». La partie V est plus accessible (Q21 : 22 %, Q22 : 4 %).
- **Consigne générale** : soigner la présentation, **expliquer chaque fonction intermédiaire**, et surtout **respecter les invariants des structures de données** (mesures sans poids nul, arbres bien formés) — « une réponse ne rapporte des points que si le correcteur arrive à la déchiffrer ».
> **Remarque de notation préalable.**
La définition de $P^\sigma$ de l'énoncé porte un produit écrit $\prod_{0\le i<N-1}$ ; il s'agit d'une coquille : c'est bien $\prod_{0\le i<N}$ (sur **tous** les caractères) qui est visé, comme l'imposent les questions 2 à 4.
Je corrige silencieusement dans toute la copie.
---
# Partie I — Description probabiliste des plantes
## Question 1
**Stratégie.** Application directe de la loi des probabilités totales pour $P^{\sigma_0}(C_1=\text{blanc})$, puis de Bayes pour les probabilités a posteriori. Aucune justification demandée.
**Rédaction.** $$P^{\sigma_0}(C_1=\text{blanc}) = \sum_s \sigma_0(s)\,s_1(\text{blanc}) = 0{,}5\cdot 1 + 0{,}3\cdot 0{,}2 + 0{,}2\cdot 0 = \boxed{0{,}56}.$$
Puis $P^{\sigma_0}(S=s\mid C_1=\text{blanc}) = \dfrac{\sigma_0(s)\,s_1(\text{blanc})}{0{,}56}$ :
$$P(\text{gaillet}\mid\text{blanc}) = \frac{0{,}5}{0{,}56}=\frac{25}{28}\approx 0{,}893,\quad
P(\text{myosotis}\mid\text{blanc}) = \frac{0{,}06}{0{,}56}=\frac{3}{28}\approx 0{,}107,\quad
P(\text{lin}\mid\text{blanc}) = 0.$$
(Somme $=1$, cohérent : le lin a des fleurs bleues, il est exclu.)
**Commentaire du correcteur.** Question la mieux réussie du sujet (MP : 98 % traitée, 84 % au maximum). Le rapport la qualifie de « simple application numérique de lois classiques ». Piège d'inattention : oublier de renormaliser par $0{,}56$.
## Question 2
**Stratégie.**
Marginaliser la loi jointe $P^\sigma(\{(s,\vec v)\})=\sigma(s)\prod_i s_i(v_i)$ en exploitant que chaque $s_i$ est de masse 1 ($\sum_{v}s_i(v)=1$).
**Rédaction.**
$$P^\sigma(S=s) = \sum_{\vec v}\sigma(s)\prod_i s_i(v_i)
= \sigma(s)\prod_i\Big(\sum_{v_i\in V_i}s_i(v_i)\Big) = \sigma(s)\prod_i 1 = \boxed{\sigma(s)}.$$
$$P^\sigma(C_i=v) = \sum_s\sum_{\vec v : v_i=v}\sigma(s)\prod_j s_j(v_j)
= \sum_s \sigma(s)\,s_i(v)\!\!\prod_{j\ne i}\Big(\sum_{v_j}s_j(v_j)\Big) = \boxed{\sum_s \sigma(s)\,s_i(v)}.$$
Enfin, si $P^\sigma(S=s)=\sigma(s)>0$ : $$P^\sigma(C_i=v\mid S=s) = \frac{P^\sigma(C_i=v,S=s)}{P^\sigma(S=s)} = \frac{\sigma(s)\,s_i(v)}{\sigma(s)} = \boxed{s_i(v)},$$ car $P^\sigma(C_i=v,S=s)=\sigma(s)s_i(v)$ (même marginalisation, en fixant $s$ et $v_i=v$).
**Commentaire du correcteur.** Bien réussie (MP : 79 % au max). Le rapport insiste : il fallait *faire le calcul* et retrouver le résultat naturel ($P(S=s)=\sigma(s)$), pas simplement l'annoncer.
## Question 3
**Stratégie.** Bayes, puis simplification via la Q2. Ne pas oublier l'**interprétation informelle**, explicitement attendue.
**Rédaction.** Par la formule de Bayes, quand $P^\sigma(C_i=v)>0$ :
$$P^\sigma(S=s\mid C_i=v) = \frac{P^\sigma(C_i=v\mid S=s)\,P^\sigma(S=s)}{P^\sigma(C_i=v)}
= \boxed{\dfrac{\sigma(s)\,s_i(v)}{\displaystyle\sum_{s'}\sigma(s')\,s'_i(v)}}.$$
Elle est **bien définie ssi le dénominateur est non nul**, c.-à-d. s'il existe une espèce $s'$ avec $\sigma(s')>0$ et $s'_i(v)>0$ : autrement dit, ssi la valeur $v$ du caractère $i$ est *observable* dans l'état $\sigma$.
*Interprétation.*
On part de l'a priori $\sigma(s)$ sur l'espèce, on le **repondère par la vraisemblance** $s_i(v)$ de l'observation « caractère $i$ vaut $v$ », puis on **renormalise**.
C'est la mise à jour bayésienne de la croyance après une observation.
**Commentaire du correcteur.** Chute de réussite nette (MP : 80 % traitée mais **23 %** au max). Le rapport le dit : « l'explication informelle a souvent manqué ». Rédiger l'interprétation rapporte ici des points faciles que beaucoup ont laissés.
## Question 4
**Stratégie.**
Ne surtout **pas** invoquer l'indépendance de $C_i$ et $C_j$ : elle est fausse.
On calcule les deux membres par marginalisation et on constate l'égalité, le facteur de normalisation se simplifiant.
**Rédaction.**
Comme en Q2, en fixant $s$, $v_i=v$, $v_j=v'$ : $$P^\sigma(S=s,C_i=v,C_j=v') = \sigma(s)\,s_i(v)\,s_j(v').$$
Donc, avec $Z=\sum_{s'}\sigma(s')s'_i(v)s'_j(v')=P^\sigma(C_i=v,C_j=v')$ : $$\text{(gauche)}\quad P^\sigma(S=s\mid C_i=v,C_j=v') = \frac{\sigma(s)\,s_i(v)\,s_j(v')}{Z}.$$
Posons $\sigma'=\sigma[i:=v]$, de sorte que $\sigma'(s)=\dfrac{\sigma(s)s_i(v)}{Z_i}$ avec $Z_i=\sum_{s'}\sigma(s')s'_i(v)$.
Par la Q3 appliquée dans l'état $\sigma'$ :
$$\text{(droite)}\quad P^{\sigma'}(S=s\mid C_j=v') = \frac{\sigma'(s)\,s_j(v')}{\sum_{s'}\sigma'(s')s'_j(v')}
= \frac{\tfrac{\sigma(s)s_i(v)}{Z_i}\,s_j(v')}{\sum_{s'}\tfrac{\sigma(s')s'_i(v)}{Z_i}\,s'_j(v')}
= \frac{\sigma(s)\,s_i(v)\,s_j(v')}{\sum_{s'}\sigma(s')s'_i(v)s'_j(v')}.$$
Le facteur $Z_i$ se simplifie et le dénominateur vaut $Z$ : les deux membres coïncident. $\qquad\blacksquare$
**Commentaire du correcteur.** Question **charnière** (MP : 45 % traitée, **8 %** au max).
Le rapport avertit explicitement : « il était tentant d'utiliser un argument d'indépendance mais les événements $C_i=v$ et $C_j=v'$ ne sont pas indépendants, ils le sont uniquement conditionnés à une espèce ».
Le calcul complet est obligatoire.
## Question 5
**Stratégie.** Traductions directes. **Point clé** : le type `'x mesure` a pour invariant l'absence de poids nul ; `repondere` doit donc **filtrer** les coefficients devenus nuls.
**Rédaction.**
```ocaml
(* val proba_de : 'x -> 'x mesure -> float *)
let rec proba_de x mu =
match mu with
| [] -> 0. (* absent => poids nul *)
| (y, p) :: reste -> if y = x then p else proba_de x reste
(* val somme_ponderee : 'x mesure -> ('x -> float) -> float *)
let somme_ponderee mu f =
List.fold_left (fun acc (x, p) -> acc +. p *. f x) 0. mu
(* val repondere : 'x mesure -> ('x -> float) -> 'x mesure *)
let repondere mu f =
List.filter (fun (_, p) -> p <> 0.) (* invariant : pas de 0 *)
(List.map (fun (x, p) -> (x, p *. f x)) mu)
```
**Commentaire du correcteur.** MP : 98 % traitée mais seulement **8 %** au max. Le rapport pointe précisément le défaut massif : « il fallait bien respecter les invariants, notamment pour `proba_de` et `repondere`, de ne pas avoir de coefficients nuls dans la liste ». Le `List.filter` de `repondere` est ce qui distingue une copie notée d'une copie sanctionnée.
## Question 6
**Stratégie.** $P^{\delta_s}(C_i=v)=s_i(v)$ (Q2 avec $\sigma=\delta_s$) ; $P^\sigma(C_i=v)=\sum_s\sigma(s)s_i(v)$ (Q2).
On réutilise la Q5.
**Rédaction.**
```ocaml
(* val proba_espece : espece -> caractere -> valeur -> float *)
let proba_espece s i v = proba_de v s.mesures.(i) (* = s_i(v) *)
(* val proba_etat : etat -> caractere -> valeur -> float *)
let proba_etat sigma i v =
somme_ponderee sigma (fun s -> proba_espece s i v) (* = sum_s sigma(s) s_i(v) *)
```
**Commentaire du correcteur.** Bien réussie (MP : 70 % au max) : « simple application de la question précédente ».
## Question 7
**Stratégie.** $\sigma[i:=v](s)=\dfrac{\sigma(s)s_i(v)}{P^\sigma(C_i=v)}$ : on calcule $p=P^\sigma(C_i=v)$, on lève si $p=0$, sinon on repondère par $s\mapsto s_i(v)/p$.
**Rédaction.**
```ocaml
(* val reponse : etat -> caractere -> valeur -> etat *)
let reponse sigma i v =
let p = proba_etat sigma i v in
if p = 0. then failwith "reponse : observation impossible"
else repondere sigma (fun s -> proba_espece s i v /. p)
```
La mesure obtenue a pour poids $\sigma(s)\cdot\frac{s_i(v)}{p}$, de masse $\frac1p\sum_s\sigma(s)s_i(v)=\frac{p}{p}=1$ : c'est bien une distribution.
Le `List.filter` interne à `repondere` élimine les espèces incompatibles ($s_i(v)=0$), respectant l'invariant.
**Commentaire du correcteur.** MP : 72 % traitée, **47 %** au max. Le rapport résume la méthode attendue : « calculer la probabilité de la valeur, si nulle lever une exception, sinon utiliser `repondere` ».
---
# Partie II — Arbre optimal
## Question 8
**Stratégie.**
Énumérer les arbres de décision pour $\sigma_0=\{\text{gaillet}:0{,}5,\text{myosotis}:0{,}3,\text{lin}:0{,}2\}$ et $\{0,1\}$.
La racine est forcément un `Noeud` (état non-dirac, caractères disponibles). Deux choix de caractère racine ; la seule liberté restante est d'ajouter, ou non, une question inutile dans une branche déjà **dirac**.
**Rédaction.** Caractère 0 = pétales (gaillet : 4 ; myosotis, lin : 5). Caractère 1 = couleur (gaillet : blanc ; lin : bleu ; myosotis : 0,8 bleu / 0,2 blanc).
*Racine = caractère 0 (pétales).* $P(C_0{=}4)=0{,}5$, $P(C_0{=}5)=0{,}5$.
- Branche $C_0{=}4$ : $\sigma[0{:=}4]=\delta_{\text{gaillet}}$ (dirac) → **feuille**, hauteur 0 (une seule question a suffi).
- Branche $C_0{=}5$ : $\sigma[0{:=}5]=\{\text{myo}:0{,}6,\text{lin}:0{,}4\}$ (non-dirac) → question forcée sur le caractère 1 : bleu ($0{,}88$)→feuille, blanc ($0{,}12$)→$\delta_{\text{myo}}$ feuille.
Sous-arbre de hauteur 1.
$$h = 1 + 0{,}5\cdot 0 + 0{,}5\cdot 1 = \boxed{\tfrac32}.$$
*Racine = caractère 1 (couleur).* $P(C_1{=}\text{bleu})=0{,}44$, $P(C_1{=}\text{blanc})=0{,}56$.
Chaque branche donne un état à deux espèces, imposant une seconde question (caractère 0) : les deux branches ont hauteur 1.
$$h = 1 + 0{,}44\cdot 1 + 0{,}56\cdot 1 = 2.$$
*Troisième arbre* : racine caractère 0, mais en ajoutant dans la branche dirac $C_0{=}4$ une question **inutile** sur la couleur (bleu impossible, blanc→gaillet) : sous-arbre de hauteur 1, d'où $h = 1+0{,}5\cdot1+0{,}5\cdot1 = 2$.
**Il y a donc trois arbres de décision, de hauteurs moyennes $\tfrac32,\ 2,\ 2$. L'arbre optimal enracine sur le nombre de pétales (caractère 0), de hauteur $\boxed{\tfrac32}$.**
Pour l'arbre représenté dans l'énoncé (hauteur 2, celui de racine « couleur »), les probabilités des arcs valent : à la racine $p=P(C_1{=}\text{bleu})=0{,}44=\tfrac{11}{25}$ et $q=P(C_1{=}\text{blanc})=0{,}56=\tfrac{14}{25}$ ; sous la branche blanche, le caractère 0 vaut 4 avec proba $\tfrac{25}{28}$ et 5 avec proba $\tfrac{3}{28}$ (cf. Q1).
> **[Point non entièrement établi : identification exacte de $p$ et $q$ sur la figure.]**
Le fichier ne fournit pas l'image `img-0.jpeg`.
Je donne ci-dessus **toutes** les probabilités d'arcs de l'arbre de hauteur 2 ; $p$ et $q$ en sont deux, très probablement les deux arcs de la racine ($0{,}44$ et $0{,}56$).
**Commentaire du correcteur.** MP : 82 % traitée, **32 %** au max. Le rapport donne la clé : « dans l'autre ordre des questions, il y a une branche de hauteur 1, ce qui fait un arbre plus petit en moyenne » — c'est exactement la branche $C_0{=}4$ qui identifie le gaillet en une seule question. L'erreur classique est de ne pas voir que la feuille dirac termine la branche.
## Question 9
**Stratégie.** C'est le **produit cartésien** d'un tableau de listes. Récursion sur les listes : pour la première liste, préfixer chaque élément à chaque combinaison du reste. `List.concat_map` donne la solution la plus courte.
**Rédaction.**
```ocaml
(* val choix_possibles : 'x list array -> 'x array list *)
let choix_possibles (tab : 'x list array) : 'x array list =
let listes = List.init (Array.length tab) (fun i -> tab.(i)) in
let rec produit = function
| [] -> [[]] (* une seule combinaison : la vide *)
| l :: reste ->
let suites = produit reste in
List.concat_map (fun x -> List.map (fun s -> x :: s) suites) l
in
List.map Array.of_list (produit listes)
```
Sur `[| [1;2]; [3;4;5] |]`, on obtient bien, dans l'ordre lexicographique attendu,
`[ [|1;3|];[|1;4|];[|1;5|];[|2;3|];[|2;4|];[|2;5|] ]`.
**Commentaire du correcteur.** Question **difficile et clivante** (MP : 38 % traitée, 13 % max ; MPI bien mieux). Le rapport confirme : « calculer le produit cartésien d'un tableau de listes ; la solution récursive avec `List.concat_map` est la plus courte, d'autres solutions impératives ont été acceptées ».
## Question 10
**Stratégie.** Énumération récursive.
Pour un état $\sigma$ et un ensemble de caractères, un arbre de décision est soit une **feuille** (si dirac ou plus de caractère), soit un **nœud** sur un caractère $i$ ; pour chaque valeur, la récursion fournit une *liste* de sous-arbres possibles, et `choix_possibles` recombine un sous-arbre par enfant.
**Rédaction.**
```ocaml
let est_dirac (sigma : etat) : bool = List.length sigma = 1
(* tous les arbres de decision pour (sigma, cs) *)
let rec enumere_aux (sigma : etat) (cs : caractere list) : arbre list =
let feuilles = if cs = [] || est_dirac sigma then [Feuille sigma] else [] in
let noeuds =
List.concat_map (fun i ->
let cs' = List.filter (fun c -> c <> i) cs in
(* pour chaque valeur v : la liste des (proba, sous-arbre) possibles *)
let options =
List.init num.(i) (fun v ->
let p = proba_etat sigma i v in
if p = 0. then [(0., Impossible)]
else List.map (fun t -> (p, t)) (enumere_aux (reponse sigma i v) cs'))
in
List.map (fun enfants -> Noeud {caractere = i; enfants})
(choix_possibles (Array.of_list options)))
cs
in
feuilles @ noeuds
(* val enumere : etat -> arbre list *)
let enumere (sigma : etat) : arbre list = enumere_aux sigma caracteres
```
*Terminaison* : chaque appel récursif retire $i$ de `cs`, dont la longueur décroît strictement. *Correction* : on produit exactement les feuilles autorisées (dirac ou `cs=[]`) et tous les nœuds bien formés ; sur l'exemple de la Q8 on retrouve les 3 arbres.
**Commentaire du correcteur.** « Une des questions les plus difficiles du sujet » (MP : 10 % traitée, **1 %** max). Le rapport décrit précisément la difficulté : « la récursion donne une liste de possibilités pour chaque enfant, il faut ensuite retourner toutes les possibilités en choisissant une possibilité par enfant, avec `choix_possibles` ».
## Question 11
**Stratégie.** `argmin` par un simple `fold_left` gardant le meilleur couple `(élément, score)`. La hauteur moyenne se calcule par la formule récursive de l'énoncé.
**Rédaction.**
```ocaml
(* val argmin : 'x list -> ('x -> float) -> 'x *)
let argmin (l : 'x list) (f : 'x -> float) : 'x =
match l with
| [] -> invalid_arg "argmin : liste vide"
| x0 :: reste ->
fst (List.fold_left
(fun (meilleur, score) x ->
let s = f x in if s < score then (x, s) else (meilleur, score))
(x0, f x0) reste)
(* hauteur moyenne h(t) *)
let rec hauteur (t : arbre) : float =
match t with
| Feuille _ | Impossible -> 0.
| Noeud {enfants; _} ->
1. +. Array.fold_left (fun acc (p, tv) -> acc +. p *. hauteur tv) 0. enfants
(* val arbre_optimal : etat -> arbre *)
let arbre_optimal (sigma0 : etat) : arbre = argmin (enumere sigma0) hauteur
```
**Commentaire du correcteur.** MP : 58 % traitée, 30 % max. Le rapport : « question simple qui nécessite le calcul de la hauteur moyenne d'un arbre ». `arbre_optimal` s'obtient en une ligne à partir de `enumere` et `argmin`.
---
# Partie III — Algorithme glouton
## Question 12
**Stratégie.**
Minorer $H\ge0$ terme à terme (diracs) ; majorer $H\le\ln k$ par l'inégalité de **Jensen** appliquée à la concavité de $\ln$ (distribution uniforme).
**Rédaction.** Soit $k=|X|\ge1$.
Pour tout $x$, $0\le\mu(x)\le1$ donc $\ln\mu(x)\le0$ et $-\mu(x)\ln\mu(x)\ge0$ : ainsi $H(\mu)\ge0$.
L'égalité $H=0$ a lieu ssi chaque terme est nul, i.e. $\mu(x)\in\{0,1\}$, donc pour les **diracs** $\delta_x$.
**Minimum $=0$, atteint aux diracs.**
Pour le maximum, écrivons $H(\mu)=\sum_{x:\mu(x)>0}\mu(x)\ln\frac{1}{\mu(x)}$.
Par concavité de $\ln$ (Jensen, poids $\mu(x)$ de somme 1) : $$H(\mu) = \sum_{\mu(x)>0}\mu(x)\ln\frac{1}{\mu(x)} \le \ln\!\Big(\sum_{\mu(x)>0}\mu(x)\cdot\tfrac{1}{\mu(x)}\Big) = \ln\big(|\{x:\mu(x)>0\}|\big) \le \ln k.$$
Égalité ssi $\frac{1}{\mu(x)}$ est constant sur le support et le support est $X$ tout entier, i.e. $\mu(x)=\frac1k$ (**uniforme**).
On vérifie $H(\text{unif}) = -\sum_x\frac1k\ln\frac1k=\ln k$.
**Maximum $=\ln k$, atteint à l'uniforme** (pour $k=1$, min et max coïncident à $0=\ln1$).
**Commentaire du correcteur.** MP : 77 % traitée mais **12 %** max. Le rapport : « pour conclure que l'uniforme maximise $H$, on peut utiliser l'inégalité de Jensen sur le logarithme, mais relativement peu de copies ont trouvé cet argument ». Le minimum (diracs) est facile ; c'est la borne $\ln k$ par Jensen qui rapporte.
## Question 13
**Stratégie.** Traduire $H_i(\sigma)=\sum_{v\in V_i}P^\sigma(C_i{=}v)\,H(\sigma[i{:=}v])$. **Piège** : ne sommer que sur les $v$ de proba non nulle, sinon `reponse` lève une exception.
**Rédaction.**
```ocaml
(* entropie H(mu) = - sum_x mu(x) ln mu(x) *)
let entropie (mu : 'x mesure) : float =
-. List.fold_left (fun acc (_, p) -> acc +. p *. log p) 0. mu
(* val score_caractere : etat -> caractere -> float *)
let score_caractere (sigma : etat) (i : caractere) : float =
List.fold_left
(fun acc v ->
let p = proba_etat sigma i v in
if p = 0. then acc (* terme nul, on evite reponse *)
else acc +. p *. entropie (reponse sigma i v))
0. (List.init num.(i) (fun v -> v))
```
**Commentaire du correcteur.** MP : 64 % traitée mais **2 %** max — la question la plus « piégeuse » de la partie.
Le rapport est formel : l'énoncé sous-entend une somme restreinte aux $v$ tels que $P^\sigma(C_i{=}v)\ne0$, « mais dans le code, il faut bien l'expliciter, sinon le calcul de $\sigma[i:=v]$ lève une exception ».
Le `if p = 0. then acc` vaut tous les points.
## Question 14
**Stratégie.** Comme `enumere` mais **sans choix** : à chaque nœud on prend l'unique caractère minimisant `score_caractere`, et on descend récursivement.
**Rédaction.**
```ocaml
(* val glouton : etat -> arbre *)
let glouton (sigma0 : etat) : arbre =
let rec construire sigma cs =
if cs = [] || est_dirac sigma then Feuille sigma
else
let i = argmin cs (score_caractere sigma) in (* caractere le plus discriminant *)
let cs' = List.filter (fun c -> c <> i) cs in
let enfants =
Array.init num.(i) (fun v ->
let p = proba_etat sigma i v in
if p = 0. then (0., Impossible)
else (p, construire (reponse sigma i v) cs'))
in
Noeud {caractere = i; enfants}
in
construire sigma0 caracteres
```
*Terminaison* : `cs` décroît. *Correction* : arbre de décision bien formé (feuille seulement en dirac/`cs=[]`, `Impossible` pour $p=0$).
**Commentaire du correcteur.** MP : 25 % traitée, 5 % max. Le rapport : « similaire à `enumere` mais plus simple, car on calcule un seul arbre : il n'y a pas de choix entre plusieurs possibilités ».
## Question 15
**Stratégie.**
Dessiner les deux arbres pour $\sigma_0=\{a:0{,}2,b:0{,}4,c:0{,}4\}$ ($a=(\delta_{\text{oui}},\tfrac12\delta_{\text{oui}}{+}\tfrac12\delta_{\text{non}})$, $b=(\delta_{\text{non}},\delta_{\text{oui}})$, $c=(\delta_{\text{non}},\delta_{\text{non}})$) et comparer.
**Rédaction.**
*Racine = caractère 0.* $P(C_0{=}\text{oui})=0{,}2$ → $\delta_a$ (feuille) ; $P(C_0{=}\text{non})=0{,}8$ → $\{b:0{,}5,c:0{,}5\}$, question caractère 1 (oui→$\delta_b$, non→$\delta_c$), sous-arbre hauteur 1. $$h = 1 + 0{,}2\cdot0 + 0{,}8\cdot1 = 1{,}8.$$
*Racine = caractère 1.* $P(C_1{=}\text{oui})=0{,}5$ → $\{a:0{,}2,b:0{,}8\}$ ; $P(C_1{=}\text{non})=0{,}5$ → $\{a:0{,}2,c:0{,}8\}$ ; chaque branche redemande le caractère 0 (hauteur 1). $$h = 1 + 0{,}5\cdot1 + 0{,}5\cdot1 = 2.$$
**L'arbre optimal enracine sur le caractère 0, de hauteur $\boxed{1{,}8}$** (le caractère 0 identifie l'espèce rare $a$ d'un coup).
**Commentaire du correcteur.** MP : 36 % traitée, 27 % max — « relativement bien traitée ». Le rapport : « dessiner les deux arbres et se rendre compte que l'un est légèrement plus petit » ($1{,}8<2$).
## Question 16
**Stratégie.**
Calculer $H_0(\sigma_0)$ et $H_1(\sigma_0)$ ; montrer que le glouton choisit le caractère de plus petite entropie moyenne, ici le caractère 1 — donc **l'arbre sous-optimal** de la Q15.
**Rédaction.** $$H_0(\sigma_0) = 0{,}2\cdot H(\delta_a) + 0{,}8\cdot H(\{b:\tfrac12,c:\tfrac12\}) = 0 + 0{,}8\,\ln 2 = \tfrac{4}{5}\ln 2.$$
Pour le caractère 1, les deux états mis à jour sont $\{a:0{,}2,\cdot:0{,}8\}$, de même entropie $h=-(0{,}2\ln0{,}2+0{,}8\ln0{,}8)=\ln5-\tfrac{8}{5}\ln2$ : $$H_1(\sigma_0) = 0{,}5\,h + 0{,}5\,h = \ln5 - \tfrac{8}{5}\ln 2.$$
Comparaison : $H_1<H_0 \iff \ln5-\tfrac85\ln2<\tfrac45\ln2 \iff \ln5<\tfrac{12}{5}\ln2$, **vrai** par l'indication admise.
Numériquement $H_1\approx0{,}500<H_0\approx0{,}555$.
**Conclusion.**
Le glouton minimise l'entropie moyenne, donc choisit le **caractère 1** à la racine — l'arbre de hauteur $2$, alors que l'optimal (caractère 0) a hauteur $1{,}8$.
**L'algorithme glouton n'est donc pas optimal.** $\qquad\blacksquare$
**Commentaire du correcteur.** MP : 24 % traitée, 15 % max. Le rapport : « le but est de montrer que l'algorithme glouton ne calcule pas l'arbre optimal dans cet exemple ». L'indication $\ln5<\tfrac{12}5\ln2$ est exactement ce qu'il faut pour conclure sans calculatrice (interdite ici).
---
# Partie IV — Optimisation de l'algorithme naïf
> Cette partie, quasi vierge (Q17-20 : 1 à 3 % de copies), était le principal **différenciateur**. Les questions demandent une preuve de programme rigoureuse.
## Question 17
**Stratégie.** Repérer que `arbre_optimal_avec_oracle`, quand `caracteres ≠ []`, ne renvoie **jamais** de `Feuille` : elle explore uniquement les arbres à racine `Noeud`. Sa correction exige donc que la feuille ne soit **pas** optimale (état non-dirac), et un oracle correct sur les sous-appels.
**Rédaction.
Préconditions** pour que `arbre_optimal_avec_oracle oracle σ C` **termine** et renvoie $(t,h(t))$ avec $t$ optimal pour $(C,\sigma)$ :
1. **(État)** $\sigma$ est un état valide : $\sigma\in D(\mathcal S)$ (mesure de masse 1, sans poids nul).
2. **(Caractères)** $C$ est une liste de caractères **deux à deux distincts**, tous dans $\{0,\dots,N-1\}$.
3. **(Non-trivialité)** $C=[\,]$ **ou** $\sigma$ n'est pas un dirac.
*En effet*, si $\sigma=\delta_s$ et $C\ne[\,]$, la feuille `Feuille σ` (hauteur 0) est un arbre de décision optimal, que la fonction ne peut pas produire : la précondition l'exclut.
4. **(Oracle)** Pour tous $i\in C$ et $v\in V_i$ tels que $P^\sigma(C_i{=}v)>0$, en posant $\sigma'=\sigma[i{:=}v]$ et $C'=C\setminus\{i\}$, l'appel `oracle σ' C'` **termine** et renvoie $(t',h(t'))$ où $t'$ est un arbre **optimal** pour $(C',\sigma')$.
Sous ces hypothèses, la boucle `while` (finie, sur $C$) et les `Array.init` terminent, et la fonction renvoie l'optimum (démontré en Q18).
**Commentaire du correcteur.** MP : **3 %** traitée, 0 % max. Le rapport confirme le cœur attendu : « énoncer les préconditions de `arbre_optimal_avec_oracle`, en particulier sur `oracle` ». La précondition 3 (non-dirac) est subtile mais nécessaire à la rigueur ; elle est réparée en Q19 par un test de dirac.
## Question 18
**Stratégie.** Invariant de la boucle `while` : `arbre_optimal` contient le meilleur nœud dont la racine est un caractère **déjà testé**.
La clé est que, pour une racine $i$ fixée, la hauteur $1+\sum_v p_v h(t_v)$ se minimise **enfant par enfant indépendamment**, ce que fournit l'oracle.
**Rédaction.**
Pour $i\in C$, notons $\mathrm{score}_i = 1+\sum_{v}P^\sigma(C_i{=}v)\,h_v$, où $h_v=0$ si $P^\sigma(C_i{=}v)=0$ (enfant `Impossible`) et sinon $h_v=h(t'_v)$ avec $t'_v$ l'arbre **optimal** de `oracle σ[i:=v] (C\{i})`.
Comme $h(\texttt{Noeud}_i)=1+\sum_v p_v h(t_v)$ avec les $p_v\ge0$ fixés et les $t_v$ indépendants, le nœud de racine $i$ de hauteur minimale a exactement pour hauteur $\mathrm{score}_i$ (chaque enfant pris optimal).
**Invariant de boucle.**
Soit $T$ l'ensemble des caractères déjà retirés de `!caracteres_a_tester` (les caractères déjà testés — c'est un préfixe de $C$, car on dépile par `List.tl`).
Après chaque tour :
$$\texttt{!arbre\_optimal} = \begin{cases}\texttt{Some}\ a,\ h(a)=\texttt{!score\_optimal}=\min_{i\in T}\mathrm{score}_i,\ a\ \text{minimiseur} & \text{si } T\ne\emptyset\\ \texttt{None},\ \texttt{!score\_optimal}=+\infty & \text{si } T=\emptyset.\end{cases}$$
*Initialisation* : avant la boucle $T=\emptyset$, `arbre_optimal=None`, `score_optimal=∞`. ✓
*Conservation* : le tour courant traite $i=$ tête de `!caracteres_a_tester`.
Il construit `enfants` (enfants optimaux via l'oracle) et `score_total`$=1+\sum_v p_v\cdot\texttt{score\_sous\_arbre}=\mathrm{score}_i$ (les enfants `Impossible` ont $p_v=0$, contribution nulle).
Le test `score_total < score_optimal` met à jour vers le minimiseur de $T\cup\{i\}$. L'invariant tient avec $T\cup\{i\}$. ✓
*Terminaison* : `!caracteres_a_tester` raccourcit strictement (`List.tl`) à chaque tour → atteint `[]`. ✓
*Conclusion.*
À la sortie, $T=C$, donc `score_optimal`$=\min_{i\in C}\mathrm{score}_i$.
Par la précondition 3 ($\sigma$ non-dirac, $C\ne[]$), **tout** arbre de décision pour $(C,\sigma)$ a une racine `Noeud` sur un $i\in C$, donc de hauteur $\ge\mathrm{score}_i\ge\min_{i\in C}\mathrm{score}_i$ : le minimum est atteint et `arbre_optimal` en est un témoin.
La fonction renvoie $(a,h(a))$ avec $a$ optimal. $\qquad\blacksquare$
**Commentaire du correcteur.** MP : **1 %** traitée. Le rapport donne exactement l'invariant attendu : « à chaque tour, `arbre-optimal` contient l'arbre optimal parmi tous ceux ayant pour racine un critère déjà testé, ou rien si aucun critère n'a été testé ».
## Question 19
**Stratégie.** « Fermer la récursion » : définir `arbre_optimal` récursive qui se passe elle-même comme oracle. **Ajout nécessaire** : traiter le cas dirac par une feuille (précondition 3 de la Q17), sinon on renverrait un `Noeud` de hauteur $\ge1$ au lieu de la feuille optimale (hauteur 0).
**Rédaction.**
```ocaml
(* val arbre_optimal : etat -> caractere list -> arbre * float *)
let rec arbre_optimal (etat : etat) (caracteres : caractere list) : arbre * float =
if caracteres <> [] && est_dirac etat then (Feuille etat, 0.) (* feuille optimale *)
else arbre_optimal_avec_oracle arbre_optimal etat caracteres
```
**Spécification** : `arbre_optimal σ C` termine et renvoie $(t,h(t))$ avec $t$ optimal pour $(C,\sigma)$, dès que $C$ est une liste de caractères distincts et $\sigma$ un état valide.
**Preuve par récurrence sur $|C|$.**
- *Base $|C|=0$* : `caracteres=[]`, le test est faux, on appelle `arbre_optimal_avec_oracle` qui renvoie `(Feuille σ, 0.)` — seul arbre pour $(\emptyset,\sigma)$, donc optimal. ✓
- *Hérédité $|C|=n>0$* : par HR, pour tout $C'$ avec $|C'|<n$ et tout $\sigma'$, `arbre_optimal σ' C'` renvoie l'optimum ; en particulier l'oracle appelé sur $C\setminus\{i\}$ ($|C\setminus\{i\}|=n-1$) satisfait la précondition 4.
Deux cas :
- $\sigma$ dirac : on renvoie `(Feuille σ, 0.)`, optimal (feuille valide, hauteur 0 minimale). ✓
- $\sigma$ non-dirac : les préconditions 1-4 de la Q17 sont réunies, donc par la Q18 l'appel renvoie l'optimum. ✓
Les caractères restent distincts le long de la récursion (on n'en retire jamais deux fois le même). La récurrence est bien fondée car l'oracle est toujours appelé sur un ensemble de caractères **strictement plus petit**. $\qquad\blacksquare$
**Commentaire du correcteur.** MP : **2 %** traitée. Le rapport : « fermer la récursion, déclarer une fonction récursive qui appelle `arbre-optimal-avec-oracle` avec elle-même ; la preuve se fait par induction sur le nombre de critères ».
> **Honnêteté.** Le rapport ne mentionne pas explicitement le garde-dirac ; mais sans lui la fonction renverrait un arbre **strictement sous-optimal** dès qu'un état devient dirac avant épuisement des caractères (elle donnerait hauteur 2 au lieu de $\tfrac32$ sur l'exemple de la Q8). Le garde est donc indispensable pour coïncider avec l'`arbre_optimal` de la partie II.
## Question 20
**Stratégie.** *Branch-and-bound* : ajouter une **borne** (score à ne pas dépasser). On construit les enfants d'un caractère en accumulant le score partiel ; dès qu'il atteint la borne, on **abandonne** ce caractère. On resserre la borne à chaque arbre complet trouvé, meilleur que le précédent.
**Rédaction.**
```ocaml
(* val arbre_optimal_opt : etat -> caractere list -> float -> (arbre * float) option
Renvoie Some (t, h(t)) avec t optimal si l'optimum est <= borne, sinon None. *)
let rec arbre_optimal_opt (etat : etat) (caracteres : caractere list)
(borne : float) : (arbre * float) option =
if caracteres = [] || est_dirac etat then
(if 0. <= borne then Some (Feuille etat, 0.) else None) (* feuille, hauteur 0 *)
else begin
let meilleur = ref None in
let borne_courante = ref borne in (* se resserre a chaque amelioration *)
List.iter (fun i ->
let cs' = List.filter (fun c -> c <> i) caracteres in
let acc = ref 1. in (* score partiel du noeud i *)
let enfants = Array.make num.(i) (0., Impossible) in
let abandon = ref false in
let v = ref 0 in
while (not !abandon) && !v < num.(i) do
let p = proba_etat etat i !v in
(if p = 0. then enfants.(!v) <- (0., Impossible)
else
(* il faut acc + p*h_v <= borne_courante, donc h_v <= (borne_courante - acc)/p *)
let borne_enfant = (!borne_courante -. !acc) /. p in
match arbre_optimal_opt (reponse etat i !v) cs' borne_enfant with
| None -> abandon := true (* i ne peut plus battre la borne *)
| Some (t_v, h_v) ->
enfants.(!v) <- (p, t_v);
acc := !acc +. p *. h_v);
incr v
done;
if (not !abandon) && !acc <= !borne_courante then begin
meilleur := Some (Noeud {caractere = i; enfants}, !acc);
borne_courante := !acc (* borne resserree *)
end)
caracteres;
!meilleur
end
```
*Idée de correction* : si un enfant renvoie `None`, son optimum dépasse $(\texttt{borne}-\texttt{acc})/p$, donc $\texttt{acc}+p\cdot h_v>\texttt{borne}$ même en ignorant les enfants restants ($\ge0$) : abandonner $i$ est sûr.
La borne ne fait que décroître, restant un majorant valide de l'optimum.
**Commentaire du correcteur.** « Sans doute la question la plus difficile du sujet » (MP : **1 %** traitée, 0 % max). Le rapport : « ajouter une approche *branch and bound* qui coupe le calcul d'un arbre dès que son score dépasse celui de l'arbre optimal ». La preuve n'était pas demandée.
> **Honnêteté.** L'énoncé laisse une légère ambiguïté strict/large sur « dépasser ». J'ai retenu : `None` ssi l'optimum $>$ `borne` (seuil large). Un choix strict changerait seulement les tests `<=`/`<`, sans toucher au principe.
---
# Partie V — Observations complexes et formules logiques
## Question 21
**Stratégie.** Équivalence entre « mêmes modèles déterministes » et « mêmes probabilités partout ». Sens direct par égalité des ensembles de modèles ; réciproque en spécialisant aux modèles **diracs** $(\delta_{w_i})_i$.
**Rédaction.** Notons $\mathrm{Mod}(\varphi)=\{\vec v\in\vec V:\vec v\models\varphi\}$.
$(\Rightarrow)$ Si $\mathrm{Mod}(\varphi)=\mathrm{Mod}(\psi)$, alors pour tout modèle probabiliste $\vec d$ : $$P(\vec d\models\varphi)=\!\!\sum_{\vec v\in\mathrm{Mod}(\varphi)}\prod_i d_i(v_i) = \!\!\sum_{\vec v\in\mathrm{Mod}(\psi)}\prod_i d_i(v_i) = P(\vec d\models\psi).$$
$(\Leftarrow)$ Pour tout modèle déterministe $\vec w$, prenons $\vec d=(\delta_{w_0},\dots,\delta_{w_{N-1}})$.
Alors $\prod_i d_i(v_i)=1$ si $\vec v=\vec w$ et $0$ sinon, d'où $P(\vec d\models\varphi)=\mathbf 1[\vec w\models\varphi]$.
L'hypothèse $P(\vec d\models\varphi)=P(\vec d\models\psi)$ donne $\mathbf 1[\vec w\models\varphi]=\mathbf 1[\vec w\models\psi]$, i.e. $\vec w\models\varphi\iff\vec w\models\psi$, pour tout $\vec w$. $\qquad\blacksquare$
**Commentaire du correcteur.** MP : 33 % traitée, 22 % max — « assez directe en dépliant les définitions ». L'astuce des diracs pour la réciproque est le seul point technique.
## Question 22
**Stratégie.** Compter les modèles déterministes puis le coût par modèle (produit + test de satisfaction).
**Rédaction.**
L'algorithme naïf parcourt $\vec V=V_0\times\dots\times V_{N-1}$, soit $\prod_i|V_i|\le K^N$ modèles.
Pour chaque $\vec v$ :
- calcul de $\prod_i d_i(v_i)$ : $N$ facteurs, chaque $d_i(v_i)$ étant une recherche dans une distribution-liste de taille $\le K$, soit $O(NK)$ ;
- test $\vec v\models\varphi$ : parcours récursif de $\varphi$ ; chaque atome $c_i\in V$ teste $v_i\in V$ en $O(|V|)$, et $\sum_{\text{atomes}}|V|\le|\varphi|$ : coût $O(|\varphi|)$.
Coût total : $\boxed{O\big(K^N\,(NK+|\varphi|)\big)}$ (le nombre exact de modèles est $\prod_i|V_i|$).
Le facteur exponentiel $K^N$ domine.
> **Hypothèses explicitées** : distributions et modèles codés par listes/tableaux, d'où $d_i(v_i)$ en $O(K)$.
Avec des tableaux d'accès $O(1)$, on aurait $O(K^N(N+|\varphi|))$.
**Commentaire du correcteur.** MP : 24 % traitée, 4 % max — « plutôt bien réussie même si la formule exacte est rarement trouvée ».
L'essentiel : identifier le facteur $\prod_i|V_i|\le K^N$ et un coût par modèle en $O(N+|\varphi|)$-ish.
## Question 23
**Stratégie.** Une **clause** = conjonction d'atomes sur des caractères **distincts**. Les caractères étant indépendants dans le modèle, la probabilité **se factorise** en produit de probabilités par caractère.
**Rédaction.**
Soit $\varphi=\bigwedge_{k=1}^m (c_{i_k}\in V_k)$ avec les $i_k$ distincts.
Les contraintes ne portent que sur des coordonnées distinctes, donc en marginalisant les coordonnées libres (chacune de somme 1) : $$P(\vec d\models\varphi) = \sum_{\vec v:\ \forall k,\ v_{i_k}\in V_k}\ \prod_i d_i(v_i) = \prod_{k=1}^m\Big(\sum_{v\in V_k} d_{i_k}(v)\Big).$$
**Algorithme** : pour chaque atome $k$, calculer $q_k=\sum_{v\in V_k}d_{i_k}(v)$ (parcourir la liste $d_{i_k}$, $\le K$ entrées, en ajoutant celles dont la valeur $\in V_k$, test $O(|V_k|)$), puis renvoyer $\prod_k q_k$.
**Complexité** : $\sum_k O(K\,|V_k|)=O\big(K\sum_k|V_k|\big)=O(K\,|\varphi|)$ pour les $q_k$, plus $O(m)$ pour le produit.
Total $\boxed{O(K\,|\varphi|)}$, **indépendant de $N$**.
Correction : justifiée par la factorisation ci-dessus (caractères distincts et indépendants).
**Commentaire du correcteur.** MP : 12 % traitée, 4 % max. Le rapport : « évaluer une clause par induction sur sa structure, la conjonction se transformant en produit des probabilités grâce à la structure des clauses ».
## Question 24
**Stratégie.** La conjonction de deux clauses est « presque » une clause ; seul un caractère commun pose problème, résolu par $c_i\in V_1\wedge c_i\in V_2\equiv c_i\in(V_1\cap V_2)$.
**Rédaction.**
Soit $\varphi=\bigwedge_{i\in A}(c_i\in U_i)$ et $\psi=\bigwedge_{i\in B}(c_i\in W_i)$ ($A,B$ ensembles de caractères, atomes distincts).
Définissons la clause $\varphi\,\overline\wedge\,\psi$ sur les caractères $A\cup B$ : $$c_i\in\begin{cases}U_i\cap W_i & i\in A\cap B\\ U_i & i\in A\setminus B\\ W_i & i\in B\setminus A.\end{cases}$$
Les caractères y sont distincts : c'est bien une clause.
Équivalence (via Q21, modèles déterministes) : $\vec v\models\varphi\wedge\psi\iff(\forall i\in A,\ v_i\in U_i)\wedge(\forall i\in B,\ v_i\in W_i)\iff\forall i\in A\cup B,\ v_i\in(\text{ensemble ci-dessus})\iff\vec v\models\varphi\,\overline\wedge\,\psi$. $\qquad\blacksquare$
**Commentaire du correcteur.** MP : 11 % traitée, 6 % max.
Le rapport : « la conjonction de deux clauses est presque déjà une clause, sauf si elles parlent du même critère, auquel cas $c_i\in V_1\wedge c_i\in V_2$ équivaut à $c_i\in(V_1\cap V_2)$ ».
## Question 25
**Stratégie.**
Forme normale disjonctive : induction structurelle sur $\varphi$, le cas conjonction utilisant la distributivité $\wedge/\vee$ puis la Q24.
**Rédaction.**
On montre que toute $\varphi$ est équivalente à une disjonction de clauses, par induction sur $\varphi$.
- **Atome** $c_i\in V$ : c'est déjà une clause ($m=1$). ✓
- **Disjonction** $\varphi=\psi_1\vee\dots\vee\psi_p$ : par HR $\psi_j\equiv\bigvee_l\chi_{j,l}$ (clauses), donc $\varphi\equiv\bigvee_{j,l}\chi_{j,l}$, disjonction de clauses (concaténation).
Cas $p=0$ : $\bot$ = disjonction de $0$ clause. ✓
- **Conjonction** $\varphi=\psi_1\wedge\dots\wedge\psi_p$ : par HR $\psi_j\equiv\bigvee_l\chi_{j,l}$.
Par distributivité (justifiée par Q21 : $\vec v\models\bigwedge_j\bigvee_l\chi_{j,l}\iff\exists(l_1,\dots,l_p),\ \forall j,\ \vec v\models\chi_{j,l_j}$), $$\varphi\equiv\bigvee_{(l_1,\dots,l_p)}\big(\chi_{1,l_1}\wedge\dots\wedge\chi_{p,l_p}\big).$$
Chaque conjonction de clauses $\chi_{1,l_1}\wedge\dots\wedge\chi_{p,l_p}$ est, par itération de la Q24, équivalente à **une** clause.
Donc $\varphi$ est une disjonction de clauses.
Cas $p=0$ : $\top$ = clause vide. $\qquad\blacksquare$
**Commentaire du correcteur.** MP : 7 % traitée, 1 % max. Le rapport : « simple induction sur $\varphi$, le cas difficile de la conjonction étant traité à la question d'avant » (Q24).
## Question 26
**Stratégie.**
Mettre $\varphi$ en DNF (Q25), puis évaluer la disjonction de clauses par **inclusion-exclusion** : $P(A\vee B)=P(A)+P(B)-P(A\wedge B)$, chaque conjonction de clauses redevenant une clause (Q24) évaluée par la Q23.
**Rédaction.** **Algorithme** :
1. Calculer une DNF $\varphi\equiv\varphi_1\vee\dots\vee\varphi_m$ (clauses, Q25).
2.
Par la formule du crible : $$P(\vec d\models\varphi) = \sum_{\emptyset\ne J\subseteq\{1,\dots,m\}}(-1)^{|J|+1}\,P\big(\vec d\models\textstyle\overline\bigwedge_{k\in J}\varphi_k\big),$$ où $\overline\bigwedge_{k\in J}\varphi_k$ est **une clause** (Q24 itérée, éventuellement insatisfiable → probabilité 0), évaluée en $O(K|\varphi|)$ par la Q23.
Équivalent, formulation récursive : $P(\varphi_1\vee R)=P(\varphi_1)+P(R)-P\big((\varphi_1\overline\wedge\varphi_2)\vee\dots\vee(\varphi_1\overline\wedge\varphi_m)\big)$, où chaque $\varphi_1\overline\wedge\varphi_k$ est une clause.
**Complexité** : $2^m$ (ou $O(m!)$ selon la variante) sous-ensembles, chacun combinant/évaluant des clauses en temps $\mathrm{poly}(K,|\varphi|)$.
Le nombre $m$ de clauses peut être exponentiel en $|\varphi|$ (distribution des conjonctions).
Total : **exponentiel en $|\varphi|$ mais totalement indépendant de $N$** (toutes les opérations — Q23, Q24 — le sont). $\qquad\blacksquare$
**Commentaire du correcteur.** MP : **2 %** traitée, 0 % max.
Le rapport donne exactement la voie : « la mise en clause a une complexité acceptable, et on évalue une disjonction de clauses avec la formule classique $P(A\vee B)=P(A)+P(B)-P(A\cap B)$, ce qui mène à une complexité exponentielle en la taille de la formule mais indépendante de $N$ ».
---
*Fin du corrigé. Les 26 questions sont traitées. Seul point de figure non vérifiable : l'identification exacte de $p,q$ sur l'image `img-0.jpeg` de la Q8 (toutes les probabilités d'arcs sont néanmoins fournies).*