X-ENS 2025 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 2025, filière MPI, en 4 heures. Thème : Couplages maximaux et parfaits : algorithme d'Edmonds, déterminant de Mahajan-Vinay et test probabiliste de Tutte.
Ce que traite le sujet, partie par partie
- Partie I : algorithme d'Edmonds. Couplages dans un graphe non orienté en OCaml : listes d'association, sommets couverts, chemins d'augmentation et augmentation d'un couplage, contraction d'une fleur, forêt alternée et assemblage de l'algorithme d'Edmonds de recherche d'un couplage maximal.
- Partie II : calculs de déterminants. Matrices linéarisées en C, déterminant exprimé par des suites de marches fermées dans le graphe d'adjacence, relation de récurrence par couches et implémentation par programmation dynamique de l'algorithme de Mahajan-Vinay sans division.
- Partie III : méthode algébrique et probabiliste pour les couplages parfaits. Matrice de Tutte instanciée par tirage aléatoire, lemme de Schwartz-Zippel et algorithme probabiliste testant l'existence d'un couplage parfait avec une probabilité d'erreur bornée.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Langage C : types, tableaux, pointeurs, allocation
- Espaces probabilisés
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.