Corrigé CCINP 2025 Informatique MPI — Partie II (Q6 à Q16) : Bin-packing : NP-complétude, 3/2-approximation, Premier Casier en OCaml

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

Énoncé

Un rangement de $n$ objets dans $k$ boîtes est une fonction $R : [[1, n]] \to [[1, k]]$ ; la boîte $j$ contient $B_{j} = R^{- 1} (j)$ . Pour des tailles $a = (a_{1}, \dots, a_{n}) \in (Q \cap] 0, 1])^{n}$ , il est valide si $\sum_{i \in B_{j}} a_{i} ⩽ 1$ pour tout $j$ . bin-packing : étant donnés $n, k$ et $a$ , existe-t-il un rangement valide ? partition : étant donnés des entiers $c_{1}, \dots, c_{n}$ , existe-t-il $S \subseteq [[1, n]]$ avec $\sum_{i \in S} c_{i} = \sum_{i \in / S} c_{i}$ ? (admis NP-complet).

Q6. bin-packing est dans NP.
Q7. Il est NP-complet (réduction depuis partition).

min-bin-packing cherche le plus petit $k$ admettant un rangement valide. Algorithme 1 (Premier Casier) : objets traités dans l'ordre $1, \dots, n$ , chacun dans la première boîte de la liste $L$ qui peut le recevoir, sinon dans une boîte nouvelle ajoutée en fin ; $k = ∣ L ∣$ . Algorithme 2 (Premier Casier Décroissant) : Premier Casier sur les objets triés par tailles décroissantes. On note $k$ le nombre de boîtes de l'algorithme 2, $k^{*}$ l'optimum, $k_{1} = ⌈ 2 k /3 ⌉$ .

Q8. Si $B_{k_{1}}$ contient un objet de taille $> \frac{1}{2}$ , alors $k^{*} ⩾ k_{1} ⩾ \frac{2}{3} k$ .
Q9. Sinon, $B_{k_{1}}, \dots, B_{k}$ contiennent au moins $2 (k - k_{1}) + 1$ objets, dont aucun ne rentre dans $B_{1}, \dots, B_{k_{1} - 1}$ .
Q10. Justifier $\sum_{i = 1}^{n} a_{i} > min (k_{1} - 1, 2 (k - k_{1}) + 1)$ , puis, en admettant $\frac{2}{3} k + \frac{2}{3} ⩾ ⌈ 2 k /3 ⌉$ , en déduire $k^{*} ⩾ ⌈ \frac{2}{3} k ⌉ ⩾ \frac{2}{3} k$ .

Types du sujet. Coquilles rectifiées : ses commentaires disent « de la boîte » pour les champs de objet et « tailles des objets » pour objets (une objet list) ; les types sont inchangés :


