Corrigé Centrale 2025 Informatique MPI — Partie B, II (classe NP) (Q30 à Q32) : Le problème 3CASSE est dans NP

Sujet officiel du concours Centrale, session 2025, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un camion occupe trois cases alignées. 3casse : étant donnés un terrain $t$ et un entier $n$ , peut-on placer au moins $n$ camions sur $t$ ?
Q30. Définir : problème de décision de la classe NP ; problème NP-difficile ; problème NP-complet.


type terrain = bool array array
type direction = Horizontal | Vertical
type camion = { i : int; j : int; d : direction }

t.(i).(j) vaut true si et seulement si la case $(i, j)$ appartient au terrain ; un camion est repéré, comme dans la partie A, par sa case la plus en haut à gauche et sa direction.
Q31. est_valide (t : terrain) (n : int) (lst : camion list) : bool : true si la liste contient $n$ camions que l'on peut placer sur $t$ comme indiqué, false sinon.
Q32. En déduire que 3casse est dans NP.

Corrigé

Q30. On reprend les définitions du cours (chapitre 31). Un problème de décision associe à chaque instance la réponse « oui » ou « non ».

Un problème de décision $Π$ est dans la classe NP s'il existe un polynôme $P$ et un algorithme $V$ , le vérificateur, qui s'exécute en temps polynomial en la taille de ses entrées, tels que, pour toute instance $x$ : $x$ est positive si et seulement s'il existe un certificat $y$ de taille $∣ y ∣ ⩽ P (∣ x ∣)$ avec $V (x, y) = vrai$ .
$Π$ est NP-difficile si tout problème $Π^{'}$ de NP se réduit polynomialement à $Π$ : il existe $f$ calculable en temps polynomial telle que $x$ est une instance positive de $Π^{'}$ si et seulement si $f (x)$ est une instance positive de $Π$ (on note $Π^{'} ⩽_{p} Π$ ).
$Π$ est NP-complet s'il est à la fois dans NP et NP-difficile.

La relation $⩽_{p}$ est transitive ; pour montrer qu'un problème est NP-difficile, il suffit donc d'y réduire un problème NP-difficile connu (c'est ce que fera Q38, à partir de planar 3sat).

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 →