Corrigé Centrale 2025 Option informatique MP — Partie II, II.4 (Q19 à Q21) : Éléments minimaux pour un ordre partiel quelconque

Sujet officiel du concours Centrale, session 2025, épreuve Option informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

On ne dispose plus que d'un type abstrait element et d'une fonction inferieur : element -> element -> bool qui teste $x ⪯ y$ pour un ordre partiel $⪯$ . Pour $X \subseteq E$ , la largeur de $X$ est le cardinal maximal d'une partie de $X$ formée d'éléments deux à deux incomparables :

$largeur (X) = max {card (Y) ∣ Y \subseteq X, \forall (x, y) \in Y^{2}, x \neq = y \Rightarrow x \neq ⪯ y \land y \neq ⪯ x} .$

Q19. Écrire existe_plus_petit : element -> element list -> bool : existe_plus_petit u liste vaut true ssi un élément de liste est inférieur ou égal à u.
Q20. Écrire ajoute_plus_petit : element -> element list -> element list, qui ajoute u à la liste après en avoir supprimé tous les éléments supérieurs ou égaux à u.
Q21. En déduire elements_minimaux : element list -> element list, qui renvoie les éléments minimaux d'un ensemble $X$ donné par une liste sans doublons, en au plus $O (nk)$ appels à inferieur, où $n = card (X)$ et $k = largeur (X)$ ; justifier brièvement.

Corrigé

Q19.


let existe_plus_petit (u : element) (liste : element list) : bool =
  List.exists (fun v -> inferieur v u) liste

List.exists évalue inferieur v u pour les éléments v successifs et renvoie true dès qu'un test réussit : c'est exactement « il existe $v$ dans la liste avec $v ⪯ u$ ». Au plus $∣ liste ∣$ appels à inferieur.

Q20.


let ajoute_plus_petit (u : element) (liste : element list) : element list =
  u :: List.filter (fun v -> not (inferieur u v)) liste

On ne garde de liste que les $v$ tels que $u \neq ⪯ v$ , c'est-à-dire qu'on supprime ceux qui sont supérieurs ou égaux à $u$ , puis on ajoute $u$ en tête. Exactement $∣ liste ∣$ appels à inferieur.

Ce que le correcteur attend : supprimer les éléments supérieurs ou égaux à $u$ , et non garder ceux qui lui sont inférieurs : pour un ordre partiel, « ne pas être supérieur ou égal à $u$ » ne veut pas dire « être inférieur à $u$ » (un élément incomparable à $u$ doit rester).

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 →