Mines Informatique optionnelle MP 2021

A2021 --- INFO MP

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
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 2021
ÉPREUVE D'INFORMATIQUE MP

Durée de l'épreuve : 3 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement les candidats de la filière MP.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE - MP

L'énoncé de cette épreuve comporte 11 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur 
d'énontcé, 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 CCMEP. 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'option informatique MP 2021

Préliminaires

L'épreuve est composée d'un problème unique, comportant 30 questions. Après 
cette
section de préliminaires et une section de présentation du jeu du solitaire, le 
problème
est divisé en deux sections indépendantes, pages 4 et 8. Dans la première 
section, nous
étudions le jeu du solitaire sur un tablier de forme classique par des méthodes 
de théorie
des graphes. Dans la seconde section, nous étudions le jeu du solitaire sur un 
tablier en
bande unidimensionnelle par des méthodes de théorie des automates. Pour 
répondre à
une question, un candidat pourra réutiliser le résultat d'une question 
antérieure, même
s'il n'est pas parvenu à établir ce résultat.

Concernant la programmation

Il faudra coder des fonctions à l'aide du langage de programmation OCaml, en 
reprenant
l'entête de fonction fournie par le sujet, sans nécessairement reprendre la 
déclaration
des types. Pour écrire une fonction, on pourra faire appel à d'autres fonctions 
définies
dans les questions précédentes ; on pourra aussi définir des fonctions 
auxiliaires. Quand
l'énoncé demande de coder une fonction, il n'est pas nécessaire de justifier 
que celle-ci
est correcte, sauf si l'énoncé le demande explicitement. Si les paramètres 
d'une fonction
à coder sont supposés vérifier certaines hypothèses, il ne sera pas utile de 
tester si les
hypothèses sont bien vérifiées dans le code de la fonction.

Dans tout l'énoncé, un même identificateur écrit dans deux polices de caractère
différentes désignera 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).

Aide à la programmation en OCaml
Opérations sur les listes : Sans qu'il ne soit imposé de coder dans un style de 
pro-
grammation les utilisant, on pourra s'appuyer sur les fonctions suivantes :

-- append, de type 'a list -> 'a list -> ?'a list, qui concatène deux listes en 
une
seule liste ;

