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)

   Deux tables : commune(Nom, INSEE) et conseiller(Monde, INSEE, Département). Le monde 0 est le monde réel, les mondes 1 à 20 ceux des conseillers.

   • Q1 — les conseillers proposant de créer le Gévaudan.
   • Q2 — ceux rattachant le Mont-Saint-Michel à l'Ille-et-Vilaine.
   • Q3, Q4 — les communes qui peuvent faire partie de la Sarthe, puis celles qui le peuvent sans en faire partie réellement.
   • Q5 — les rattachements obligatoires qui ne sont pas réalisés.
   View solution

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

   • Q6 — appartient, sans utiliser String.contains.
   • Q7 — sous_chaine, sans utiliser String.sub, avec levée d'exception.
   • Q8 — detecte_lexeme, qui fait tourner l'automate donné.
   • Q9 — analyse_lexicale, qui produit la liste des lexèmes.
   View solution

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

   G et H sont deux grammaires non contextuelles pour les formules déontiques, la seconde imposant des parenthèses autour de chaque conjonction.

   • Q10 — les mots m_1 et m_2 dérivent-ils de G ? de H ?
   • Q11 — engendrent-elles le même langage ?
   • Q12 — sont-elles ambiguës ?
   View solution

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

   Trois fonctions mutuellement récursives, une par symbole non terminal de H.

   • Q13, Q14 — compléter les deux blocs manquants.
   • Q15 — la fonction analyse_syntaxique.
   View solution

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

   Les formules sont des arbres alloués sur le tas, de type formule.

   • Q16 — cree_formule.
   • Q17 — compter_peut, qui compte les occurrences de ◇.
   • Q18 — free_formule, qui libère toutes les sous-formules.
   • Q19 — retirer_implications, qui produit une copie sans implications.
   View solution

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

   Un univers est un graphe de mondes ; □φ se lit « φ dans tous les mondes idéaux », ◇φ « dans au moins un ».

   • Q20 — satisfaction, pour une formule purement propositionnelle.
   • Q21, Q22 — l'univers E de l'énoncé satisfait-il deux formules données ?
   • Q23 à Q25 — satisfiabilité de θ_1, θ_2 et de leurs négations, puis la conséquence logique.
   View solution

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

   Dans une formule réduite, les négations ne portent que sur des variables et il n'y a plus d'implication.

   • Q26 — les règles de De Morgan.
   • Q27 — toute formule déontique équivaut à une formule réduite.
   • Q28, Q29 — les fonctions est_reduite et satisfaction2.
   View solution

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

   On déplie un univers en un arbre de profondeur N.

   • Q30, Q31 — la taille de l'arbre, puis sa construction effective.
   • Q32, Q33 — la satisfaction se transporte à l'arbre.
   • Q34 — la satisfiabilité d'une formule déontique est décidable.
   View solution

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

   Un univers est total lorsque tout monde est idéal pour tout monde.

   • Q35 — DSAT est NP-complet si et seulement s'il est dans NP.
   • Q36 — une formule satisfiable dans aucun univers total.
   • Q37, Q38 — vérification rapide, et existence d'un témoignage de taille polynomiale.
   • Q39 — TOTAL-DSAT est NP-complet.
   View solution

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

    Le système D étend la déduction naturelle classique par trois règles portant sur □.

    • Q40 — un arbre de preuve pour ⊢ A → (B → (A ∧ B)).
    • Q41 — le système interdit les obligations contradictoires.
    • Q42 — l'équivalence □(A ∧ B) ↔ (□A ∧ □B).
    View solution