CCINP 2025 MPI Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2025, filière MPI, en 4 heures. Thème : Grammaires, bin-packing et couplages stables.

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

Ce que traite le sujet, partie par partie

• Partie I : grammaire non contextuelle. Dérivation à gauche, ambiguïté, élimination de la récursivité gauche et langage engendré.
• Partie II : problème de bin-packing. Appartenance à NP et NP-complétude par réduction depuis PARTITION, garantie de l'algorithme Premier Casier Décroissant, puis fonctions OCaml sur des enregistrements d'objets et de boîtes.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité
• Partie III : algorithmes de couplage. Algorithme de Gale-Shapley : terminaison, invariant, stabilité et optimalité, couplages Pareto-optimaux par circuits d'un graphe orienté, puis implémentation en C.
  À revoir : Algorithmes, discipline de programmation, validation et tests, Langage C : types, tableaux, pointeurs, allocation

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Algorithmes, discipline de programmation, validation et tests
• Langage C : types, tableaux, pointeurs, allocation

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.