Centrale 2025 — Informatique MPI : sujet et corrigé

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

• Partie A, I (Q1 à Q6) — Rush Hour en C : états, plateau, listes de déplacements
• Partie A, II (Q7 à Q11) — File circulaire et complexité amortie par la méthode du potentiel
• Partie A, III (Q12 à Q16) — Table de hachage à adressage ouvert
• Partie A, IV (Q17 à Q18) — Solution optimale par parcours en largeur, gestion de la mémoire
• Partie B, I (pavages) (Q19 à Q21) — Couvrir un terrain de voitures : parité et coloration
• Partie B, I (couplages) (Q22 à Q29) — Couplage maximum : chemins augmentants, Hopcroft-Karp (OCaml)
• Partie B, II (classe NP) (Q30 à Q32) — Le problème 3CASSE est dans NP
• Partie B, II (réduction) (Q33 à Q38) — Réduction de Planar 3SAT à 3CASSE : gadgets et NP-complétude