Corrigé X-ENS 2025 Informatique A MP — Partie I (Q1 à Q7) : Description probabiliste des plantes : états, Bayes, mesures en listes

Une mesure sur un ensemble fini $X$ est une fonction $X\to {\mathbb{R}}^{+}$ ; de masse $1$, c'est une distribution. On note $D(X)$ l'ensemble des distributions et ${\delta }_x$ la dirac en $x$. Il y a $N$ caractères $i\in \{0,\dots ,N-1\}$, le caractère $i$ prenant ses valeurs dans un ensemble fini $V_i$. Une espèce est un $N$-uplet $s=(s_0,\dots ,s_{N-1})$ avec $s_i\in D(V_i)$ ; $\mathcal{S}$ est l'ensemble fini des espèces. Exemple, avec $V_0=\{4,5\}$ (pétales) et $V_1=\{\mathsf{bleu},\mathsf{blanc}\}$ :

$$\mathsf{myosotis}=({\delta }_5,0,8\cdot {\delta }_{\mathsf{bleu}}+0,2\cdot {\delta }_{\mathsf{blanc}}),\mathsf{lin}=({\delta }_5,{\delta }_{\mathsf{bleu}}),\mathsf{gaillet}=({\delta }_4,{\delta }_{\mathsf{blanc}}).$$

Sur $\Omega =\{(s,v_0,\dots ,v_{N-1})\mid s\in \mathcal{S},v_i\in V_i\}$ (tribu discrète), un état $\sigma \in D(\mathcal{S})$ induit la loi définie par

$$P^{\sigma }(\{(s,v_0,\dots ,v_{N-1})\})=\sigma (s)\prod _{0\le i\le N-1}{s}_i(v_i);$$

$S$ et $C_i$ sont les variables qui renvoient $s$ et $v_i$. L'état mis à jour $\sigma [i:=v]$ est la distribution $s\mapsto P^{\sigma }(S=s\mid C_i=v)$. En OCaml, $V_i=\{0,\dots ,\text{num.(i)}-1\}$ et une mesure $\mu$ est la liste, sans doublons et dans un ordre quelconque, des couples $(x,\mu (x))$ tels que $\mu (x)>0$ :

type caractere = int
type valeur = int
val num : int array          (* num.(i) = k_i, i.e., V_i = {0,1,...,num.(i)-1} *)
let caracteres : caractere list = List.init (Array.length num) (fun i -> i)
let num = [|2; 2|]
let nb_petales : caractere = 0
let quatre, cinq = 0, 1
let couleur_petales : caractere = 1
let bleu, blanc = 0, 1
type 'x mesure = ('x * float) list
let dirac v = [(v, 1.)]
type espece = { name: string; mesures: valeur mesure array }
type etat = espece mesure
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)]

Q1. Pour ${\sigma }_0=\{\mathsf{gaillet}:50\%,\mathsf{myosotis}:30\%,\mathsf{lin}:20\%\}$, donner $P^{{\sigma }_0}(C_1=\mathsf{blanc})$ et chaque $P^{{\sigma }_0}(S=s\mid C_1=\mathsf{blanc})$, sans justification.
Q2. Exprimer, en justifiant, $P^{\sigma }(S=s)$, $P^{\sigma }(C_i=v)$ et $P^{\sigma }(C_i=v\mid S=s)$.
Q3. Exprimer $P^{\sigma }(S=s\mid C_i=v)$ ; quand est-elle définie ?
Q4. Pour $i\ne j$, montrer que $P^{\sigma }(S=s\mid C_i=v,C_j=v^{\prime })=P^{\sigma [i:=v]}(S=s\mid C_j=v^{\prime })$.
Q5. Écrire proba_de : 'x -> 'x mesure -> float (poids d'un élément), somme_ponderee : 'x mesure -> ('x -> float) -> float (la somme ${\sum }_x\mu (x)f(x)$) et repondere : 'x mesure -> ('x -> float) -> 'x mesure (nouveau poids $\mu (x)f(x)$).
Q6. Écrire proba_espece : espece -> caractere -> valeur -> float, qui renvoie $P^{{\delta }_s}(C_i=v)$, et proba_etat : etat -> caractere -> valeur -> float, qui renvoie $P^{\sigma }(C_i=v)$.
Q7. Écrire reponse : etat -> caractere -> valeur -> etat, qui renvoie $\sigma [i:=v]$ s'il est défini et lève une exception sinon.