Durée de l'épreuve : 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'é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.
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 ) 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 programmation 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 l renvoie la liste des éléments de la liste tels que le prédicat 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 [b1; ..; bn] renvoie .bn ;
map, de type ('a -> 'b) -> 'a list -> 'b list, telle que map [a1; ..; an] renvoie la liste [f a1; ..; f an].
Opérations sur les couples : On rappelle que
la fonction fst, de type 'a * 'b -> 'a, renvoie le premier terme d'un couple;
la fonction snd, de type ' ' 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 et avec et , nous notons le bit de poids le plus faible de la représentation binaire de , ce qui permet d'écrire .
Le tableau ci-dessous rappelle le résultat de quelques-uns des opérateurs logiques de OCaml qui agissent bit à bit sur deux entiers naturels et . Tous ces opérateurs renvoient un élément de type int. Dans ce tableau, les symboles 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
a lor b
Ou logique bit à bit
a lxor b
Xor logique bit à bit
lnot a
Non logique bit à bit
a 1 sl b
Décalage vers la gauche
a lsr b
Décalage vers la droite
zéros à gauche
Par exemple, lorsque et , les écritures sur 62 bits de et sont et et
le calcul de a land b vaut l'entier 2, dont l'écriture sur 62 bits est ;
le calcul de a lor b vaut l'entier 7 , dont l'écriture sur 62 bits est ;
le calcul de a lxor b vaut l'entier 5 , dont l'écriture sur 62 bits est ;
le calcul de a 1 sl b renvoie 48, dont l'écriture sur 62 bits est ;
le calcul de a lsr b renvoie 0 puisque les deux bits non nuls de sont sortis de la représentation.
L'entier , avec , peut commodément se définir en OCaml par 1 lsl k .
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
dont on peut décrire les coordonnées par
D'autres tabliers existent tels que le tablier rectangulaire de dimension , où est un entier,
et dont on peut décrire les coordonnées par
Sur un tablier, toute encoche de coordonnées ( ) possède au plus quatre encoches voisines, à savoir les encoches de coordonnées et si elles existent.
Nous appellons motif tout sous-ensemble d'encoches dans le tablier. Nous disons qu'un motif est ponctuel s'il est de cardinal 1.
En début de jeu, des fichets (ou des billes) viennent se loger dans les encoches d'un motif initial. En cours de jeu, un coup simple consiste à déplacer l'un des fichets en sautant par-dessus l'une des encoches voisines pour atteindre l'encoche immédiatement après. Il peut être joué à condition que l'encoche voisine en question soit occupée et que le fichet déplacé retombe dans une encoche inoccupée. À l'issue d'un coup simple, le fichet planté dans l'encoche au-dessus de laquelle a eu lieu le saut est retiré. Par exemple,
peut devenir
En cours de jeu, un coup composé consiste à jouer zéro, un ou plusieurs coups simples en déplaçant le même fichet. Par exemple,
peut devenir
Une suite de motifs obtenus en jouant une suite de coups s'appelle une partie. L'objectif de la joueuse ou du joueur est de transformer un motif en un autre motif par une suite de coups.
1 Partie jouée sur le tablier européen en un minimum de coups
Dans toute la section 1 du sujet, une joueuse joue sur le tablier européen. Elle souhaite transformer un motif initial en un motif final par un minimum de coups composés.
1 - À titre préliminaire, nommer le type de parcours de graphe le plus approprié pour déterminer un chemin entre deux sommets qui minimise le nombre d'arcs traversés. Quelle politique de mise en attente de sommets caractérise ce parcours?
1.1 Numérotation du tablier
Nous numérotons l'encoche de coordonnées dans le tablier européen par l'entier (voir figure 1, page 5). Nous notons l'ensemble des numéros d'encoches du tablier européen par
Indication OCaml : En OCaml, on peut retrouver les coordonnées d'une encoche à partir de son numéro en écrivant z mod 8 pour obtenir l'abscisse et pour obtenir l'ordonnée . On peut calculer la valeur absolue d'un entier avec abs.
2 - Écrire une fonction numero_interieur (z:int) : bool, qui teste si un entier naturel est le numéro d'une encoche du tablier européen .
Figure 1 - Numérotation des encoches du tablier européen
- En énumérant les entiers naturels inférieurs à 52 et à l'aide de la fonction numero_interieur introduite à la question 2 , définir une constante globale numeros_europeens, de type int list, égale à la liste des numéros d'encoches du tablier européen. - En supposant qu'elles existent dans le tablier, donner par une expression mathématique le numéro des quatre encoches voisines de l'encoche de numéro .
1.2 Motifs
Pour représenter un motif , nous utilisons un entier naturel dont nous exploitons une partie des bits de l'écriture binaire comme suit : pour tout numéro d'encoche , nous fixons
Lorsqu'un motif est ponctuel, c'est-à-dire qu'il ne contient qu'une seule encoche, sa représentation est simplement une puissance de 2 .
Par exemple, le motif à quatre encoches suivant
se représente par le nombre entier
Indication OCaml : Pour représenter les motifs et les motifs ponctuels, nous définissons les types motif et ponctuel par la déclaration suivante :
type motif = int;;
type ponctuel = motif;;
L'exemple ci-dessus se déclare à l'aide des opérateurs logiques en OCaml par
let lor (1 lsl 20) lor (1 lsl 18) lor (1 lsl 17);; - Écrire une fonction numero_vers_ponctuel (z:int) : ponctuel qui renvoie le motif ponctuel formé d'une seule encoche de numéro . - Écrire une fonction numeros_vers_motif (l:int list) : motif qui renvoie le motif formé des encoches de numéro appartenant à la liste . - En s'appuyant sur la constante numeros_europeens introduite à la question 3, définir une constante globale motif_europeen, de type motif, égale au motif formé de toutes les encoches du tablier européen. - Démontrer que la fonction suivante
let est_ponctuel (m:motif) : bool = && land ;;
renvoie true si le motif est un motif ponctuel et false sinon. - Écrire, à l'aide des opérateurs logiques sur les entiers, une fonction inclus (m:motif) (p:ponctuel) : bool qui renvoie true si le motif ponctuel est inclus dans le motif ou false dans le cas opposé. Donner une preuve mathématique du résultat. - É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 . Si le motif ponctuel 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 respectivement 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_b];;.
1.3 Coups simples et composés
11 - Écrire une fonction coup_simple ((m, p) : motif * ponctuel) : (motif * ponctuel) list qui prend en entrée un motif quelconque et un motif ponctuel contenu dans et qui construit la liste des couples ( ) où est un motif obtenu à partir de à la suite du déplacement par un coup simple du fichet initialement placé dans et où est le motif ponctuel repérant le même fichet après son déplacement. - Écrire une fonction coup_compose ((m, p) : motif * ponctuel) : (motif * ponctuel) list qui prend en entrée un motif quelconque et un motif ponctuel contenu dans et qui construit la liste des couples ( ) où est un motif obtenu à partir de à la suite du déplacement par un coup composé du fichet initialement placé dans et où est le motif ponctuel repérant le même fichet après son déplacement. - Écrire une fonction mouvements (m:motif) : motif list dont la valeur de retour est la liste de tous les motifs que l'on peut obtenir en jouant un coup composé depuis le motif , n'importe quel fichet pouvant être déplacé.
1.4 Partie de longueur minimale
Indication OCaml : 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 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 une association entre la clé et l'entier (si une association de clé existe déjà, elle est remplacée);
la fonction mem, de type dico -> motif -> bool, telle que mem m renvoie le booléen true si la clé est membre du dictionnaire ou false sinon.
la fonction find, de type dico -> motif -> int, telle que find renvoie la valeur associée à la clé si la clé est membre du dictionnaire ou une erreur sinon. - Écrire une fonction add_and_mem (d:dico) (s:int) (m:motif) : bool qui ajoute l'association entre le motif et l'entier dans le dictionnaire si le motif est initialement absent du dictionnaire . La valeur de retour de la fonction est true si le dictionnaire a été modifié et false sinon. - Écrire une fonction strate (d:dico) (s:int) (l:motif list) : motif list qui, pour tout motif que l'on peut obtenir après un coup composé à partir d'un motif de la liste , ajoute l'association entre le motif et l'entier au dictionnaire si le motif n'est pas présent dans le dictionnaire . La valeur de retour de la fonction est la liste des motifs que la fonction ajoute. - Dans cette question, nous supposons qu'il est possible de passer d'un motif à un motif par une suite de coups. Écrire une fonction partie_minimale (mi:motif) (mf:motif) : int qui calcule le nombre minimal de coups composés à jouer pour passer du motif initial au motif final . On pourra utiliser un dictionnaire qui associe des motifs au nombre de coups minimal pour les atteindre depuis le motif . - 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 , où 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 et notons l'ensemble des mots sur . Pour tout mot , nous notons le symbole de .
Le mot d'un motif du tablier rectangulaire de dimension est le mot formé de symboles de l'alphabet tel que, pour variant entre 1 et , le symbole vaut 1 si la encoche à partir de la gauche appartient au motif et vaut 0 sinon. Par exemple, sur ce tablier, le motif est décrit par le mot .
Dans toute cette section, hous ne considérons que des coups simples. Une partie est par conséquent une suite finie de mots de même longueur telle que pour tout indice compris entre 0 et , le mot est obtenu à partir du mot en remplaçant dans le mot 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 de la partie ne comprend le symbole 1 qu'une seule fois.
L'objectif de cette section est d'étudier le langage des mots de longueur quelconque de motifs résolubles.
2.1 Mots de motifs ponctuels
Nous notons le langage des mots de longueur quelconque de motifs ponctuels. - Donner, sans justification, une expression rationnelle qui décrit le langage .
19 - Dessiner, sans justification, un automate fini qui reconnaît le langage .
20 - Le langage est-il un langage local?
2.2 Bascules de l'état d'une encoche
Soient une partie en coups simples joués sur le tablier de dimension et un entier compris entre 1 et . Dans cette sous-section, nous souhaitons démontrer qu'il existe une constante indépendante des entiers ou telle la suite des symboles ne change jamais de valeur à plus de reprises.
Nous notons l'une des racines du polynôme . On pourra utiliser sans preuve l'inégalité . Pour tout mot de longueur , nous introduisons le variant par la somme
- Montrer qu'il existe un réel , indépendant des entiers et , tel que, pour tout mot , on ait l'inégalité . - Montrer que la suite des variants est une suite de réels décroissante. - Montrer que si, pour un indice compris entre 0 et , le symbole vaut 1 et le symbole vaut 0 , alors on a . - En déduire qu'il existe une constante , indépendante des entiers , et , telle que la suite ne change jamais de valeur à plus de reprises.
2.3 Trace d'une partie
À partir d'une partie en coups simples joués sur le tablier de dimension , nous construisons la trace de la partie 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 ( ) où et .
Étape 1 : Nous organisons les mots de sous forme d'un tableau de colonnes et lignes en positionnant le mot dans la ligne . Les lignes sont numérotées de bas en haut.
0
1
0
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
Étape 2 : Pour tout indice de ligne compris entre 0 et , pour tout indice de colonne compris entre 1 et , quand les symboles et sont égaux, nous effaçons le symbole inscrit en position ( ), de sorte qu'il ne reste que le mot dans la ligne 0 et les 3 symboles qui ont été modifiés dans les autres lignes.
1
0
0
0
0
1
Étape 3 : Pour tout indice compris entre 0 et , lorsqu'un coup vers la gauche a été joué entre le mot et le mot , nous ajoutons la flèche en indice des symboles de la ligne ; lorsqu'un coup vers la droite a été joué, nous ajoutons la flèche en indice.
1
1
0
1
0
1
Étape 4 : Nous numérotons dans chaque ligne différente de la ligne 0 les trois symboles restants par les marques I, II et III en exposant, en allant de gauche à droite.
1
1
0
1
0
1
Étape 5 : Nous abaissons l'ensemble des symboles, colonne par colonne, pour les regrouper dans les alvéoles les plus bas.
1
1
0
1
0
1
Étape 6 : Si est un symbole marqué par l'exposant I ou II et est initialement issu de la ligne et si est son successeur dans le mot , nous adjoignons à le numéro de ligne dans lequel se trouve après abaissement.
1
1
0
1
0
1
La trace de la partie est la suite des colonnes du tableau obtenue par la procédure ainsi décrite. - Soit la trace d'une partie. Décrire une construction qui produit une partie de trace à partir de la trace . (Il est suggéré de raisonner par récurrence.) - 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 du tablier ou de la longueur de la partie . 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 le langage des mots sur qui représentent la trace d'une partie. - Donner une caractérisation de l'ensemble des facteurs de longueur 2 de mots du langage . - Montrer qu'il existe un automate local qui reconnaît exactement le langage . - Montrer qu'il existe un automate fini qui reconnaît le langage des mots de longueur quelconque de motifs résolubles.
Dans la question qui suit, le terme complexité désigne un ordre de grandeur asymptotique de la complexité en temps et dans le pire des cas. - 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 où est un entier fixé et est un entier pouvant varier.
Fin de l'épreuve
Mines Option Informatique MP 2021 - Version Web LaTeX | WikiPrépa | WikiPrépa
