X-ENS 2024 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 2024, filière MPI, en 4 heures. Thème : Égalités et différences : satisfiabilité de conjonctions de contraintes, de la logique propositionnelle à la clôture par congruence.
Ce que traite le sujet, partie par partie
- Partie I : équivalences de littéraux. Contraintes d'équivalence entre littéraux, réduction à 2-SAT, graphe associé à la formule et composantes connexes en OCaml, caractérisation des formules contradictoires et construction d'une valuation en O(p n).
- Partie II : équivalences avec une conjonction de deux littéraux. Réduction à 3-SAT, preuve en déduction naturelle, simplification par valuation partielle et algorithme de retour sur trace en OCaml : terminaison, correction par cas et complexité exponentielle.
- Partie III : égalités et différences entre entiers. Formules d'égalités et de différences entre variables entières codées par des listes chaînées en C, structure unir et trouver, test de satisfiabilité, construction d'une valuation et lien avec la 2-coloration d'un graphe.
- Partie IV : égalités et différences d'expressions. Termes représentés par des arbres binaires puis partagés dans un graphe orienté acyclique, test de différence et de congruence, fusion récursive de classes (clôture par congruence) et nombre maximal d'appels récursifs.
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.