Mines Informatique optionnelle MP 2025

A2025 ­ INFO MP

ÉCOLE NATIONALE DES PONTS et CHAUSSÉES,
ISAE-SUPAERO, ENSTA PARIS,
TÉLÉCOM PARIS, MINES PARIS,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT ATLANTIQUE, ENSAE PARIS,
CHIMIE PARISTECH - PSL.
Concours Mines-Télécom,
Concours Centrale-Supélec (Cycle International).

CONCOURS 2025

É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 10 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 d'option MP 2025

Préliminaires

L'épreuve est formée d'un problème unique, constitué de 28 questions, et porte 
sur l'apprentissage automatique (ou machine learning) d'un langage régulier que 
l'on souhaite déterminer
à partir de requêtes d'appartenance et de requêtes d'équivalence.
Les applications de l'apprentissage automatique d'un langage sont étendues. En 
analysant
le modèle appris, il est possible de détecter les divergences entre une 
spécification et sa mise en
oeuvre ou entre différentes mises en oeuvre tant pour des systèmes matériels 
que logiciels : par
exemple, protocoles de cartes à puce, réseaux de zombies sur internet (ou 
botnets), logiciels
patrimoniaux (ou legacy software) pour ne citer que quelques illustrations.
Le problème est divisé en quatre sections reliées entre elles. Une question 
peut être traitée
à condition d'avoir lu les définitions introduites jusque là. Dans la première 
section (page 2),
nous établissons quelques prolégomènes. Dans la deuxième section (page 4), nous 
nous
intéressons à une relation d'équivalence induite par le langage à apprendre. 
Dans la troisième
section (page 6), nous étudions un certain type d'arbre de décision. Dans la 
quatrième section
(page 8), nous construisons un automate reconnaissant le langage à apprendre.
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, T , ) et du point de vue informatique pour celle en romain avec 
espacement fixe
(par exemple n, t, delta).
Des rappels des extraits du manuel de documentation de OCaml portant sur le 
module
List sont reproduits en annexe (page 10).

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,
en reprenant l'en-tête de fonctions fourni par le sujet, sans s'obliger à 
recopier la déclaration
des types. Il est permis d'utiliser la totalité du langage OCaml sauf 
indication contraire. Il
est recommandé de s'en tenir aux fonctions les plus courantes afin de rester 
compréhensible.
Quand l'énoncé demande de coder une fonction, sauf demande explicite, il n'est 
pas nécessaire
de justifier que celle-ci est correcte ou de tester que des préconditions sont 
satisfaites.
Le barème tient compte de la clarté et de la concision des programmes : il est 
attendu que
l'on choisisse des noms de variables intelligibles ou encore que l'on structure 
de longs codes
par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.

Page 1 sur 10

Épreuve d'informatique d'option MP 2025

1. Alphabets, mots et automates
Dans l'ensemble du sujet, nous fixons un alphabet binaire  = {a, b} muni de 
l'ordre
alphabétique ; la notation  désigne le mot vide ; la notation  désigne 
l'ensemble des mots
sur l'alphabet  muni de l'ordre lexicographique induit. La concaténation de 
deux mots
u   et v   est notée uv.
Indication OCaml : Nous adoptons les types suivants :
1.
2.

type letter = A | B
type word = letter list

1 ­ Écrire une fonction OCaml cmp_letter (x1:letter) (x2:letter) : int dont la 
valeur de retour est nulle si les lettres x1 et x2 sont égales, est strictement 
négative si la lettre x1
précède strictement la lettre x2 dans l'ordre alphabétique et est strictement 
positive sinon.
2 ­ Écrire une fonction OCaml cmp_word (w1:word) (w2:word) : int dont la valeur 
de
retour est nulle si les mots w1 et w2 sont égaux, est strictement négative si 
le mot w1 précède
strictement le mot w2 dans l'ordre lexicographique et est strictement positive 
sinon. On
s'interdira l'usage de la fonction compare du module List et toute autre 
approche similaire.
3 ­ Décrire une structure de données immuables qui implémente un dictionnaire 
dont les
clés sont des mots de  et dont les valeurs sont d'un type quelconque. Il est 
attendu un nom
de structure classique, un type OCaml, une condition concernant l'ensemble des 
clés et un
invariant de bonne constitution.
Indication OCaml : Dans la suite du sujet, nous nous munissons d'un module OCaml
WordMap et d'un type 'a wordmap qui implémentent des dictionnaires de clés de 
type word et
de valeurs d'un type quelconque 'a. Nous disposons de la constante et des deux 
fonctions
suivantes :
-- WordMap.empty, de type 'a wordmap, qui désigne le dictionnaire vide.
-- WordMap.add, de type word -> 'a -> 'a wordmap -> 'a wordmap, telle que la 
valeur
de retour de WordMap.add w v d est un dictionnaire contenant les associations du
dictionnaire d ainsi qu'une association supplémentaire entre la clé w et la 
valeur v.
-- WordMap.find, de type word -> 'a wordmap -> 'a, telle que la valeur de 
retour de
WordMap.find w d est la valeur associée à la clé w dans le dictionnaire d.
4 ­ À titre d'exemple, déclarer deux valeurs OCaml delta_a et delta_b, de type
word wordmap, et une valeur OCaml un_a, de type bool wordmap, égales aux 
dictionnaires
respectifs
a :

