Mines Informatique 1 MPI 2026Sujet et rapport du jury

ÉCOLE NATIONALE DES PONTS et CHAUSSÉES, ISAE-SUPAERO, ENSTA, TÉLÉCOM PARIS, MINES PARIS - PSL, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.

Préliminaires

Travail attendu

Introduction

• - Σ est un alphabet fini;
• - Q est un ensemble fini d'états;
• - q_0 est un état de Q appelé état initial;
• - F est un sous-ensemble de Q appelé ensemble des états finaux ;
• - δ est une fonction de Q × Σ dans P(Q) appelée fonction de transition.

1. Implémentation de quelques fonctions utiles

• □1 - Écrire une fonction pow2 : int -> int qui prend en entrée un entier n et renvoie 2^n. On attend une fonction récursive de complexité temporelle en O(log(n)).

• □2 - Exhiber une bijection entre [ [0, 2^n − 1] ] et Σ_n.
  À présent, on souhaite implémenter notre bijection.
• □3 - Écrire une fonction decompose : int -> int -> int array qui prend en entrée x et n tels que x ∈ [ [0, 2^n − 1] ] et qui renvoie l'élément de Σ_n associée par la bijection précédemment définie. On vérifiera que l'entrée est valide à l'aide d'une assertion.

2. Automates finis sur ∑_n

Figure 1 - Représentation de l'automate A_1

Figure 2 - Représentation de l'automate A_2

type automate = {
    k : int ;
    n : int ;
    finaux : bool array ;
    delta : int -> int array -> int list ;
}

• a soit un automate à k états;
• etats soit un tableau d'entiers de taille k à valeur dans {0,1};
• lettre soit une lettre représentée par un tableau d'entiers.

3. Opérations arithmétiques

• □14 - Donner, dans un premier temps sans justifier, un automate à deux états reconnaissant le langage L_+ = {m ∈ Σ_3^∗|v_1(m) + v_2(m) = v_3(m)}.
• □15 - Démontrer que l'automate proposé dans la question précédente reconnaît bien L_+.
  ◻16 - Le langage L_× = {m ∈ Σ_3^∗|v_1(m) × v_2(m) = v_3(m)} est-il reconnaissable? Justifier.

4. Arithmétique de Presburger

• -pour tout x ∈ V, x est un terme;
• -pour deux termes t_1 et t_2, t_1 + t_2 est un terme.

• -pour t_1 et t_2 deux termes, t_1 = t_2 est une formule;
• -pour φ une formule, ¬φ est une formule;
• -pour φ_1 et φ_2 deux formules φ_1 → φ_2, φ_1 ∧ φ_2 et φ_1 ∨ φ_2 sont des formules;
• -pour φ une formule et x une variable qui n'apparaît pas juste après un quantificateur dans φ, alors ∃x.φ et ∀x.φ sont des formules.

• (i)Elle ne contient pas les opérateurs ∨ et →.
• (ii)Elle ne contient pas le quantificateur ∀.
• (iii)Pour toute sous-formule de la forme t_1 = t_2, t_1 est une variable dans V et
  - soit t_2 est une variable dans V;
  - soit t_2 = x + y avec x et y deux variables de V.

5. Retour sur les automates

• -Entrée : Une formule de Presburger φ sans variable libre.
• -Sortie : La valeur de vérité de cette formule.

• -Entrée : Une formule logique sans quantificateur φ sous forme normale conjonctive.
• -Sortie : Un booléen indiquant si φ est satisfiable.

type terme = V of int | Plus of int*int
type formule =
    |Existe of int * formule
    |Et of formule * formule
    |Non of formule
    |Egale of terme * terme

• □26 - Expliquer en langage courant le principe d'un algorithme qui prend en entrée une formule φ sous forme simple, l'indice de la plus grande variable apparaissant dans φ, et qui renvoie un automate reconnaissant L_φ.
• □27 - Faites tourner à la main votre algorithme en détaillant bien les étapes et automates intermédiaires sur la formule φ(x_2):=¬∃x_1.¬(x_1 = x_2) pour renvoyer l'automate correspondant
• □28 - Écrire une fonction automate_formule : formule -> int -> automate qui prend en entrée une formule φ sous forme simple et l'indice de la plus grande variable apparaissant dans φ, et qui renvoie un automate reconnaissant L_φ.
• □29 - Démontrer la correction de votre algorithme.
• □30 - En déduire une fonction est_vraie : formule -> int -> bool qui détermine pour une formule sous forme simple supposée sans variable libre et le plus grand indice de ses variables si elle est vraie.

A. Annexe : Règles de la déduction naturelle