Mines-Ponts 2026 MP Informatique option MP : sujet en PDF

Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2026, filière MP, en 3 heures. Thème : Automates sur des vecteurs binaires et arithmétique de Presburger.

Lire le sujet 10 pages · sujet sans corrigé, reproduit sans retouche−+Télécharger le PDF (0,5 Mo)

Ce que traite le sujet, partie par partie

• Section 1 : implémentation de quelques fonctions utiles. Calcul récursif de 2^n en O(log n) sans décalage de bits et preuve de la complexité, puis bijection entre les entiers de 0 à 2^n - 1 et les vecteurs de n bits, et sa programmation.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Récursivité, Complexité des algorithmes itératifs et récursifs, Architecture de l'ordinateur et représentation des nombres
• Section 2 : automates finis sur Σ_n. Automates qui lisent des entiers écrits en binaire, bit de poids faible en tête : langage lié à la plus grande puissance de 2 qui divise un entier, automate pour une égalité de valeurs, test de déterminisme, déterminisation, complémentaire et automate produit pour l'intersection.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Architecture de l'ordinateur et représentation des nombres, Complexité des algorithmes itératifs et récursifs
• Sections 3 et 4 : opérations arithmétiques et arithmétique de Presburger. Automate à deux états qui reconnaît l'addition binaire et sa preuve, non-reconnaissabilité du langage de la multiplication, puis formules de Presburger, variables libres et liées, mise sous forme simple et preuves en déduction naturelle avec des règles sur l'égalité.
  À revoir : Logique, ensembles et applications, Architecture de l'ordinateur et représentation des nombres
• Section 5 : retour sur les automates. Zéros non significatifs, projection existentielle sur une composante, construction d'un automate qui reconnaît les assignations satisfaisant une formule sous forme simple, exemple déroulé à la main, preuve de correction et décision de la vérité d'une formule close.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Récursivité, Spécifier, tester, prouver : terminaison et correction

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Récursivité
• Complexité des algorithmes itératifs et récursifs
• Architecture de l'ordinateur et représentation des nombres
• Logique, ensembles et applications
• Spécifier, tester, prouver : terminaison et correction

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.