a

7

a
7 

;

b :

a

7

7

a

Page 2 sur 10

et

1{a} :

a

 {faux, vrai}
7

faux
.
7

vrai

Épreuve d'informatique d'option MP 2025
Définition : Le terme automate s'entend systématiquement dans le sens d'un 
automate fini
déterministe complet, c'est-à-dire un quadruplet (Q, q0 , , 1F ) où
-- l'ensemble Q est un ensemble fini d'états,
-- l'état q0 est un élément particulier de Q appelé l'état initial,
-- l'application  est une application Q ×   Q appelée fonction de transition,
-- et l'application 1F : Q  {faux, vrai} est la fonction indicatrice d'une 
partie F de Q
appelée ensemble des états finals.
5 ­ À titre d'exemple, décrire en langue française le langage reconnu par 
l'automate
figuré ci-dessous puis énoncer une expression régulière qui le dénote. On ne 
demande pas de
justification.
b

b
a

a
a

6 ­ Dire s'il existe une expression régulière admettant l'automate figuré à la 
question 5
comme automate de Glushkov associé.
Indication OCaml : Dans ce sujet, l'ensemble des états des automates est 
systématiquement
choisi parmi les mots de  . Typographiquement, nous convenons de souligner les 
mots
servant d'état dans ce sujet et adoptons les types OCaml suivants
3.
4.
5.
6.

type state = word
type automaton = { initial : state ;
transitions : state -> letter -> state ;
finals : state -> bool }

7 ­ À titre d'exemple, définir une valeur OCaml automaton_example, de type 
automaton,
égale à l'automate figuré à la question 5.
On copiera et on complètera le code suivant :
1.
2.
3.
4.
5.
6.

let automaton_example =
{initial = .... ;
transitions = ( fun q x -> WordMap.find q
);
finals = .....
}

Page 3 sur 10

(.....)

Épreuve d'informatique d'option MP 2025
Définition : Pour tout automate A = (Q, q0 , , 1F ), pour tout état q de Q et 
pour tout
mot w de  , nous notons   (q, w) l'état d'arrivée dans l'automate A au terme du 
parcours
démarrant en l'état q et suivant les transitions de A étiquetées par les 
lettres successives du
mot w. Ainsi, la fonction   est une application Q ×   Q qui étend l'application 
.
8 ­ Écrire une fonction OCaml delta_star (a:automaton) (q:state) (w:word) : 
state
dont la valeur de retour est   (q, w).

9 ­ Écrire une fonction OCaml accepts (a:automaton) (w:word) : bool dont la 
valeur
de retour est le booléen vrai si le mot w est reconnu par l'automate A et le 
booléen faux sinon.
Il est demandé d'utiliser la fonction de la question précédente.

2. Relation de séparabilité par rapport à un langage
Il a été fixé, jusqu'à la fin de ce sujet, un certain langage régulier L   , 
que nous ne
connaissons pas mais que nous souhaitons apprendre. Autrement dit, notre 
objectif est de
produire en temps fini et efficacement un automate qui reconnait le langage L. 
Nous accédons
au langage L par l'intermédiaire d'un oracle qui répond à deux types de 
requêtes :

-- des requêtes d'appartenance, prenant la forme de la question « le mot w   
appartientil au langage fixé L ? »
-- et des requêtes d'équivalence, prenant la forme de la question : « 
l'automate A reconnait-il
le langage fixé L ? ».