type objet = {
  id : int;         (* identifiant de l'objet *)
  taille : float;   (* taille de l'objet *)
}

type boite = {
  charge : float;        (* somme des tailles des objets de la boîte *)
  objets : objet list;   (* objets contenus dans la boîte *)
}

Q11. La constante boite_vide : boite.
Q12. ajoute_boite : objet -> boite -> boite ajoute un objet à une boîte.
Q13. trouve_boite : boite list -> objet -> int, récursive : indice (depuis $0$ ) de la première boîte pouvant contenir l'objet, sinon longueur de la liste.
Q14. transforme : 'a -> ('a -> 'a) -> int -> 'a list -> 'a list, récursive : remplace l'élément x d'indice i par f x, ou ajoute f d en fin si i dépasse la taille.
Q15. premier_casier : objet list -> boite list (algorithme 1, liste de boîtes rendue).
Q16. premier_casier_decroissant : objet list -> boite list (algorithme 2), avec List.sort et compare.

Corrigé

Q6. Rappel du cours : un problème de décision est dans NP si toute instance positive admet un certificat de taille polynomiale en celle de l'instance, vérifiable en temps polynomial. L'instance est $(n, k, a)$ , de taille au moins $n$ (les $n$ rationnels sont écrits) plus $lo g_{2} k$ bits pour $k$ , plus la taille des numérateurs et dénominateurs des $a_{i}$ .

Certificat : le rangement $R$ , donné par la suite $(R (1), \dots, R (n))$ , soit $O (n lo g k)$ bits : polynomial en la taille de l'instance.
Vérification : on teste $1 ⩽ R (i) ⩽ k$ pour chaque $i$ ; puis, pour chaque $i$ , on calcule la charge $\sum_{i^{'} : R (i^{'}) = R (i)} a_{i^{'}}$ de la boîte de $i$ et on la compare à $1$ . Cela fait $O (n^{2})$ comparaisons et additions de rationnels ; une somme de rationnels a une taille au plus la somme des tailles des termes (dénominateur commun produit des dénominateurs), donc chaque opération est polynomiale. On ne crée pas de tableau de $k$ cases : $k$ peut être exponentiel en sa taille $lo g_{2} k$ , seules les boîtes non vides (au plus $n$ ) sont examinées.

Le vérificateur accepte si et seulement si $R$ est un rangement valide : une instance est positive si et seulement si elle possède un certificat accepté. Donc bin-packing $\in$ NP. Ce que le correcteur attend : la taille polynomiale du certificat, que le jury dit rarement précisée.

Q7. On montre partition $⩽_{p}$ bin-packing. Les $c_{i}$ sont des entiers naturels (cadre usuel de partition) ; les $c_{i}$ nuls ne changent pas la réponse (on les place dans $S$ ou non indifféremment), on les retire. Soit $C = \sum_{i} c_{i}$ . Transformation $τ$ :

si $C = 0$ (plus aucun entier), la réponse est oui ( $S = \emptyset$ ) : $τ$ rend l'instance positive fixe $n = 1$ , $k = 1$ , $a = (1)$ ;
si $C$ est impair, ou si un $c_{i}$ vérifie $c_{i} > C /2$ , la réponse est non (la somme $C /2$ n'est pas entière, ou la partie contenant $i$ dépasse $C /2$ ) : $τ$ rend l'instance négative fixe $n = 2$ , $k = 1$ , $a = (1, 1)$ ;
sinon, $τ$ rend $n$ objets de tailles $a_{i} = \frac{2 c _{i}}{C}$ et $k = 2$ boîtes. Comme $0 < c_{i} ⩽ C /2$ , on a bien $a_{i} \in Q \cap] 0, 1]$ , et $\sum_{i} a_{i} = 2$ .

Coût. Calculer $C$ , tester la parité et les $c_{i} > C /2$ , écrire les fractions $2 c_{i} / C$ : $O (n)$ opérations sur des entiers de taille au plus celle de l'instance, donc temps polynomial, et l'instance produite a une taille polynomiale.

Équivalence (dans le troisième cas, les deux premiers étant réglés ci-dessus).

Si $S$ convient, $\sum_{i \in S} c_{i} = \sum_{i \in / S} c_{i} = C /2$ . Posons $R (i) = 1$ si $i \in S$ , $2$ sinon : les deux boîtes ont pour charge $\frac{2}{C} \cdot \frac{C}{2} = 1 ⩽ 1$ , le rangement est valide.
Si $R$ est un rangement valide dans $2$ boîtes, de charges $ℓ_{1}, ℓ_{2} ⩽ 1$ , alors $ℓ_{1} + ℓ_{2} = \sum_{i} a_{i} = 2$ , donc $ℓ_{1} = ℓ_{2} = 1$ . Avec $S = B_{1}$ , $\sum_{i \in S} c_{i} = \frac{C}{2} ℓ_{1} = \frac{C}{2}$ , et le complémentaire a la même somme : $S$ convient.

$τ$ est donc une réduction polynomiale. partition étant NP-complet, tout problème de NP se réduit à partition, donc (composition de réductions polynomiales) à bin-packing, qui est NP-difficile ; avec Q6, bin-packing est NP-complet. (L'équivalence a été vérifiée par force brute sur $3000$ instances aléatoires de partition d'au plus $7$ entiers.)

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 →