Mines Informatique optionnelle MP 2026

A2026 ­ INFO MP

É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.
Concours Mines-Télécom,
Concours Centrale-Supélec (Cycle International).

CONCOURS 2026

ÉPREUVE D'INFORMATIQUE MP
Durée de l'épreuve : 3 heures
L'usage de la calculatrice ou de tout dispositif électronique est interdit.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE - MP
Cette épreuve concerne uniquement les candidats de la filière MP.
L'énoncé de cette épreuve comporte 9 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur 
d'énoncé, il le
signale sur sa copie et poursuit sa composition en expliquant les raisons des 
initiatives qu'il est
amené à prendre.
Les sujets sont la propriété du GIP CCMP. Ils sont publiés sous les termes de 
la licence
Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de 
Modification 3.0 France.
Tout autre usage est soumis à une autorisation préalable du Concours commun 
Mines-Ponts.

Épreuve d'informatique MP option informatique 2026

Préliminaires
L'épreuve est composée d'un problème unique, comportant 30 questions. Le 
problème
est divisé en cinq sections. Dans la première section (page 2), nous 
implémentons plusieurs
fonctions mathématiques. Dans la deuxième section (page 3), nous étudions des 
automates
sur un alphabet particulier et nous nous intéressons à une implémentation. Dans 
la troisième
section (page 5), nous nous intéressons à la reconnaissabilité de certains 
langages sous cet
alphabet. Dans la quatrième section (page 5), nous nous intéressons à 
l'arithmétique de
Presburger et ses formules logiques. Enfin, dans la cinquième et dernière 
section (page 7), nous
cherchons à décider de la satisfiabilité de ces formules à l'aide des automates 
précédemment
étudiés.
Dans tout l'énoncé, un même identificateur écrit dans deux polices de 
caractères différentes
désigne la même entité, mais du point de vue mathématique pour la police en 
italique (par
exemple n) et du point de vue informatique pour celle en romain avec espacement 
fixe (par
exemple n).
Des rappels portant sur les règles de la déduction naturelle sont fournis en 
annexe.

Travail attendu

Pour répondre à une question, il est permis de réutiliser le résultat d'une 
question antérieure,
même sans avoir réussi à établir ce résultat.
Il faudra coder des fonctions à l'aide du langage de programmation OCaml 
exclusivement. Les fonctions des modules List et Array peuvent être utilisées 
sans explication. Il
est cependant recommandé de s'en tenir aux fonctions les plus courantes afin de 
rester
compréhensible.
Le barème tient compte de la clarté et de la concision des programmes. Nous 
recommandons
de choisir des noms de variables intelligibles ou encore de structurer de longs 
codes par des
blocs ou par des fonctions auxiliaires dont on décrit le rôle.

Introduction

On note N l'ensemble des entiers naturels. Pour tout couple d'entiers a, b tel 
que a  b,
on note Ja, bK l'ensemble des entiers de a à b compris. Pour tout ensemble E, 
on note P (E)
l'ensemble des parties de E, c'est-à-dire l'ensemble des sous-ensembles de E. 
Pour tout
ensemble fini E, on note |E| son cardinal.
Pour tout mot m, on note |m| la taille de m, qui correspond à son nombre de 
lettres.
Dans tout le sujet, pour tout entier n positif, on notera n l'alphabet composé 
des vecteurs
colonnes de taille n à valeurs dans {0, 1}. Par exemple,
(

2 =

!

!

!

!)

0
1
0
1
,
,
,
0
0
1
1

.

Pour tout entier i dans J1, nK, et pour tout mot m sur n , on note i (m) la 
projection de
m sur la composante i, c'est-à-dire, le mot sur {0, 1} composé du terme à la 
i-ème ligne sur
chaque lettre de m.
Par abus de notation, on s'autorise à confondre la lettre 0 et 1 de l'alphabet 
{0, 1} avec les
entiers 0 et 1. Pour tout mot u de taille |u| = k sur {0, 1} tel que u = u0 . . 
. uk-1 , on va noter
v(u) la valeur suivante :

Page 1 sur 9

Épreuve d'informatique MP option informatique 2026

v(u) =

k-1
X

2j uj

j=0

Autrement dit, v(u) est l'entier dont u en est une de ses représentations en 
binaire telles
que le bit de poids faible soit à gauche, donc à l'inverse du sens habituel.
Pour un mot m sur n et un entier i entre 1 et n, on note vi (m) = v(i (m)).
Considérons par exemple le mot m suivant :

0 1 1 0 1 0 1 1
       
m=
10001100
1 1 0 0 1 1 1 0