En cas de réponse négative à une requête d'équivalence, l'oracle nous pourvoit 
d'un contreexemple c   pour lequel l'automate A se trompe. Autrement dit, soit 
le mot c appartient
au langage à apprendre L mais n'est pas reconnu par l'automate A, soit le mot c 
n'appartient
pas au langage à apprendre L mais est reconnu par l'automate A.
Indication OCaml : L'oracle est empaqueté dans un module Oracle ainsi signé :
7.
8.
9.
10.

type answer = Yes | Counterexample of word
val mem : word -> bool
val equiv : automaton -> answer

et s'utilise avec la syntaxe Oracle.mem w pour une requête d'appartenance ou 
Oracle.equiv a
pour une requête d'équivalence.

Définition : Nous notons 1 :   {faux, vrai} la fonction indicatrice de tout 
langage
   . Pour tout mot u   , 1 (u) prend la valeur vrai si et seulement si le mot u
appartient au langage .

Page 4 sur 10

Épreuve d'informatique d'option MP 2025
Définition : Deux mots quelconques u1   et u2   sont dits séparés par le mot v 
par
rapport à un langage    si l'on a
1 (u1 v) = 1 (u2 v),
autrement dit, si concaténation u1 v appartient au langage  tandis que la 
concaténation u2 v
n'appartient pas au langage  ou si la concaténation u1 v n'appartient pas au 
langage 
tandis que la concaténation u2 v appartient au langage . Nous disons alors que 
le mot v est
un discriminant.
Indication OCaml : Typographiquement, nous convenons de surligner les mots 
servant de
discriminant dans ce sujet et marquons le rôle de discriminant en adoptant 
l'alias de type
11.

type disc = word

10 ­ Écrire une fonction OCaml separated_by (u1:word) (u2:word) (v:disc) : bool
qui teste si les deux mots u1 et u2 sont séparés par rapport au langage à 
apprendre L par le
mot discriminant v .
Définitions : Deux mots quelconques u1   et u2   sont dits séparables par 
rapport à
un langage    , ou simplement séparables, s'il existe un discriminant qui les 
sépare. Ils
sont dits inséparables sinon. Nous notons u1  u2 la relation d'inséparabilité 
par rapport au
langage .
11 ­ Montrer que la relation d'inséparabilité par rapport à un langage 
quelconque est une
relation d'équivalence sur l'ensemble des mots  .
12 ­ Soient A = (Q, q0 , , 1F ) un automate quelconque, LA   le langage reconnu 
par
l'automate A et (u1 , u2 )  ( )2 deux mots tels que   (q0 , u1 ) =   (q0 , u2 
). Montrer que les
mots u1 et u2 sont inséparables par rapport au langage LA .
13 ­ Citer un théorème liant langages réguliers d'une part et langages reconnus 
par un
automate d'autre part. Déduire de la question 12 que le nombre de classes 
d'équivalences de
la relation d'inséparabilité par rapport au langage à apprendre L est fini.

Page 5 sur 10

Épreuve d'informatique d'option MP 2025

3. Arbre discriminant
Définition : Un arbre discriminant est un arbre de décision binaire, dont les 
sommets
internes sont étiquetés par des discriminants et dont les feuilles sont 
étiquetées par des états
distincts deux à deux.
12.
13.

type disctree =

Node of disctree * disc * disctree
| Leaf of state

La figure 1 présente un exemple d'arbre discriminant T0 , dans lequel les trois 
sommets internes
sont figurés par des cercles et les quatre feuilles par des rectangles.

aa

bbbba
a

aba

b

Figure 1 ­ Un exemple d'arbre discriminant : l'arbre T0
14 ­ Écrire une fonction OCaml states_of_disctree (t:disctree) : state list dont
la valeur de retour est une liste des étiquettes des feuilles de l'arbre 
discriminant T . Il est
attendu que la complexité en temps de states_of_disctree soit linéaire en le 
nombre de
feuilles et qu'on le justifie.
Par exemple, avec l'arbre discriminant T0 de la figure 1, la valeur 
states_of_disctree t0
peut égaler la liste [aa, a, , b], la liste [, a, aa, b] ou encore toute autre 
permutation.
Définition : Cribler un mot u   à travers un arbre discriminant T pour un 
langage L
consiste à construire l'unique chemin s0 - s1 - · · · - sk dans l'arbre T où :
-- le sommet s0 est la racine de T ,
-- pour tout indice i compris entre 0 et k - 1, le
sommet si est un sommet interne et, en notant vi
l'étiquette du sommet interne si , si le mot concaténé uvi appartient au 
langage à apprendre L, alors
le sommet si+1 est le fils gauche de si , sinon, le
sommet si+1 est le fils droit de si ,
-- le sommet sk est une feuille de l'arbre T .
et renvoyer l'état q porté par la feuille sk . L'état q
s'appelle le criblat du mot u et est noté u.

