X-ENS 2026 MP Informatique B : sujet en PDF
Sujet de l'épreuve de Informatique B du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2026, filière MP, en 2 heures. Thème : Cycles et unification dans un graphe orienté acyclique, avec représentation relationnelle.
Ce que traite le sujet, partie par partie
- Partie I. Détection de cycles. Parcours en profondeur avec époques et dates de sortie, invariants sur les arcs, test d'accessibilité et ajout d'un arc de liaison sans créer de cycle, avec preuves de préservation des invariants.
- Partie II. Unification. Sommets libres, liés et internes, forme normale récursive, terminaison et coût exponentiel, calcul linéaire par mémorisation, nombre de chemins vers les sommets libres et algorithme d'unification à compléter.
- Partie III. Représentation relationnelle. Graphe stocké dans deux tables liées par des clés étrangères, requêtes SQL pour vérifier les invariants et trouver deux sommets distincts de même forme normale.
Chapitres à revoir avant de traiter ce sujet
- Spécifier, tester, prouver : terminaison et correction
- Récursivité
- Tuples, dictionnaires et ensembles
- Complexité des algorithmes itératifs et récursifs
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.