Corrigé X-ENS 2025 Informatique A MP — Partie III (Q12 à Q16) : Algorithme glouton fondé sur l'entropie, et sa non-optimalité

Q12. Il faut $k\ge 1$ ($D(\varnothing )$ est vide). Notons $\Sigma =\{x\in X\mid \mu (x)\ne 0\}$ le support de $\mu$, non vide.

Minimum : $0$, atteint exactement par les diracs. Pour $t\in ]0,1]$, $-t\ln t\ge 0$, avec égalité si et seulement si $t=1$. Donc $H(\mu )\ge 0$, et $H(\mu )=0$ si et seulement si $\mu (x)=1$ pour tout $x\in \Sigma$ ; la masse valant $1$, c'est que $\Sigma$ est un singleton, c'est-à-dire que $\mu ={\delta }_x$. Réciproquement $H({\delta }_x)=-1\cdot \ln 1=0$.

Maximum : $\ln k$, atteint exactement par la distribution uniforme. On utilise $\ln t\le t-1$ pour $t>0$, avec égalité si et seulement si $t=1$ (concavité de $\ln$) :

$$H(\mu )-\ln k=\sum _{x\in \Sigma }\mu (x)\ln \frac{1}{k\mu (x)}\le \sum _{x\in \Sigma }\mu (x)(\frac{1}{k\mu (x)}-1)=\frac{|\Sigma |}{k}-1\le 0,$$

où l'on a utilisé ${\sum }_{x\in \Sigma }\mu (x)=1$. Il y a égalité si et seulement si $k\mu (x)=1$ pour tout $x\in \Sigma$ et $|\Sigma |=k$, c'est-à-dire si $\mu$ est la distribution uniforme $x\mapsto 1/k$, pour laquelle $H=-k\cdot \frac{1}{k}\ln \frac{1}{k}=\ln k$. (C'est l'inégalité de Jensen pour la fonction concave $\ln$, appliquée aux valeurs $1/\mu (x)$.) Pour $k=1$, minimum et maximum valent $0$. Interprétation : l'entropie mesure l'incertitude, nulle quand l'espèce est connue, maximale quand toutes les espèces sont également probables.

Q13. Les poids d'une mesure étant non nuls, l'entropie se calcule directement sur la liste. Dans $H_i(\sigma )$, un terme avec $P^{\sigma }(C_i=v)=0$ est nul (et $\sigma [i:=v]$ n'y est pas défini) : on ne somme que sur les valeurs de probabilité non nulle, sans quoi reponse lèverait son exception.

let entropie (mu : 'x mesure) : float =
  List.fold_left (fun acc (_, p) -> acc -. p *. log p) 0. mu

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 else acc +. p *. entropie (reponse sigma i v))
    0. (List.init num.(i) (fun v -> v))

Ce que le correcteur attend : l'exclusion explicite des valeurs de probabilité nulle. Coût : pour chacune des $|V_i|$ valeurs, proba_etat et reponse coûtent $O(|\mathcal{S}||V_i|)$ (Q6, Q7) et entropie $O(|\mathcal{S}|)$ : $O(|\mathcal{S}||V_i{|}^2)$ en tout. Exécuté : sur l'exemple de la partie I, $H_0({\sigma }_0)\approx 0,3365$ et $H_1({\sigma }_0)\approx 0,4938$ ; sur l'exemple ci-dessous, les valeurs de Q16.