Mines Option Informatique MP 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

• □4 - É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

• □5 - Démontrer que L(A_1) = E.
• □6 - Montrer que pour tout m ∈ L(A_1), v_1(m) ≡ v_2(m)[2 × v_2(m)].
• □7 - Décrire sans justifier le langage L(A_2) en donnant une condition nécessaire et suffisante pour qu'un mot m sur Σ_2 soit dans le langage qui fait intervenir v_1(m) et v_2(m).

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

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 ∀.

• soit t_2 est une variable dans V;
• soit t_2 = x + y avec x et y deux variables de V.
  □ 20 - Montrer que toute formule de Presburger φ est équivalente à une formule sous forme simple.

5. Retour sur les automates

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