Le jeu du solitaire : théorie des graphes sur le tablier européen et théorie des automates sur le tablier unidimensionnel
Afficher ou masquer la section
Le sujet, composé de 30 questions, s'intéresse à l'analyse et à la programmation du jeu du solitaire. La première section étudie une partie sur le tablier européen classique en un minimum de coups, à l'aide de méthodes de théorie des graphes. La seconde section étudie la reconnaissance des motifs résolubles sur un tablier rectangulaire unidimensionnel, à l'aide de méthodes de théorie des automates.
1Partie 1 : partie jouée sur le tablier européen en un minimum de coupsNumérotation du tablier, manipulation de motifs, coups simples et composés, puis recherche d'une partie de longueur minimale à l'aide d'un dictionnaire.
2Partie 2 : reconnaissance des motifs résolubles sur le tablier unidimensionnelCodage des motifs par des mots, étude des bascules de l'état d'une encoche, construction de la trace d'une partie et automate associé.
Difficile. Le rapport indique que plusieurs questions de la seconde partie, comme les questions 16, 17, 21, 24 ou 26, sont peu traitées ou obtiennent très peu de bonnes réponses, et que les questions 27 à 30 sont très peu abordées.
Ce qu'a observé le jury
5 erreurs relevées
Confusion entre parcours en profondeur et en largeur · Effet de bord supposé sur x :: l · Code confus et oublis de conditions pour le saut d'un fichet
Afficher ou masquer la section
Les candidats ont globalement bien saisi les différences entre le jeu sur tablier européen et sur tablier unidimensionnel, et ont su répondre au maximum de questions en gérant le passage entre les deux parties. Le jury note une baisse des compositions traitant exclusivement la programmation ou exclusivement les démonstrations, mais relève encore l'usage de Python malgré l'interdiction explicite de l'énoncé et une tendance à écrire du code OCaml en style impératif plutôt que fonctionnel.
Les erreurs les plus sanctionnées
1
Confusion entre parcours en profondeur et en largeur1
De nombreux candidats ignorent la distinction entre parcours en profondeur ou en largeur et l'emploi associé d'une pile ou d'une file.
2
Effet de bord supposé sur x :: l3
L'opération x :: l est interprétée à tort comme un effet de bord sur l, alors que ce n'est pas le cas en OCaml.
« L ’opérationx :: l est interprétée comme un effet de bord surl. Ce n’est pas le cas. »
3
Code confus et oublis de conditions pour le saut d'un fichet11
Les copies présentent souvent du code très compliqué et beaucoup de candidats oublient de vérifier certaines conditions pour que le saut soit possible, ou de tester si le fichet reste dans le damier européen.
4
Notion de langage et d'automate local mal maîtrisée20
Une majorité de candidats ne connaissent pas la notion de langage, et la relation avec un automate local semble confuse.
5
Question 16 sur le dictionnaire peu traitée16
La question est peu traitée et semble difficile pour de nombreux candidats ; certains oublient la création du dictionnaire lorsqu'ils choisissent cette option.
« Question peu traitée. Elle semble difficile pour de nombreux candidats. »
Ce qui a été bien réussi
La question 4 est globalement bien traitée.
La question 7 est globalement bien traitée.
La question 14 est en général assez bien traitée par les candidats qui l'ont abordée.
La question 18 est globalement bien traitée.
Conseils du jury
Respecter l'interdiction d'utiliser un autre langage qu'OCaml, explicitement précisée en préambule du sujet.
Utiliser des noms de fonctions auxiliaires significatifs plutôt que des noms génériques comme Aux, Aux1, Aux2.
Mener les preuves d'équivalence dans les deux sens plutôt que par une succession d'équivalences imprécise.
Éviter les expressions comme « c'est évident » ou « il est clair que » lorsque la question exige une démonstration rigoureuse.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
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'é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 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 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 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 [b1; ..; bn] renvoie f(..(f(fab1)b2).).bn ;
map, de type ('a -> 'b) -> 'a list -> 'b list, telle que map f [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 ' 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^(62) et 0 ⩽ k < 62, nous notons [n]_k le k^e bit de poids le plus faible de la représentation binaire de n, ce qui permet d'écrire n = [n]_(61)[n]_(60)⋯[n]_0^–.
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 a et b. 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.
[a]_(61 − b)⋯[a]_1[a]_0 0⋯0_()_(b zéros à droite)^–
a lsr b
Décalage vers la droite
0⋯0_()[a]_(61)⋯[a]_(b + 1)[a]_b
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⋯0011^– et
le calcul de a land b vaut l'entier 2, dont l'écriture sur 62 bits est 0⋯0010^–;
le calcul de a lor b vaut l'entier 7 , dont l'écriture sur 62 bits est 0⋯0111^–;
le calcul de a lxor b vaut l'entier 5 , dont l'écriture sur 62 bits est 0⋯0101^–;
le calcul de a 1 sl b renvoie 48, dont l'écriture sur 62 bits est 0⋯0110000^–;
le calcul de a lsr b renvoie 0 puisque les deux bits non nuls de a sont sortis de la représentation.
L'entier 2^k, avec 0 ⩽ k < 62, 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
{(x, y) ∈ ℕ^2; 0 ⩽ x ⩽ 6, 0 ⩽ y ⩽ 6 et |x − 3| + |y − 3| ⩽ 4}
D'autres tabliers existent tels que le tablier rectangulaire de dimension n × 1, où n ⩾ 1 est un entier,
et dont on peut décrire les coordonnées par
{(x, y) ∈ ℕ^2; 1 ⩽ x ⩽ n et y = 0}
Sur un tablier, toute encoche de coordonnées ( x, y ) possède au plus quatre encoches voisines, à savoir les encoches de coordonnées (x + 1, y), (x − 1, y), (x, y + 1) et (x, y − 1) 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 (x, y) ∈ ℕ^2 dans le tablier européen par l'entier z = 8y + x ∈ ℕ (voir figure 1, page 5). Nous notons l'ensemble des numéros d'encoches du tablier européen par
E = {8y + x; (x, y) ∈ ℕ^2 avec 0 ⩽ x, y ⩽ 6 et |x − 3| + |y − 3| ⩽ 4} ⊆ ℕ.
Indication OCaml : En OCaml, on peut retrouver les coordonnées (x, y) d'une encoche à partir de son numéro z en écrivant z mod 8 pour obtenir l'abscisse x et z/8 pour obtenir l'ordonnée y. 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 z est le numéro d'une encoche du tablier européen E.
Figure 1 - Numérotation des encoches du tablier européen
◻3 - 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. ◻4 - 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 z.
1.2 Motifs
Pour représenter un motif M ⊆ E, nous utilisons un entier naturel m dont nous exploitons une partie des bits de l'écriture binaire comme suit : pour tout numéro d'encoche z ∈ E, nous fixons
[m]_z = {1, si z ∈ M; 0, si z ∉ M ou si z ∉ E
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 mO = (1lsl29) lor (1 lsl 20) lor (1 lsl 18) lor (1 lsl 17);; ◻5 - Écrire une fonction numero_vers_ponctuel (z:int) : ponctuel qui renvoie le motif ponctuel {z} ⊆ E formé d'une seule encoche de numéro z. ◻6 - Écrire une fonction numeros_vers_motif (l:int list) : motif qui renvoie le motif formé des encoches de numéro appartenant à la liste ℓ. ◻7 - 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. ◻8 - Démontrer que la fonction suivante
let est_ponctuel (m:motif) : bool = (m > 0) && ((m land (m − 1)) = 0);;
renvoie true si le motif m est un motif ponctuel et false sinon. ◻9 - É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 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 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 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ù m^′ 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 valeur 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é.
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 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 que mem 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 dm 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. ◻16 - Dans cette question, nous supposons qu'il est possible de passer d'un motif m_i à un motif m_f 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 m_i au motif final m_f. On pourra utiliser un dictionnaire qui associe des motifs au nombre de coups minimal pour les atteindre depuis le motif m_i. ◻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 × 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 Σ = {0, 1} et notons Σ^∗ l'ensemble des mots sur Σ. Pour tout mot w = σ_1…σ_n ∈ Σ^∗, nous notons [w]_k le k^e symbole σ_k de w.
Le mot d'un motif M du tablier rectangulaire de dimension n × 1 est le mot w formé de n symboles de l'alphabet Σ tel que, pour k variant entre 1 et n, le symbole [w]_k vaut 1 si la k^e encoche à partir de la gauche appartient au motif M et vaut 0 sinon. Par exemple, sur ce tablier, le motif ∙∙∙∙ est décrit par le mot 10110 ∈ Σ^∗.
Dans toute cette section, hous ne considérons que des coups simples. Une partie est par conséquent une suite finie W de mots w_0, w_1, …, w_m de même longueur telle que pour tout indice i compris entre 0 et m − 1, le mot w_(i + 1) est obtenu à partir du mot w_i en remplaçant dans le mot w_i 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_m de la partie ne comprend le symbole 1 qu'une seule fois.
L'objectif de cette section est d'étudier le langage R ⊆ Σ^∗ des mots de longueur quelconque de motifs résolubles.
2.1 Mots de motifs ponctuels
Nous notons P ⊆ Σ^∗ 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 langage P.
20 - Le langage P est-il un langage local?
2.2 Bascules de l'état d'une encoche
Soient W = (w_0, w_1, …, w_m) ∈ (Σ^n)^(m + 1) une partie en m coups simples joués sur le tablier de dimension n × 1 et k 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 [w_0]_k, [w_1]_k, …, [w_m]_k ne change jamais de valeur à plus de α reprises.
Nous notons φ = (√5 − 1)/2 l'une des racines du polynôme X^2 + X − 1. On pourra utiliser sans preuve l'inégalité ∑_(j = 1)^(+ ∞)φ^j ⩽ 2. Pour tout mot w ∈ Σ^n de longueur n, nous introduisons le variant V_k(w) par la somme
V_k(w) = ∑_(j = 1)^n φ^(|j − k|)[w]_j ∈ ℝ
◻21 - Montrer qu'il existe un réel S, indépendant des entiers n et k, tel que, pour tout mot w ∈ Σ^n, on ait l'inégalité V_k(w) ⩽ S. ◻22 - Montrer que la suite des (m + 1) variants V_k(w_0), V_k(w_1), …, V_k(w_m) est une suite de réels décroissante. ◻23 - Montrer que si, pour un indice i compris entre 0 et m − 1, le symbole [w_i]_k vaut 1 et le symbole [w_(i + 1)]_k vaut 0 , alors on a V_k(w_(i + 1)) ⩽ V_k(w_i) − 1. ◻24 - En déduire qu'il existe une constante α, indépendante des entiers n, m et k, telle que la suite [w_0]_k, [w_1]_k, …, [w_m]_k ne change jamais de valeur à plus de α reprises.
2.3 Trace d'une partie
À partir d'une partie W = (w_0, w_1, …, w_m) ∈ (Σ^n)^(m + 1) en m coups simples joués sur le tablier de dimension n × 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 ( w_0, w_1, w_2 ) où w_0 = 110101, w_1 = 001101 et w_2 = 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_i dans la ligne i. Les lignes sont numérotées de bas en haut.
w_2
0
1
0
0
0
1
w_1
0
0
1
1
0
1
w_0
1
1
0
1
0
1
Étape 2 : Pour tout indice de ligne i compris entre 0 et m − 1, pour tout indice de colonne j compris entre 1 et n, quand les symboles [w_i]_j et [w_(i + 1)]_j sont égaux, nous effaçons le symbole [w_(i + 1)]_j inscrit en position ( i + 1, j ), de sorte qu'il ne reste que le mot w_0 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 i compris entre 0 et m − 1, lorsqu'un coup vers la gauche a été joué entre le mot w_i et le mot w_(i + 1), nous ajoutons la flèche ← en indice des symboles de la ligne i + 1; lorsqu'un coup vers la droite a été joué, nous ajoutons la flèche → en indice.
1_←
0_←
0_←
0_→
0_→
1_→
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_←^I
0_←^(II)
0_←^(III)
0_→^I
0_→^(II)
1_→^(III)
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_←^I 0_←^(II)
0_→^I
0_→^(II)
1^(III)
0_←^(III)
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 i et si y est son successeur dans le mot w_i, nous adjoignons à x le numéro de ligne dans lequel y se trouve après abaissement.
(1_←^I, 2)
(0_←^(II), 1)
(0_→^I, 1)
(0_→^(II), 1)
1_→^(III)
0_←^(III)
1
1
0
1
0
1
La trace de la partie W est la suite des colonnes du tableau obtenue par la procédure ainsi décrite. ◻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 T 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 T ⊆ Δ^∗. ◻28 - Montrer qu'il existe un automate local qui reconnaît exactement le langage T ⊆ Δ^∗. ◻29 - Montrer qu'il existe un automate fini qui reconnaît le langage R ⊆ Σ^∗ 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. ◻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 × n_0 où n_0 est un entier fixé et n est un entier pouvant varier.
Fin de l'épreuve
Questions fréquentes
4 questions
Sur quels chapitres porte le sujet d'informatique Mines-Ponts MP 2021 ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet d'informatique Mines-Ponts MP 2021 ?
+
Il porte sur le jeu du solitaire, étudié avec des méthodes de théorie des graphes sur le tablier européen puis des méthodes de théorie des automates sur un tablier unidimensionnel.
Le sujet d'informatique Mines-Ponts MP 2021 doit-il être traité en OCaml ?
+
Oui, l'usage d'un autre langage, en particulier Python, est explicitement proscrit en préambule du sujet, bien que le rapport note que certains candidats ne respectent pas cette consigne.
Quelle est la question la plus difficile du sujet informatique Mines MP 2021 sur le solitaire ?
+
Le rapport indique que les questions 27 à 30, en fin de seconde partie sur les automates, sont très peu abordées par les candidats.
Faut-il privilégier la programmation fonctionnelle sur ce sujet Mines MP informatique 2021 ?
+
Le jury note une tendance marquée à écrire du code en style impératif et encourage les candidats à maîtriser aussi bien le style fonctionnel que le style impératif.
Pas de description pour le moment
Commentaires• Mines Option Informatique MP 2021
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Structures de données… (+2)CCINP Informatique MPI 2024CCINP · 2024Sujet seul
Même année, X-ENSX ENS Option Informatique MP 2021X-ENS · 2021Corrigé
Même chapitre : Structures de données… (+1)Centrale Informatique MPI 2024Centrale · 2024Corrigé.jpg)
.jpg)
.jpg)
.jpg)
