Centrale-Supélec 2026 — Informatique (MPI)

Independent solutions, written by Pulsars. Neither official nor affiliated with Concours Centrale-Supélec.

1. Exercise 1 — Partie A — Base de données (Q1 à Q5)

   Two tables: commune(Nom, INSEE) and conseiller(Monde, INSEE, Département). World 0 is the real world, worlds 1 to 20 are those of the advisers.

   • Q1 — the advisers proposing to create the Gévaudan.
   • Q2 — those attaching Mont-Saint-Michel to Ille-et-Vilaine.
   • Q3, Q4 — the communes that may be part of the Sarthe, then those that may be without actually being part of it.
   • Q5 — the mandatory attachments that are not in effect.
   View solution

2. Exercise 2 — Partie B · I — Analyse lexicale en OCaml (Q6 à Q9)

   • Q6 — appartient, without using String.contains.
   • Q7 — sous_chaine, without using String.sub, raising an exception.
   • Q8 — detecte_lexeme, which runs the given automaton.
   • Q9 — analyse_lexicale, which produces the list of lexemes.
   View solution

3. Exercise 3 — Partie B · II — Deux grammaires (Q10 à Q12)

   G and H are two context-free grammars for deontic formulas, the second requiring parentheses around each conjunction.

   • Q10 — are the words m_1 and m_2 derived from G? from H?
   • Q11 — do they generate the same language?
   • Q12 — are they ambiguous?
   View solution

4. Exercise 4 — Partie B · III — Analyse syntaxique par descente récursive (Q13 à Q15)

   Three mutually recursive functions, one per non-terminal symbol of H.

   • Q13, Q14 — complete the two missing blocks.
   • Q15 — the function analyse_syntaxique.
   View solution

5. Exercise 5 — Partie C · I — Manipuler les formules en C (Q16 à Q19)

   Formulas are trees allocated on the heap, of type formule.

   • Q16 — cree_formule.
   • Q17 — compter_peut, which counts the occurrences of ◇.
   • Q18 — free_formule, which frees all the subformulas.
   • Q19 — retirer_implications, which produces a copy without implications.
   View solution

6. Exercise 6 — Partie C · II — Univers de Kripke et modèles (Q20 à Q25)

   A universe is a graph of worlds; □φ reads "φ in all ideal worlds", ◇φ "in at least one".

   • Q20 — satisfaction, for a purely propositional formula.
   • Q21, Q22 — does the universe E of the statement satisfy two given formulas?
   • Q23 to Q25 — satisfiability of θ_1, θ_2 and of their negations, then logical consequence.
   View solution

7. Exercise 7 — Partie C · III — Formules réduites (Q26 à Q29)

   In a reduced formula, negations apply only to variables and there are no more implications.

   • Q26 — De Morgan's laws.
   • Q27 — every deontic formula is equivalent to a reduced formula.
   • Q28, Q29 — the functions est_reduite and satisfaction2.
   View solution

8. Exercise 8 — Partie C · IV — Décidabilité par dépliage arborescent (Q30 à Q34)

   We unfold a universe into a tree of depth N.

   • Q30, Q31 — the size of the tree, then its actual construction.
   • Q32, Q33 — satisfaction carries over to the tree.
   • Q34 — satisfiability of a deontic formula is decidable.
   View solution

9. Exercise 9 — Partie C · V — NP-complétude (Q35 à Q39)

   A universe is total when every world is ideal for every world.

   • Q35 — DSAT is NP-complete if and only if it is in NP.
   • Q36 — a formula that is satisfiable in no total universe.
   • Q37, Q38 — fast verification, and existence of a witness of polynomial size.
   • Q39 — TOTAL-DSAT is NP-complete.
   View solution

10. Exercise 10 — Partie D — Déduction naturelle déontique (Q40 à Q42)

    The system D extends classical natural deduction with three rules involving □.

    • Q40 — a proof tree for ⊢ A → (B → (A ∧ B)).
    • Q41 — the system rules out contradictory obligations.
    • Q42 — the equivalence □(A ∧ B) ↔ (□A ∧ □B).
    View solution