Page 6 sur 10

v0
uv0  L

v1
uv1 
/L

v2
uv2  L

q

u = q

Épreuve d'informatique d'option MP 2025

Par exemple, en supposant que le langage à apprendre L est dénoté par 
l'expression
régulière ab a, le criblat du mot abbba par l'arbre discriminant T0 (figure 1) 
est l'état
abbba = aa, qui est l'extrémité du chemin  - aa obtenu en observant que abbba 
appartient
à L. En revanche, le criblat du mot abb est l'état abb = a, qui est l'extrémité 
du chemin
 - bbbba - a obtenu en observant que abb appartient à L mais abbbbbba 
n'appartient pas à L.
15 ­ Donner le criblat du mot ba pour l'exemple précédent.
16 ­ Écrire une fonction OCaml sift (t:disctree) (u:word) : state dont la 
valeur de
retour est le criblat u du mot u à travers l'arbre discriminant T pour le 
langage L.
17 ­ Déterminer la complexité en temps dans le pire des cas de la fonction sift 
t u en
fonction de tout ou partie des grandeurs suivantes : la longueur |u| du mot u, 
le nombre n de
sommets de l'arbre T , la hauteur h de l'arbre T , le maximum M = maxvT |v| des 
longueurs
des mots discriminants de l'arbre T , le coût µ(|w|) d'un appel Oracle.mem w, 
le coût (|A|)
d'un appel Oracle.equiv a.
18 ­ Démontrer, en exhibant un discriminant, que deux mots de criblats 
distincts sont
toujours séparables.
19 ­ Démontrer que deux mots inséparables ont les mêmes criblats.

Définition : Nous disons qu'un arbre discriminant est accessible si, pour tout 
état w   ,
apparaissant dans la liste des étiquettes des feuilles, le criblat w du mot w 
est l'état w.
20 ­ Démontrer qu'il existe une constante dépendant uniquement du langage à 
apprendre
L, qui majore le nombre de feuilles d'un arbre discriminant accessible.
Définition : Nous disons qu'un arbre discriminant est démêlant s'il comporte au 
moins un
sommet interne et si l'étiquette de la racine est le discriminant mot vide .
21 ­ Démontrer que si deux mots u1 et u2   ont le même criblat par rapport à un
arbre discriminant démêlant, alors on a l'égalité 1L (u1 ) = 1L (u2 ).

Page 7 sur 10

Épreuve d'informatique d'option MP 2025

4. Automate tiré d'un arbre discriminant
Définitions : Nous disons qu'un arbre discriminant T est un crible s'il est 
accessible,
démêlant et si le mot vide  est un état qui apparait dans la liste des 
étiquettes des feuilles.
L'automate associé à un crible T pour un langage L est l'automate A ainsi 
défini :
-- l'ensemble des états de A est l'ensemble des étiquettes des feuilles de T ;
-- l'état initial de A est l'état  ;
-- la fonction de transition associe l'état w et la lettre x à l'état wx obtenu 
en criblant
le mot wx à travers l'arbre discriminant T pour le langage L ;
-- l'ensemble des états finals est l'ensemble des mots w où w est une étiquette 
d'une feuille
du sous-arbre gauche de T .
Par exemple, l'automate associé au crible T0 de la figure 1 pour le langage 
dénoté par ab a
est l'automate ainsi figuré
b

a

a

b

a

aa

a, b
b
a, b

22 ­ Écrire une fonction OCaml automaton_of_disctree (t:disctree) : automaton 
dont
la valeur de retour est l'automate associé au crible T .
On recopiera et on complètera le code suivant :
7.
8.
9.
10.
11.

let automaton_of_disctree (t:disctree) : automaton =
{ initial = .... ;
transitions = .... ;
finals = ....
}

23 ­ En supposant que le langage à apprendre L n'est ni le langage vide, ni le 
langage
plein  , décrire une construction, à l'aide des fonctions Oracle.mem et 
Oracle.equiv, d'un
premier crible formé d'un seul sommet interne et de deux feuilles.

