Prepa HelpMines-Ponts 2026 MPI Informatique 1 : sujet en PDF
Sujet de l'épreuve de Informatique 1 du Concours commun Mines-Ponts, France, session 2026, filière MPI, en 3 heures. Thème : Automates sur des vecteurs binaires et décidabilité de l'arithmétique de Presburger en OCaml.
Ce que traite le sujet, partie par partie
- Section 1 : implémentation de quelques fonctions utiles. Puissance de 2 récursive en temps logarithmique, bijection entre entiers et vecteurs de bits et sa programmation.
- Section 2 : automates finis sur Sigma_n. Mots de vecteurs binaires lus comme entiers écrits poids faible en tête, preuve du langage reconnu par un automate, automates déterministes complets, déterminisation, complémentaire et produit.
- Section 3 : opérations arithmétiques. Automate à deux états de l'addition binaire et sa preuve, non-reconnaissabilité du langage de la multiplication.
- Section 4 : arithmétique de Presburger. Termes et formules, variables libres et liées, divisibilité par 2 et entiers exprimés sans constantes, forme simple et preuves en déduction naturelle avec règles d'égalité.
- Section 5 : retour sur les automates. Réduction de SAT-CNF, projection existentielle d'un langage, construction inductive d'un automate pour une formule, preuve de correction et décision de la vérité d'une formule close.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Architecture de l'ordinateur et représentation des nombres
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.