CCINP 2025 — Informatique MPI : sujet et corrigé

5 parties corrigées, avec un corrigé rédigé · filière MPI.

• Partie I (Q1 à Q5) — Grammaire non contextuelle : ambiguïté, récursivité gauche, langage
• Partie II (Q6 à Q16) — Bin-packing : NP-complétude, 3/2-approximation, Premier Casier en OCaml
• Partie III (III.1) (Q17 à Q25) — Couplages stables : l'algorithme de Gale-Shapley et son optimalité pour V
• Partie III (III.2) (Q26 à Q31) — Couplages Pareto-optimaux par circuits du graphe des premiers choix
• Partie III (III.3) (Q32 à Q38) — Gale-Shapley et graphe des premiers choix en C