On a 2 (m) = 10001100, v1 (m) = 2 + 4 + 16 + 64 + 128 = 214, v2 (m) = 49 et v3 
(m) = 115.
Dans ce sujet, un automate fini non déterministe à un seul état initial, qu'on 
s'autorise à
appeler simplement automate, est défini comme un tuple A = (, Q, q0 , F, ) où :
--  est un alphabet fini ;
-- Q est un ensemble fini d'états ;
-- q0 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.
On dit qu'un automate A = (, Q, q0 , , F ) est déterministe complet lorsque 
pour chaque
sommet q  Q, et chaque lettre a  , on a |(q, a)| = 1.
a
Pour deux états p et q de Q, et pour toute lettre a de , on note p -
 q si q  (p, a). On
dit qu'il existe une transition de p à q étiquetée par a. On prend comme 
convention graphique
d'indiquer l'état initial par une flèche entrante et les états finaux en les 
entourant.
Pour un automate A on note L(A) le langage reconnu par A.
Dans tout le sujet, on fera l'hypothèse simplificatrice qu'en OCaml, on dispose 
d'une
mémoire infinie et que les variables peuvent stocker des valeurs aussi grandes 
que l'on
souhaite.

1. Implémentation de quelques fonctions utiles
Commençons par implémenter plusieurs fonctions mathématiques qui nous seront 
utiles
dans la suite.
1 ­ Écrire une fonction pow2 : int -> int qui prend en entrée un entier n et 
renvoie
2 . On attend une fonction récursive de complexité temporelle en O(log(n)) qui 
n'utilise pas
les opérateurs de décalage lsr et lsl.
n

2 ­ Démontrer que la complexité de votre algorithme est bien en O(log(n)).
On représente en OCaml les lettres de n à l'aide du type int array en utilisant 
des
tableaux de dimension n dont les éléments sont à valeurs dans {0, 1}.
3 ­ Exhiber une bijection entre J0, 2n - 1K et n .
Page 2 sur 9

Épreuve d'informatique MP option informatique 2026
À présent, on souhaite implémenter notre bijection.
4 ­ Écrire une fonction decompose : int -> int -> int array qui prend en entrée
x et n tels que x  J0, 2n - 1K 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
Considérons les automates A1 et A2 suivants :
!

!

0
0

!

0
1
,
0
0

!

1
1

q0

!

!

0
1
,
1
1

q1

!

q2

!

1
0
,
0
1

Figure 1 ­ Représentation de l'automate A1

!

!

!

!

0
0
1
,
,
0
1
1

!

1
0

!

!

0
1
1
,
,
0
0
1

q0

q1
!

0
1

Figure 2 ­ Représentation de l'automate A2
Soit E l'ensemble des mots m sur 2 tels que v2 (m) est la plus grande puissance 
de 2 qui
divise v1 (m).
5 ­ Démontrer que L(A1 ) = E.
6 ­ Montrer que pour tout m  L(A1 ), v1 (m)  v2 (m)[2 × v2 (m)].
7 ­ Décrire sans justifier le langage L(A2 ) en donnant une condition 
nécessaire et suffisante
pour qu'un mot m sur 2 soit dans le langage qui fait intervenir v1 (m) et v2 
(m).

Page 3 sur 9

Épreuve d'informatique MP option informatique 2026

8 ­ Proposer sans justifier un automate à 3 états qui reconnaît le langage L 
défini par :
L = {m  3 | v1 (m) = v3 (m) ou v2 (m) = v3 (m)}
.
Pour implémenter les automates, on utilise le type automate suivant en OCaml. Un
automate sur n à k états est représenté en utilisant un entier différent dans 
J0, k - 1K pour
chaque état. L'état initial est toujours l'état 0.
type automate = {
k : int ;
n : int ;
finaux : bool array ;
delta : int -> int array -> int list ;
}
Ici, k correspond donc au nombre d'états de l'automate, n correspond à n, 
finaux est un
tableau de booléens de taille k qui indique si un état est final, et delta est 
la fonction de
transition prenant en paramètre un état q et une lettre a, représentée par un 
tableau d'entiers
de taille n, et renvoie la liste des états de (q, a)
9 ­ Écrire une fonction est_deterministe_complet : automate -> bool qui vérifie
si un automate A = (n , Q, q0 , , F ) est déterministe complet. On attend une 
complexité
temporelle en O (n × |Q| × |n |). Justifier la complexité obtenue.
On se propose maintenant d'implémenter l'algorithme de déterminisation des 
automates.
10 ­ Soit A = (, Q, q0 , , F ) un automate fini non déterministe. Donner la 
construction
formelle d'un automate déterministe reconnaissant L(A).
11 ­ Écrire une fonction union : int array -> automate -> int array -> int
array qui prend en entrée les paramètres etats, a et lettre, tels que :
-- 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.
Cette fonction doit renvoyer un tableau t de taille k, tel que t.(i)=1 s'il 
existe un q tels
lettre
que etats.(q)=1 et q --- i est une transition de a, et t.(i)=0 sinon.
12 ­ En déduire une fonction determinise : automate -> automate qui prend en
entrée un automate et renvoie un automate déterministe complet reconnaissant le 
même
langage.
Indication : On pourra utiliser la fonction decompose plusieurs fois.

