X-ENS 2026 MPI Informatique C : sujet en PDF
Sujet de l'épreuve de Informatique C du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2026, filière MPI, en 4 heures. Thème : Vérification de systèmes concurrents : propriétés de sûreté, parcours en profondeur imbriqués et réduction des entrelacements.
Ce que traite le sujet, partie par partie
- Partie I : systèmes de transitions. Exécutions infinies d'un système de transitions, propriétés de sûreté et préfixes interdits, propriétés régulières, test d'accessibilité en OCaml et réduction de la vérification d'une propriété de sûreté à un problème d'inaccessibilité dans un produit avec un automate.
- Partie II : ultime invariance. Caractérisation par un état accessible hors de l'invariant et situé sur un cycle, parcours en profondeur externe et internes partageant leurs marques, ordre postfixe et preuve de correction de la vérification.
- Partie III : programmation multi-threads en C. Rappels sur pthread_create et pthread_join, analyse des affichages possibles d'un programme dont deux fils d'exécution écrivent dans une même variable globale, correction de cet accès concurrent, puis fonction main qui alloue un tableau sur le tas, lance les calculs en parallèle et libère la mémoire.
- Partie IV : systèmes de transitions concurrents. Modélisation des entrelacements d'un programme à deux fils, indépendance des actions, ensembles persistants, ordre lexicographique induit et méthode de mise en veille qui ne garde que les minima lexicographiques.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Spécifier, tester, prouver : terminaison et correction
- Récursivité
- 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.