-- filter, de type ('a -> bool) -> 'a list -> 'a list, telle que filter p 1 ren-
voie la liste des éléments x de la liste £ tels que le prédicat p(x) vaut true, 
en
respectant l'ordre de la liste ;

-- flatten, de type 'a list list -> 'a list, qui concatène une liste de listes 
en
une seule liste ;

-- fold, de type ('a -> 'b -> 'a) -> ?'a -> 'b list -> ?'a, telle que

fold f a [bi; ..; bn] renvoie f(..(f(f a b1) b2)..) bn:
-- map, de type ('a -> 'b) -> 'a list -> 'b list, telle que map f [ai; ..; an]
renvoie la liste [f ai; ..; f an].

Page 1 sur 11
Épreuve d'option informatique MP 2021

Opérations sur les couples : On rappelle que
-- ]a fonction fst, de type 'a * ?'b -> ?'a, renvoie le premier terme d'un 
couple :

-- Ja fonction snd, de type 'a * ?'b -> ?'b, renvoie le second terme d'un 
couple.

Opérateurs logiques sur les entiers : Nous supposons que les entiers naturels, 
de
type int en OCaml, sont systématiquement codés à l'aide de 62 bits. Dans un 
texte
mathématique, on pourra signaler la représentation binaire par une barre 
horizontale.
Pour tous entiers n et k avec 0 < n < 2% et 0 < k < 62, nous notons [n]4 le Æ° bit de poids le plus faible de la représentation binaire de n, ce qui permet d'écrire n = [n{g1[n160 : - - [nlo. Le tableau ci-dessous rappelle le résultat de quelques-uns des opérateurs logiques de OCamil qui agissent bit à bit sur deux entiers naturels a et b. Tous ces opérateurs renvoient un élément de type int. Dans ce tableau, les symboles À, V, @ et -- désignent respectivement le « et », le « ou », le « ou exclusif » entre deux booléens et la négation d'un booléen. Opérateur Nom Résultat exprimé sur 62 bits a land b Et logique bit à bit ([ale1 À lble1) --- (ali À lbli)([alo A [blo) a lor b Ou logique bit à bit ([ale1 V [ble1) - - - (ali V [bhi)([alo V blo) a lxor b Xor logique bit à bit | ([ale1 @ [blé1) : : - (lal1 ® bl1)([alo & (bb) Inot a Non logique bit à bit (--{al61) -:- (--lal1)(-lalo) a 1s1l b | Décalage vers la gauche lal61 0 * ** [al1[alo 0 + --0 nn b zéros à droite a lsr b | Décalage vers la droite 0--:0 lale1 - --lalpr1lalr nn, b zéros à gauche Par exemple, lorsque a = 6 et b -- 3, les écritures sur 62 bits de a et b sont a = 0---0110 et b--0---O0011 et -- Je calcul de a land b vaut l'entier 2, dont l'écriture sur 62 bits est 0 --- 0010: -- Je calcul de a lor b vaut l'entier 7, dont l'écriture sur 62 bits est 0---0111: -- Je calcul de a 1xor b vaut l'entier 5, dont l'écriture sur 62 bits est 0 ---O0101: -- le calcul de a 1s1 b renvoie 48, dont l'écriture sur 62 bits est 0 - -- 0110000: -- Je calcul de a 1lsr b renvoie O0 puisque les deux bits non nuls de a sont sortis de la représentation. L'entier 2F, avec 0 < k < 62, peut commodément se définir en OCaml par 1 1s1 k. Page 2 sur 11 Épreuve d'option informatique MP 2021 Le jeu du solitaire Le jeu du solitaire se joue sur un tablier percé d'encoches disposées en quadrillage et remplissant une certaine forme géométrique. Parmi les tabliers les plus fréquents, le tablier européen est formé de 37 encoches organisées en octogone O O © OoeO0OO0OO0OO OO0O0O0O0O0OO0O OO0O0OO0OO0OO0O OO0OO0OO0OO0OO0O © O © O © O © ® dont on peut décrire les coordonnées par {(x, 9) EN: 0 1
est un entier,

av

et dont on peut décrire les coordonnées par
{ (x, 9) e N°; 10) && ((m land (m-1)) = O) ;;

renvoie true si le motif m est un motif ponctuel et false sinon.

[1 9 -- Écrire, à l'aide des opérateurs logiques sur les entiers, une fonction
inclus (mimotif) (p:ponctuel) : bool qui renvoie true si le motif ponc-
tuel p est inclus dans le motif m ou false dans le cas opposé. Donner une
preuve mathématique du résultat.

[] 10 -- Écrire, à l'aide des opérateurs logiques sur les entiers, une fonction
voisin _g (p:ponctuel) : ponctuel qui calcule la translation par une encoche
vers la gauche du motif ponctuel p. Si le motif ponctuel p sort du tablier, la
valeur de retour est le motif vide 0.

Dans la suite du problème, nous supposerons avoir codé des fonctions similaires
voisin _d, voisin _h et voisin _b qui calculent les décalages d'un motif 
ponctuel respecti-
vement vers la droite, vers le haut et vers le bas. Nous déclarons une 
constante globale

par let voisins = [voisin g; voisin d; voisin h; voisin bl;;.

Page 6 sur 11
Épreuve d'option informatique MP 2021

1.3 Coups simples et composés

1.4

Indication OCamil :

[] 11 -- Écrire une fonction coup_simple ((m, p) : motif * ponctuel)
(motif * ponctuel) list qui prend en entrée un motif quelconque m et
un motif ponctuel p contenu dans m et qui construit la liste des couples
(m/,p') où m' est un motif obtenu à partir de m à la suite du déplacement
par un coup simple du fichet initialement placé dans p et où p' est le motif
ponctuel repérant le même fichet après son déplacement.

[] 12 -- Écrire une fonction coup_ compose ((m, p) : motif * ponctuel)
(motif * ponctuel) list qui prend en entrée un motif quelconque m et un
motif ponctuel p contenu dans m et qui construit la liste des couples (m', p')
où rm est un motif obtenu à partir de m à la suite du déplacement par un
coup composé du fichet initialement placé dans p et où p' est le motif ponctuel
repérant le même fichet après son déplacement.

[] 13 -- Écrire une fonction mouvements (m:motif) : motif list dont la va-
leur de retour est la liste de tous les motifs que l'on peut obtenir en jouant 
un
coup composé depuis le motif m, n'importe quel fichet pouvant être déplacé.

Partie de longueur minimale

dictionnaires, nous disposons des fonctions suivantes :

la fonction create, de type unit -> dico, qui permet de créer un dictionnaire 
vide:

la fonction add, de type dico -> motif -> int -> unit, telle que add d m n 
permet
d'ajouter au dictionnaire d une association entre la clé m et l'entier n (si une

association de clé m existe déjà, elle est remplacée) :

la fonction mem, de type dico -> motif -> bool, telle quemem d m renvoie le 
booléen

true si la clé m est membre du dictionnaire d ou false sinon.

la fonction find, de type dico -> motif -> int, telle que find d m renvoie la 
valeur

associée à la clé m si la clé est membre du dictionnaire d ou une erreur sinon.

©] 14 -- Écrire une fonction add and mem (d:dico) (s:int) (m:motif)
bool qui ajoute l'association entre le motif m et l'entier s dans le 
dictionnaire d
si le motif m est initialement absent du dictionnaire d. La valeur de retour
de la fonction est true si le dictionnaire a été modifié et false sinon.

[] 15 -- Écrire une fonction strate (d:dico) (s:int) (l:motif list)

motif list qui, pour tout motif m que l'on peut obtenir après un coup
composé à partir d'un motif de la liste £, ajoute l'association entre le motif 
m et
l'entier s au dictionnaire d si le motif m n'est pas présent dans le 
dictionnaire d.
La valeur de retour de la fonction est la liste des motifs que la fonction 
ajoute.

Page 7 sur 11

Nous utilisons dans cette sous-section une structure de données
de dictionnaire, avec modification en place, permettant d'associer des clés de 
type motif
et des valeurs de type int. Nous notons le type de cette structure dico. Pour 
utiliser ces
Épreuve d'option informatique MP 2021

[] 16 --- Dans cette question, nous supposons qu'il est possible de passer
d'un motif m; à un motif my par une suite de coups. Écrire une fonction
partie minimale (mi:motif) (mf:motif) : int qui calcule le nombre mini-
mal de coups composés à jouer pour passer du motif initial m; au motif final
my. On pourra utiliser un dictionnaire qui associe des motifs au nombre de
coups minimal pour les atteindre depuis le motif m;.

[] 17 -- Peut-on considérer que la réponse donnée à la question 16 observe le
parcours nommé à la question 1 ? Introduire un graphe puis argumenter.

2 Reconnaissance des motifs résolubles sur le tablier
unidimensionnel

Dans toute la section 2 du sujet, une joueuse joue sur des tabliers 
rectangulaires de
dimension n X 1, où n est un entier naturel pouvant varier d'une partie à une 
autre.

@) @ © © © © : ©

Dans cette section, le but de la joueuse est de faire disparaître tous les 
fichets sauf un
par une suite de coups, autrement dit de jouer une partie qui amène le motif 
initial à un
motif ponctuel. Lorsque ceci est possible, nous disons que le motif initial est 
résoluble et
que la partie est gagnante.

Nous introduisons l'alphabet binaire Y = {0,1} et notons Y* l'ensemble des mots
sur ». Pour tout mot w = 01...0, EUR X*, nous notons [wlz le k° symbole 64 de w.

Le mot d'un motif M du tablier rectangulaire de dimension n x 1 est le mot w 
formé
de n symboles de l'alphabet Y tel que, pour k variant entre 1 et n, le symbole 
[w]z vaut 1
si la k° encoche à partir de la gauche appartient au motif M et vaut 0 sinon. 
Par exemple.
sur ce tablier, le motif eoeeo est décrit par le mot 10110 EUR >*.

Dans toute cette section, nous ne considérons que des coups simples. Une partie 
est
par conséquent une suite finie W de mots wo, w1, ..., w,, de même longueur 
telle que
pour tout indice à compris entre 0 et m -- 1, le mot w;,., est obtenu à partir 
du mot w;
en remplaçant dans le mot w; un facteur 110 par les symboles 001 ou bien en 
remplaçant
un facteur 011 par les symboles 100. Dans le premier cas, nous parlons de coup 
vers la
droite ; dans le second cas, nous parlons de coup vers la gauche. Une partie 
est gagnante
si, de plus, le dernier mot w,, de la partie ne comprend le symbole 1 qu'une 
seule fois.

L'objectif de cette section est d'étudier le langage R EUR Y* des mots de 
longueur
quelconque de motifs résolubles.

Page 8 sur 11
Épreuve d'option informatique MP 2021

2.1 Mots de motifs ponctuels

Nous notons P EUR X* le langage des mots de longueur quelconque de motifs 
ponctuels.

[] 18 -- Donner, sans justification, une expression rationnelle qui décrit le
langage P.

[] 19 -- Dessiner, sans justification, un automate fini qui reconnaît le lan-
gage P.

CT 20 - Le langage P est-il un langage local ?

2.2 Bascules de l'état d'une encoche

Soient W = (wo, w1,...,Wm) EUR (X")"*7 une partie en m coups simples joués sur 
le
tablier de dimension n x 1 et & un entier compris entre 1 et n. Dans cette 
sous-section,
nous souhaitons démontrer qu'il existe une constante « indépendante des entiers 
n, m ou
k telle la suite des (m + 1) symboles [wolx, [wilr, ..., [um] ne change jamais 
de valeur à
plus de @ reprises.

Nous notons @ -- v5=1 l'une des racines du polynôme X°+X --1. On pourra 
utiliser sans
preuve l'inégalité DA D < 2. Pour tout mot w EUR Y" de longueur n. nous introduisons le variant V4;(w) par la somme VA(w) -- > DA av], e KR.

[] 21 - Montrer qu'il existe un réel S, indépendant des entiers n et k, tel
que, pour tout mot w EUR X", on ait l'inégalité V,(w) < S. [1 22 -- Montrer que la suite des (m +1) variants V,(wo), Vilwi), ..., V&(wm) est une suite de réels décroissante. [] 23 -- Montrer que si, pour un indice à compris entre 0 et m -- 1, le symbole lu], vaut 1 et le symbole [w;,1], vaut 0, alors on à Va(w;11) < Ve(wi) -- 1. [] 24 -- En déduire qu'il existe une constante «, indépendante des entiers n, m et k, telle que la suite [wolz, [Wilx, ..., [um] ne change jamais de valeur à plus de @ reprises. Page 9 sur 11 Épreuve d'option informatique MP 2021 2.3 Trace d'une partie À partir d'une partie W = (wo, w1,..., Wm) EUR (Dry en M coups simples joués sur le tablier de dimension n x 1, nous construisons la trace T° de la partie W en suivant la procédure suivante. Pour plus de clarté, un exemple est présenté en colonne de droite avec la partie en deux coups (wo, w1, w2) où wo -- 110101, w; -- 001101 et w2 -- 010001. ÉTAPE 1 : Nous organisons les mots de W sous forme d'un tableau de n colonnes et m + 1 lignes en positionnant le mot w; dans | "11 01011) 0 7], la ligne 2. Les lignes sont numérotées de bas wo | 1 1 0 1 0 1 en haut. ÉTAPE 2 : Pour tout indice de ligne à compris entre 0 et m -- 1, pour tout indice de colonne j compris entre 1 et n, quand les symboles 1 0 0 lw;]; et [w;,1]; sont égaux, nous effaçons le 0 0 x symbole [w;:.]; inscrit en position (à + 1,3), de sorte qu'il ne reste que le mot wo dans la ligne 0 et les 3 symboles qui ont été modifiés dans les autres lignes. ÉTAPE 3 : Pour tout indice à compris entre 0 et m -- 1, lorsqu'un coup vers la gauche à été joué entre le mot w; et le mot w;,1, nous ajoutons la flèche + en indice des symboles O0; 0; 1, de la ligne ? +1 ; lorsqu'un coup vers la droite 1 1 0 1 0 1 a été joué, nous ajoutons la flèche -- en indice. ÉTAPE 4 : Nous numérotons dans chaque 1 | oO! | où ligne différente de la ligne O0 les trois sym- 0, | om, | 1m boles restants par les marques I, II et III en exposant, en allant de gauche à droite. 1! IT + 0 I IT III III O1, | où | 1m | on ÉTAPE 5 : Nous abaissons l'ensemble des symboles, colonne par colonne, pour les re- grouper dans les alvéoles les plus bas. 1 1 0 1 0 1 ÉTAPE 6 : Si x est un symbole marqué par l'exposant I ou II et est initialement issu de la ligne 2? et si y est son successeur dans le mot (0_,,1)(0,,1) w;, nous adjoignons à x le numéro de ligne 1 1 0 1 0 1 dans lequel y se trouve après abaissement. (14,2)(0%,1) III III Page 10 sur 11 Épreuve d'option informatique MP 2021 La trace de la partie W est la suite des colonnes du tableau obtenue par la procédure ainsi décrite. CT 25 -- Soit T la trace d'une partie. Décrire une construction qui produit une partie de trace T à partir de la trace T". (Il est suggéré de raisonner par récurrence.) [] 26 -- Montrer que l'on peut majorer le nombre de lignes non vides dans la trace d'une partie par une constante indépendante de la dimension n du tablier ou de la longueur de la partie m. En déduire qu'une colonne de la trace d'une partie ne peut prendre qu'un nombre fini de valeurs distinctes. Nous appelons À l'ensemble, fini, des valeurs colonnes que peuvent prendre les colonnes d'une trace de partie. Nous appelons 7 le langage des mots sur À qui représentent la trace d'une partie. [] 27 -- Donner une caractérisation de l'ensemble des facteurs de longueur 2 de mots du langage 7 EUR A. [] 28 -- Montrer qu'il existe un automate local qui reconnaît exactement le langage 7 EUR A. CT 29 -- Montrer qu'il existe un automate fini qui reconnaît le langage R EUR Y* des mots de longueur quelconque de motifs résolubles. Dans la question qui suit, le terme complexité désigne un ordre de grandeur asympto- tique de la complexité en temps et dans le pire des cas. [] 30 -- On s'intéresse au problème de déterminer si un motif sur le tablier unidimensionnel est résoluble ou non. Montrer que l'on peut déduire de l'automate construit à la question 29 un algorithme de complexité optimale pour résoudre ce problème. Les résultats démontrés dans la section 2 ont été établis par B. Ravikumar pour un tablier rectangulaire de dimension n X ñno où 7 est un entier fixé et n est un entier pouvant varier. FIN DE L'ÉPREUVE Page 11 sur 11