Page 4 sur 9

Épreuve d'informatique MP option informatique 2026
On appelle complémentaire d'un langage L sur un alphabet  le langage L des mots 
sur 
n'appartenant pas à L.
13 ­ Écrire une fonction complementaire : automate -> automate qui prend en 
entrée
un automate et renvoie un automate reconnaissant son langage complémentaire.

14 ­ Considérons deux automates A1 = (n , Q1 , q1 , 1 , F1 ) et A2 = (n , Q2 , 
q2 , 2 , F2 ).
Donner la construction formelle d'un automate ayant pour ensemble d'états Q1 × 
Q2 et
reconnaissant L(A1 )  L(A2 ). Ici Q1 × Q2 est le produit cartésien de Q1 et Q2 .

On suppose dans la suite disposer d'une fonction OCaml intersection : automate
-> automate -> automate qui prend en entrée deux automates et renvoie un 
automate
reconnaissant l'intersection de leurs langages.

3. Opérations arithmétiques
On s'intéresse à présent aux opérations arithmétiques en binaire et à la 
possibilité de les
représenter à l'aide d'automates sur 3 .
15 ­ Donner, dans un premier temps sans justifier, un automate à deux états 
reconnaissant
le langage L+ = {m  3 | v1 (m) + v2 (m) = v3 (m)}.
16 ­ Démontrer que l'automate proposé dans la question précédente reconnaît 
bien L+ .

17 ­ Le langage L× = {m  3 | v1 (m) × v2 (m) = v3 (m)} est-il reconnaissable ? 
Justifier.

4. Arithmétique de Presburger
L'arithmétique de Presburger est l'arithmétique usuelle des entiers et de 
l'addition, mais
sans la multiplication.
Soit V un ensemble infini de variables.
L'ensemble des termes est défini inductivement de la façon suivante :
-- pour tout x  V, x est un terme ;
-- pour deux termes t1 et t2 , t1 + t2 est un terme.
L'ensemble des formules de Presburger, qu'on s'autorise à appeler formules, est 
ensuite
défini inductivement de la façon suivante :
-- pour t1 et t2 deux termes, t1 = t2 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.

Page 5 sur 9

Épreuve d'informatique MP option informatique 2026

L'évaluation des formules suit le sens habituel de l'opérateur d'égalité =, et 
des opérateurs
logiques. Les quantificateurs ont leur sens usuel avec des variables prises à 
valeurs dans
l'ensemble N. On utilise des parenthèses pour repérer les sous-formules 
lorsqu'il y a ambiguïté
et pour indiquer les priorités d'ordre des opérations usuelles.
Pour toute formule , et toute sous-formule x. ou x. de , on dit que toutes les
occurrences de x dans  sont liées. Les occurrences non liées de x dans  sont 
dites libres. Si
 possède des occurrences libres de x, on dit que x est une variable libre de .
Dans la formule x. y. (z = t + y  z = x)  (w. z = t + w), les variables x, y et 
w sont
liées, et les variables libres sont z et t.
Pour x un vecteur de variables, on notera souvent (x) pour signifier que x est 
l'ensemble
des variables libres de . Une assignation est une fonction des variables libres 
de  vers N.
Pour  une formule de Presburger et a une assignation de ses variables libres, 
on note JKa
la valeur de vérité de  dans l'assignation a.
Par exemple, considérons la formule  (x, y) := z. y = x + z, où := est un 
opérateur de
définition. Ici, z est une variable liée, et y et x sont des variables libres. 
Pour un x et un y
donnés, cette formule est vraie si et seulement s'il existe un entier z dans N 
tel que y = x + z,
donc si et seulement si x  y.
Pour deux formules  et  ayant le même ensemble de variables libres, on dit 
qu'elles sont
équivalentes, si pour toute assignation de ces variables libres, elles ont la 
même valeur de
vérité.
18 ­ Donner une formule de Presburger div2 (x) qui est vraie si et seulement si 
x est
divisible par 2.

19 ­ Pour tout entier n  N, donner une formule de Presburger fn (x) qui est 
vraie si et
seulement si x = n.
Attention, n n'est pas un terme et ne peut donc pas apparaître dans votre 
formule sous cette
forme.
On dit qu'une formule est sous forme simple si elle vérifie les propriétés 
suivantes :
(i) Elle ne contient pas les opérateurs  et .
(ii) Elle ne contient pas le quantificateur .
(iii) Pour toute sous-formule de la forme t1 = t2 , t1 est une variable dans V 
et
-- soit t2 est une variable dans V ;
-- soit t2 = x + y avec x et y deux variables de V.
20 ­ Montrer que toute formule de Presburger  est équivalente à une formule 
sous forme
simple.
On veut à présent montrer que certaines formules sont des tautologies à l'aide 
de la
déduction naturelle.
21 ­ Prouver à l'aide de la déduction naturelle le séquent suivant où (x) 
désigne une
formule faisant apparaître la variable libre x et (y) désigne une formule 
faisant apparaître
la variable libre y.
 ((x)  (y))  (¬(x)  (y))

