Centrale 2025 MPI Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Centrale-Supélec, France, session 2025, filière MPI, en 4 heures. Thème : Rush Hour (en C) et remplissage d'une casse automobile (en OCaml).

Lire le sujet 14 pages · sujet sans corrigé, reproduit sans retouche−+Télécharger le PDF (0,5 Mo)

Ce que traite le sujet, partie par partie

• Partie A : Rush Hour (langage C). Représentation des états et des déplacements, file dans un tableau redimensionnable et coût amorti, table de hachage des états, puis recherche d'une solution optimale par parcours en largeur.
  À revoir : Langage C : types, tableaux, pointeurs, allocation
• Partie B.I : remplir une casse avec le maximum de voitures (OCaml). Arguments de pavage, couplage maximum dans un graphe biparti par chemins augmentants et implémentation en OCaml.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité
• Partie B.II : remplir une casse avec le maximum de camions. Problème de décision 3CASSE : appartenance à NP puis NP-complétude par réduction à l'aide de gadgets.
  À revoir : Logique, ensembles et applications

Chapitres à revoir avant de traiter ce sujet

• Langage C : types, tableaux, pointeurs, allocation
• Langage OCaml : expressions, types, filtrage, récursivité
• Logique, ensembles et applications

Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.