Dans les questions 24, 25 et 26, nous notons A = (Q, , , 1F ) l'automate 
associé à un certain
crible T déjà construit. Nous supposons que Oracle.equiv a renvoie 
Oracle.Counterexample c,
où c est le mot non vide c = c0 c1 · · · c-1   . Nous nous proposons de 
construire un nouveau
crible T  ayant un état de plus que le crible T .

Page 8 sur 10

Épreuve d'informatique d'option MP 2025
Pour tout indice i compris entre 0 et , nous appelons i = c0 c1 · · · ci-1 le 
préfixe de c de
longueur i et i = ci+1 c1 · · · c-1 le suffixe de longueur  - i - 1 de sorte 
que le mot c admette
la factorisation c = i ci i . Nous notons les états
pi = i   

pi =   (q , i )  

et

et posons encore
i = pi ci i  

i = pi ci i   .

et

24 ­ Démontrer que l'on a 1L ( ) = 1L ( ).
On admet qu'il existe un indice i compris entre 0 et  -1 tel que les états pi 
et pi sont égaux, les
états pi+1 et pi+1 sont distincts et, alors, les mots pi ci et pi+1 sont 
séparés par le discriminant i .

25 ­ Écrire une fonction OCaml split (t:disctree) (c:word) : state * state * 
disc
dont la valeur de retour est le triplet (pj cj , pj+1 , j ) où l'entier j est 
le plus petit des indices i
compris entre 0 et  - 1 obtenu par la question 24.
On admet de la question 24 que l'arbre discriminant T  obtenu en substituant un 
arbre
constitué d'un sommet interne d'étiquette j , d'une feuille d'étiquette 
l'ancien état pj+1 et
d'une feuille d'étiquette un nouvel état pj cj à la place de la feuille 
d'étiquette pj+1 dans
l'arbre discriminant T jouit encore des propriétés de crible. Schématiquement,

devient

T

pj+1

T

ou

T

j

j

pj+1 pj cj

pj cj pj+1

26 ­ Écrire une fonction OCaml substitute (t:disctree) ((pp,p,s):state * state *
disc) : disctree ainsi spécifiée :
Précondition : Le triplet (pp, p, s) est la valeur de retour de la fonction 
split écrite à la
question 25.
Valeur de retour : Crible T  décrit ci-dessus.
27 ­ Concevoir un algorithme complet qui apprend un langage régulier à base de 
requêtes
d'appartenance et de requêtes d'équivalence en renvoyant un automate. Justifier 
sa terminaison
à l'aide d'un variant de boucle.
28 ­ Démontrer que l'automate construit à la question 27 possède un nombre 
d'état
minimal parmi l'ensemble des automates qui reconnaissent le langage à apprendre.

Page 9 sur 10

Épreuve d'informatique d'option MP 2025

A. Annexe : aide à la programmation en OCaml
Nous reproduisons des extraits de la documentation OCaml.

Opérations sur les listes : Le module List offre les fonctions suivantes :
-- length : 'a list -> int
Return the length (number of elements) of the given list.
-- append : 'a list -> 'a list -> 'a list
append l0 l1 appends l1 to l0. Same function as the infix operator @.
-- iter : ('a -> unit) -> 'a list -> unit
iter f [a1; ...; an] applies function f in turn to [a1; ...; an]. It is 
equivalent to
f a1; f a2; ...; f an.
-- map : ('a -> 'b) -> 'a list -> 'b list
map f [a1; ...; an] applies function f to a1, . . ., an, and builds the list [f 
a1; ...; f an]
with the results returned by f.
-- fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a list -> 'acc
fold_left f init [b1; ...; bn] is f (... (f (f init b1) b2) ...) bn.
-- for_all : ('a -> bool) -> 'a list -> bool
for_all f [a1; ...; an] checks if all elements of the list satisfy the 
predicate f. That
is, it returns (f a1) && (f a2) && ... && (f an) for a non-empty list and true 
if the
list is empty.
-- exists : ('a -> bool) -> 'a list -> bool
exists f [a1; ...; an] checks if at least one element of the list satisfies the 
predicate
f. That is, it returns (f a1) || (f a2) || ... || (f an) for a non-empty list 
and
false if the list is empty.
-- mem : 'a -> 'a list -> bool
mem a set is true if and only if a is equal to an element of set.
-- filter : ('a -> bool) -> 'a list -> 'a list
filter f l returns all the elements of the list l that satisfy the predicate f. 
The order
of the elements in the input list is preserved.
D'après https://ocaml.org/manual/5.1/api/List.html
Fin de l'épreuve

Page 10 sur 10