Page 6 sur 9

Épreuve d'informatique MP option informatique 2026
Pour  une formule, x une variable, et t un terme, on note [t/x] la formule  où 
toutes les
occurrences libres de x ont été remplacées par le terme t. Pour pouvoir 
effectuer des preuves
sur des formules plus complexes, on introduit les règles suivantes sur 
l'égalité pour x une
variable,  une formule et t un terme :
t=t

, x = t  [t/x]
sub=
, x = t  

ax=

De plus, on sait que l'addition est associative et pour simplifier les preuves, 
on s'autorise à
utiliser cette propriété dans nos arbres. Par exemple, pour t1 , t2 et t3 des 
termes, on peut
considérer que t1 + (t2 + t3 ) est le même terme que (t1 + t2 ) + t3 ainsi que 
t1 + t2 + t3 .
22 ­ Donner une formule de Presburger (x, y, z) avec 3 variables libres 
exprimant le fait
que l'égalité est transitive sur les variables et la prouver à l'aide de la 
déduction naturelle.

5. Retour sur les automates
23 ­ Écrire une fonction sans_zero : automate -> automate qui prend en entrée un
automate et qui renvoie une copie de cet automate ayant pour états finaux tout 
étatpermettant

0
 
d'accéder à un état final par une suite de transitions étiquetées par la lettre 
. . . dans
0
l'automate initial.
Avant de faire le lien entre automate et formules, on doit d'abord s'intéresser 
au problème
des différentes représentations des entiers dues aux zéros non significatifs.
Soit n un entier naturel non nul et i dans J1, nK. Soit L un langage sur n . On 
note Li le
langage défini par :
Li = {m  n | w  L, k  J1, nK, k = i, k (m) = k (w)}.
Autrement dit, il s'agit de l'ensemble des mots égaux à un mot de L sauf 
possiblement à la
ligne i.

0
0 1 

24 ­ Soit L =  , 1 , 01, donner L2 .

1

0

1

25 ­ Écrire une fonction automate_existe : automate -> int -> automate qui
prend en entrée un automate A et un entier i et qui renvoie un automate 
reconnaissant
L(A)i .
Soit n un entier supérieur ou égal à 3. Soit, i, j et k des entiers de J1, nK.
On note Li,j,k le langage {m  n | vi (m) + vj (m) = vk (m)}. On suppose disposer
d'une fonction automate_somme : int -> int -> int -> int -> automate telle que
automate_somme n i j k renvoie un automate reconnaissant Li,j,k .

Page 7 sur 9

Épreuve d'informatique MP option informatique 2026

On note L=i,j le langage {m  n | vi (m) = vj (m)}. On suppose disposer d'une 
fonction
automate_egalite : int -> int -> int -> automate telle que automate_egalite n
i j renvoie un automate reconnaissant L=i,j .
Considérons une formule sous forme simple  utilisant n variables qu'on note {x1 
, . . . , xn }.
Soit k le nombre de variables libres de . Soit une fonction f strictement 
croissante de J1, kK
dans J1, nK telle que les {xf (1) , . . . , xf (k) } est l'ensemble des 
variables libres de . Pour tout
mot m de n , on note am l'assignation des variables libres de  définie pour i 
dans J1, kK par
am (xf (i) ) = vf (i) (m). On note L le langage
L = {m  n | JKam est vrai } .
Intéressons nous à l'implémentation des formules de Presburger sous forme 
simple. On
représente les variables par des entiers. On utilise les types OCaml suivants :
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 (x2 ) := ¬x1 . ¬(x1 = x2 ) 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.

Page 8 sur 9

Épreuve d'informatique MP option informatique 2026

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

On présente les règles de la déduction naturelle suivantes.
Les arbres de preuves doivent être effectués à partir de l'ensemble de règles 
fourni ci-dessous.

, A  A

B
aff
, A  B

ax

  A  ¬A

, ¬A  
RAA
A

t.e.

, A  B
i
AB

AB A
e
B
AB g
e
A

A B
i
AB

A
gi
AB

B
di
AB

, A  
¬i
  ¬A

A

AB d
e
B

  A  B , A  C , B  C
e
C

  ¬A   A
¬e

, A, B  C
cut
, A  B  C
Fin de l'épreuve

Page 9 sur 9