Mines Informatique optionnelle MP 2021

Corrigé

(c'est payant, sauf le début) : - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                   

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


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

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Informatique optionnelle MP 2021
Corrigé
Ce corrigé est proposé par Pacôme Luton (ENS Lyon) ; il a été relu par Titouan
Leclercq (ENS Lyon) et Benjamin Monmege (enseignant-chercheur à l'université).

Le sujet est constitué de deux parties indépendantes ayant pour thème la 
résolution explicite du jeu du solitaire quand cela est possible, et la 
reconnaissance d'un
plateau de jeu résoluble.
· La partie I aborde l'implémentation d'un programme ayant pour objet la 
résolution du jeu du solitaire sur le tablier européen.

Les dix premières questions utilisent une manière habile de représenter un 
plateau de jeu avec des entiers, permettant une implémentation efficace du 
programme. Puis de la question 11 à 17, on utilise des parcours de graphe avec
dictionnaires, ce qui permet là aussi une implémentation efficace. Cette partie
demande une bonne maîtrise des listes d'OCaml et une bonne compréhension
des parcours de graphe.
· La partie II s'intéresse à la caractérisation des parties gagnantes d'une 
version
simplifiée du jeu de solitaire, où l'on joue sur un segment. Contrairement à la
première partie, celle-ci est essentiellement théorique. Elle commence par trois
questions relativement simples traitant d'un langage local. On étudie ensuite
une manière efficace de reconnaître les parties gagnantes à l'aide d'automates
locaux. La fin de cette partie est aussi technique que difficile.
Ce sujet aborde des problématiques classiques et importantes en algorithmique de
graphe. Il propose aussi une approche originale pour résoudre un problème 
algorithmique, en construisant pas à pas un automate reconnaissant les parties 
gagnantes.

Indications
Partie 1
3 Énumérer à l'aide d'une fonction auxiliaire récursive les entiers candidats 
et regarder un à un s'ils correspondent à un numéro intérieur.
6 Parcourir récursivement la liste en entrée et ajouter les encoches au motif. 
Pour
cela s'inspirer du petit exemple donné dans l'énoncé.
7 Composer les résultats des questions 3 et 6.
8 Décrire l'écriture en base 2 de m land (m-1) à partir de celle de m.
9 Utiliser la fonction land pour vérifier si pour un motif m, un certain bit 
[m]z est
non nul.
10 Utiliser la question 4, et ne pas oublier de vérifier si la position 
candidate appartient bien au plateau de jeu.
11 Utiliser la liste voisins et remarquer qu'il est facile de transformer la 
grille après
un coup grâce à l'opérateur lxor.
12 Faire un parcours en profondeur dans le graphe des configurations (m, p) où m
est un motif représentant la grille et p le motif ponctuel représentant la 
position
du fichet à déplacer.
13 Utiliser une fonction auxiliaire pour énumérer tous les fichets du motif qui 
peuvent
être déplacés, et récupérer la liste des motifs qu'il est possible d'obtenir en 
déplaçant ce fichet en un coup composé à l'aide de la fonction de la question 
12.
15 Introduire une fonction qui, à un motif, associe la liste de tous les 
nouveaux motifs
accessibles en un coup composé supplémentaire.
16 Énumérer récursivement la liste de tous les motifs qu'il est possible 
d'obtenir en
n étapes.
17 Regarder si l'implémentation de la question 16 respecte bien tous les 
aspects du
parcours décrit à la question 1.
Partie 2
19 Un automate à deux états suffit.
20 Trouver les facteurs de taille 2 possibles et faire un raisonnement par 
l'absurde.
21 Séparer la somme en deux pour faire disparaître les valeurs absolues. 
Utiliser
ensuite la majoration de la somme infinie des i qui est donnée par l'énoncé.
22 Remarquer que le calcul de Vk (wi ) - Vk (wi+1 ) n'est pas si compliqué, 
puis faire
une disjonction de cas.
24 Raisonner par l'absurde et utiliser les questions 21, 22 et 23.
25 Comparer la trace de la partie W = (w0 , w1 , . . . , wm ) avec celle de la 
partie
W0 = (w1 , w2 , . . . , wm ). Donner une procédure pour passer de W à W0 , puis
raisonner par récurrence.
26 Utiliser la question 24.
27 Construire une procédure récursive qui permet de caractériser les facteurs de
longueur 2.
29 Construire un automate dont la suite d'états après la lecture d'un mot x 
permet
d'expliciter la trace d'une partie où le premier mot de la partie est x et le 
dernier
un mot ponctuel.

I. Partie jouée sur le tablier européen
en un minimum de coups
1 Pour déterminer la distance entre deux sommets d'un graphe, il faut faire un
parcours en largeur. La politique de mise en attente des sommets qui caractérise
ce parcours est la politique FIFO (First In First Out). On traite en priorité 
les
sommets découverts les plus tôt lors du parcours. On l'implémente à l'aide 
d'une file.
L'autre politique au programme de CPGE de mise en attente des sommets
est LIFO (Last In First Out), qui correspond au parcours en profondeur, que
l'on implémente avec une pile.
2 Il suffit de vérifier toutes les conditions données dans la définition de 
l'ensemble E.
let numero_interieur z =
let x = z mod 8 and y = z/8 in
x >= 0 && x <= 6 && y >= 0 && y <= 6 && abs (x - 3) + abs (y - 3) <= 4;; 3 La fonction auxiliaire enumerateur permet de parcourir récursivement les entiers de 0 à 52 inclus, et les ajoute à la sortie du programme s'ils appartiennent à E. let numeros_europeens = let rec enumerateur i = match i with | 53 -> []
| i when numero_interieur i -> i::(enumerateur (i+1))
| _ -> enumerateur (i+1)
in enumerateur 0;;
4 Considérons l'encoche située à la position (x, y) avec z = 8y +x le numéro 
associé.
Les encoches voisines, dont on suppose l'existence, ont pour coordonnées (x - 
1, y),
(x + 1, y), (x, y - 1) et (x, y + 1). Elles sont donc représentées par les 
numéros
z - 1, z + 1, z - 8 et z + 8
5 Par définition, le motif qui contient seulement l'encoche du numéro z est 
représenté par l'entier 2z . Ainsi, la fonction doit juste renvoyer 2z , que 
l'on peut obtenir
directement à l'aide de la fonction de décalage lsl rappelée dans l'énoncé.
let numero_vers_ponctuel z = (1 lsl z);;
6 La fonction auxiliaire parcours_liste parcourt récursivement les éléments de
la liste des numéros des encoches, et ajoute leur représentation en tant que 
motif
ponctuel au motif qui sera renvoyé. Si z désigne le numéro d'une encoche à 
ajouter,
l'instruction 2z lor m permet de faire passer le z-ième bit de m à 1.
let numeros_vers_motif l =
let rec parcours_liste l = match l with
| [] -> 0
| t::q -> (numero_vers_ponctuel t) lor (parcours_liste q)
in parcours_liste l;;
Si on supposait que la liste ne contenait pas de doublons, une somme des
puissances de 2 associées aux entiers de la liste conviendrait également. 
L'utilisation du OU logique permet de ne pas s'embêter avec les doublons car 
pour

tout entier z, 2z lor 2z = 2z . À cela s'ajoute le fait que l'énoncé suggérait
l'utilisation du lor pour cette fonction avec la définition de m0 .
7 Il suffit d'appliquer la fonction numeros_vers_motif définie à la question 6 
à la
variable globale numeros_europeens de la question 3.
let motif_europeen = numeros_vers_motif numeros_europeens;;
8

Une manière de comprendre le test effectué dans la fonction est de le tester à
la main sur des exemples de petite taille. Par exemple, en notant f la fonction
qui à m associe m land (m - 1), on a :
f (10110) = 10110 land (10110 - 1) = 10110 land 10101 = 10100
f (01000) = 01000 land (01000 - 1) = 01000 land 00111 = 00000

On peut alors conjecturer que f (m) passe le bit non nul de poids le plus
faible de m à 0. Ce que nous allons à présent formaliser et exploiter.
Soit m  Z. Si m 6 0, par définition m ne peut pas représenter un motif (donc pas
un motif ponctuel). Dans ce cas, le test m > 0 s'assure que la fonction 
est_ponctuel
renvoie false. Considérons à présent m  N . Cet entier admet une unique 
décomposition de la forme
X
m=
2i
iI

avec I une partie finie et non vide de N. Par propriété de N, cette partie 
admet un
plus petit élément, que l'on note i0 . On a alors
X
X
m-1=
2i +
2i
i i0 , [n]i = [m]i  [m - 1]i = 1  1 = 1.
· Si i 
/ I et i > i0 , [n]i = [m]i  [m - 1]I = 0  0 = 0.
X
On en déduit que
m land (m - 1) =
2i
iIr{i0 }

Cette somme est nulle si et seulement si I r {i0 } = . Autrement dit si et 
seulement
si I contient exactement un entier. En conclusion,
La fonction est_ponctuel m renvoie true si m
représente un motif ponctuel et false sinon.
9 Considérons un motif M représenté par l'entier m et un motif ponctuel P 
représenté par l'entier p = 2z . La définition de la représentation des motifs 
par des entiers
nous indique que P  M si et seulement si [m]z = 1. Il suffit alors de tester si 
[m]z