Corrigé Centrale 2025 Option informatique MP — Partie II, II.1-II.3 (Q9 à Q18) : Optimums de Pareto en dimensions 1 et 2

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

Énoncé

Trajets proposés entre deux gares (figure 3) ; on veut minimiser les trois critères à la fois. Les optimums de Pareto sont ici (a), (c), (d) et (g).

trajet	durée (h)	correspondances	prix (euros)
(a)	6	0	60
(b)	5	1	50
(c)	4	2	110
(d)	5	1	40
(e)	5	1	90
(f)	5	2	100
(g)	4	1	120

Pour une relation d'ordre $⪯$ sur $E$ , on note $x ≺ y$ si $x ⪯ y$ et $x \neq = y$ . Pour $X \subseteq E$ , $min (X) = {x \in X ∣ ∄ y \in X, y ≺ x}$ est l'ensemble des éléments minimaux. Sur $E = A_{1} \times \dots \times A_{d}$ (chaque $A_{i}$ totalement ordonné) : l'ordre lexicographique $⊑$ (comparaison à la première composante qui diffère), total, et l'ordre produit $⪯$ ( $x ⪯ x^{'}$ ssi $x_{i} \leq x_{i}^{'}$ pour tout $i$ ), partiel. Un optimum de Pareto est un élément minimal pour l'ordre produit. Après Q10, $A_{i} = Z$ pour tout $i$ .

Q9. Montrer que (b) et (f) ne sont pas des optimums de Pareto, en donnant pour chacun un trajet strictement meilleur.
Q10. Si $X$ admet un minimum pour $⊑$ , montrer que ce minimum est un optimum de Pareto de $X$ .
Q11. (Dimension 1.) Écrire element_minimal : int list -> int (liste non vide).

Dimension 2 : un ensemble de couples est une liste sans doublons.


type tuple = int * int
let ex1 = [(4, 1); (5, 7); (3, 3); (1, 3); (2, 9); (1, 4); (2, 2)]

Q12. Éléments minimaux de l'ensemble ex1, sans justification.
Q13. Écrire inferieur : tuple -> tuple -> bool, qui teste $x ⪯ y$ .
Q14. Pour $X \subseteq Z^{2}$ à $n \geq 1$ éléments, encadrer $card (min (X))$ par des bornes atteintes.

On dispose de tri_lexico : tuple list -> tuple list, tri croissant pour $⊑$ en $O (n lo g n)$ , et de la fonction suivante, censée renvoyer les éléments minimaux de l'ensemble ens :


let elements_minimaux ens =
  let rec w u =
    match u with
    | x :: y :: z ->
      if inferieur x y then w (x :: z)
      else x :: w (y :: z)
    | v -> v
  in w (tri_lexico ens)

Une trace note -> f args au début d'un appel, <- valeur à son retour, en indentant les appels imbriqués.

Q15. Trace de w lors de l'appel elements_minimaux ex1 (on peut n'écrire que le début des listes).
Q16. Terminaison de elements_minimaux.
Q17. Complexité de elements_minimaux.
Q18. Correction de elements_minimaux.

Corrigé

Q9. On compare (durée, correspondances, prix) composante par composante.

(b) $= (5, 1, 50)$ et (d) $= (5, 1, 40)$ : $5 \leq 5$ , $1 \leq 1$ , $40 \leq 50$ et les triplets diffèrent, donc (d) $≺$ (b) : (b) n'est pas un optimum de Pareto.
(f) $= (5, 2, 100)$ et (d) $= (5, 1, 40)$ : $5 \leq 5$ , $1 \leq 2$ , $40 \leq 100$ , donc (d) $≺$ (f) ; (b) convient aussi, puisque $(5, 1, 50) ≺ (5, 2, 100)$ .

Q10. Soit $m$ le minimum de $X$ pour $⊑$ : $m \in X$ et $m ⊑ y$ pour tout $y \in X$ . Raisonnons par l'absurde et supposons $m \in / min (X)$ pour l'ordre produit : il existe $y \in X$ avec $y ≺ m$ , c'est-à-dire $y_{i} \leq_{i} m_{i}$ pour tout $i$ et $y \neq = m$ . Soit $k = min {i ∣ y_{i} \neq = m_{i}}$ ; alors $y_{k} \leq_{k} m_{k}$ et $y_{k} \neq = m_{k}$ , donc $y_{k} <_{k} m_{k}$ , ce qui signifie $y ⊑ m$ avec $y \neq = m$ . Or $y \in X$ , donc $m ⊑ y$ ; par antisymétrie de l'ordre lexicographique, $y = m$ : c'est absurde. Donc $m$ est un élément minimal de $X$ pour l'ordre produit, c'est-à-dire un optimum de Pareto sur $X$ .

Q11.


let rec element_minimal (l : int list) : int =
  match l with
  | [] -> failwith "element_minimal : liste vide"
  | [x] -> x
  | x :: r -> min x (element_minimal r)

Par récurrence sur la longueur : pour une liste à un élément, c'est lui ; sinon le minimum de x :: r est le plus petit de x et du minimum de r (non vide). Un appel par élément : $O (n)$ . (Testée sur [3; -2; 7; -2], qui donne $- 2$ , et sur un singleton.)

Q12. $min (ex1) = {(1, 3), (2, 2), (4, 1)}$ .

Q13.


let inferieur ((a, b) : tuple) ((c, d) : tuple) : bool = a <= c && b <= d

C'est la définition de l'ordre produit en dimension $2$ ; le résultat est false exactement quand $y ≺ x$ ou quand $x$ et $y$ sont incomparables.

Q14. On a $1 \leq card (min (X)) \leq n$ .

Majoration : $min (X) \subseteq X$ .
Minoration : $X$ est fini et non vide, donc il admet un minimum pour l'ordre lexicographique, qui est total ; d'après Q10 c'est un élément minimal pour l'ordre produit, donc $min (X) \neq = \emptyset$ .
La borne $1$ est atteinte pour la chaîne $X = {(i, i) ∣ 0 \leq i < n}$ : $(0, 0) ⪯ (i, i)$ pour tout $i$ , donc $min (X) = {(0, 0)}$ .
La borne $n$ est atteinte pour $X = {(i, - i) ∣ 0 \leq i < n}$ , formé de $n$ couples distincts : pour $i < j$ , la première composante de $(i, - i)$ est plus petite et la seconde plus grande que celles de $(j, - j)$ ; ces éléments sont deux à deux incomparables, donc tous minimaux.

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 →