Durée de l'épreuve : heures
L'usage de la calculatrice ou 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 27 questions. Après cette section de préliminaires, qui présente le jeu du hanjie, le problème est divisé en trois sections qui peuvent être traitées séparément, à condition d'avoir lu les définitions introduites jusqu'à la question traitée. Dans la première section (page 2), nous résolvons le jeu par des raisonnements logiques. Dans la deuxième section (page 3), nous modélisons le jeu et le résolvons par une stratégie algorithmique de retour sur trace. Dans la troisième section (page 6), nous appliquons une méthode de parcours de graphe en théorie des automates pour accélérer la résolution du jeu.
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 ) et du point de vue informatique pour celle en romain avec espacement fixe (par exemple n).
Des rappels de logique et des extraits du manuel de documentation de OCaml sont reproduits en annexe. Ces derniers portent sur le module Array et le module Hashtbl.
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, en reprenant l'en-tête de fonction fourni par le sujet, sans s'obliger à recopier la déclaration des types. Quand l'énoncé demande de coder une fonction, sauf demande explicite de l'énoncé, il n'est pas nécessaire de justifier que celle-ci est correcte ou de vérifier que des préconditions sont satisfaites.
Le barème tient compte de la clarté des programmes : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.
Description du jeu du hanjie
Le hanjie est un jeu de réflexion à l'intersection de l'art des pixels et de la tomographie discrète, technique d'imagerie courante en médecine, en géophysique ou en science des matériaux entre autres domaines.
Il consiste à retrouver une image par le noircissement de certaines cases d'une grille rectangulaire sur la base d'indications laissées sur les côtés de la grille. Pour chaque rangée, qu'elle soit horizontale ou verticale, le joueur dispose d'une suite d'entiers non nuls , etc. qui indiquent que la rangée contient une série de cases noires consécutives, suivie plus loin d'une série de cases noires consécutives, et ainsi de suite. Un nombre quelconque de cases blanches peut se trouver en tête ou en queue de rangée; au moins une case blanche sépare deux séries de cases noires.
Voici un exemple, que nous résolvons à la main. Une grille vide est fournie ci-contre. Elle est de dimension . Nous marquons les cases par des symboles «?» tant que nous ignorons leur couleur.
Nous comptons les rangées à partir de 0 , de gauche à droite pour les colonnes et du haut vers le bas pour les lignes.
La colonne 0 et la colonne 5 sont de longueur 5 . Or l'indication est [5] dans les deux cas. Elles doivent donc chacune contenir 5 blocs noirs consécutifs. Nous les noircissons en totalité.
Dans la ligne 0 , il n'y a qu'une seule manière de placer un bloc de 4 cases noires puis 2 cases noires. De même, dans la ligne 2, il n'y a qu'une seule manière de positionner le bloc de longueur 2 : il doit se trouver au milieu entre les deux blocs déjà isolés. Dans la ligne 3, nous avons déjà placé deux cases noires : les autres sont donc toutes blanches. Enfin, dans la ligne 4, il n'y a plus qu'une seule manière de placer un bloc de 6 cases noires.
Enfin, en reprenant les indications des colonnes, nous voyons que dans les colonnes 1,2 et 4 , la dernière case inconnue est blanche. Dans la colonne 3 et 6 en revanche, nous devons noircir la dernière case inconnue. Nous avons obtenu une solution de notre hanjie. Elle est unique.
1. Hanjie et calcul de vérité
Dans cette section, nous raisonnons avec la logique propositionnelle pour déterminer la couleur de certaines cases. Nous nous concentrons sur le hanjie défini par
1 - Établir, par raisonnement en langue française, que la solution du hanjie est unique.
Nous introduisons six variables booléennes, nommées , et correspondant aux cases ci-contre. Nous associons la valeur de vérité V (vrai) à la couleur noire et (faux) à la couleur blanche.
.
Soit le prédicat : «l'indication de la ligne zéro du hanjie est satisfaite». - Dresser la table de vérité du prédicat portant sur les variables . En déduire une formule de logique sous forme normale conjonctive qui décrit le prédicat .
Soit le prédicat : «l'indication de la colonne du milieu du hanjie est satisfaite». - Dresser la table de vérité du prédicat portant sur les variables . En déduire une formule de logique sous forme normale conjonctive qui décrit le prédicat .
Les règles d'inférence de la déduction naturelle sont rappelées dans l'annexe B . - Construire un arbre de preuve qui démontre le séquent à partir des règles d'inférence de la déduction naturelle. - Construire de même un arbre de preuve qui démontre le séquent .
Nous notons la formule de logique obtenue à partir de en remplaçant la variable par et la variable par . - Démontrer qu'il n'existe pas d'arbre de preuve qui démontre la formule .
2. Cadre de résolution systématique du hanjie
2.1. Le hanjie
Nous fixons un alphabet et notons l'alphabet complété . Les symboles N, B et I désignent respectivement les couleurs Noir, Blanc et Inconnu. Nous déclarons en OCaml :
type couleur - Écrire une fonction OCaml est_connu (c:couleur) : bool dont la valeur de retour est le booléen V (vrai) si et le booléen F (faux) si égale la couleur I .
Pour l'ensemble du sujet, nous fixons deux entiers naturels non nuls et qui désignent respectivement un nombre de lignes et un nombre de colonnes.
Définition : Une présolution d'un hanjie est un tableau de dimension à valeurs dans l'ensemble .
Les figures de l'introduction (en page 2) sont des exemples de présolutions.
Indication OCaml : Nous déclarons des constantes globales, le type et le constructeur suivants :
let $m=5$
let $\mathrm{n}=7$
type presolution = couleur array array
let presolution_init () : presolution $=$ (* cree une presolution *)
Array.make_matrix m n I (* toute egale a $I *$ )
Lorsqu'un tableau est de dimension , nous numérotons ses cases ligne après ligne avec les entiers compris entre 0 et . La case en ligne et colonne a pour numéro . Nous notons alors la valeur de en position .
Dans notre exemple, nous aurions les numéros :
- Écrire en langage OCaml un accesseur get (p:presolution) (z:int) : couleur dont la valeur de retour est la couleur . - Écrire en langage OCaml un transformateur set (p:presolution) (z:int) (c:couleur) : presolution dont la valeur de retour est une copie profonde de avec , c'est-à-dire une copie n'ayant aucun lien avec la présolution initiale.
Dans tout le sujet, on s'astreint à manipuler le type presolution exclusivement en employant les fonctions presolution_init, set et get. De la sorte, on pourra considérer que le type presolution est immuable.
10 - Définir le terme immuable et citer un avantage à utiliser des variables immuables.
La ligne d'un tableau, avec , désigne l'ensemble des positions de numéro , (lire numéros au total). La colonne , avec , désigne l'ensemble des positions de numéro (lire numéros au total). Nous utilisons le terme rangée pour parler indifféremment d'une ligne ou d'une colonne.
Définition : Nous disons qu'une rangée d'une présolution est complète si elle est à valeurs dans . - Écrire une fonction OCaml est_complete_lig (p:presolution) (x:int) : bool qui teste si la ligne de la présolution est complète.
Nous supposons écrite de même une fonction est_complete_col (p:presolution) (y:int) : bool, qui teste si la colonne de la présolution est complète.
Définition : Si une rangée est complète, nous appelons trace la suite des longueurs des sous-suites maximales de termes consécutifs égaux à Noir. Par exemple, la trace de la rangée
est . - Écrire une fonction OCaml trace_lig (p:presolution) (x:int) : int list dont la valeur de retour est la trace de la ligne de la présolution .
Nous supposons écrite de la même manière une fonction trace_col (p:presolution) ( int : int list, dont la valeur de retour est la trace de la colonne de la présolution .
Définition : Le terme indication désigne toute suite finie d'entiers naturels non nuls. Nous appelons hanjie de dimension la donnée d'un tableau d'indications ind , de longueur , et d'un tableau d'indications ind , de longueur .
Indication OCaml : Nous déclarons :
type hanjie = { ind_lig : int list array;
ind_col : int list array }
Définition : Une solution d'un hanjie ind , ind de dimension est un tableau de même dimension et à valeurs dans l'ensemble tel que le tableau des traces des lignes de égale ind et le tableau des traces des colonnes de égale ind .
Par exemple, le hanjie étudié en introduction et déclaré par :
- Écrire une fonction OCaml est_admissible (h:hanjie) (p:presolution) : bool dont la valeur de retour est le booléen V (vrai) si et seulement si, pour toute rangée complète de , la trace égale l'indication du hanjie. Il n'est pas nécessaire de contrôler que la présolution et le hanjie ont même dimension.
2.2. Recherche de solutions
Définition : Nous disons qu'une présolution étend une présolution , si pour tout numéro avec , les couleurs et sont égales. Par exemple, la présolution \begin{tabular}{|l|l|l|l|l|}
\hline B & N & I & N & B
étend
\hline B & I & I & N & I
\end{tabular} puisque deux cases sont passées de la couleur I à une couleur connue N ou B et les autres sont restées inchangées.
Indication OCaml : Le type paramétré 'a option permet de distinguer l'absence d'une valeur définie, avec le constructeur None, de la présence d'une valeur de type 'a, avec la construction Some v. Il est défini par la déclaration :
type 'a option = None | Some of 'a
14 - Écrire une fonction OCaml etend_trivial (h:hanjie) (p:presolution) (z:int) (c:couleur) : presolution option qui, si la copie de avec est une extension de et est admissible au sens de la question 13, renvoie Some p' et sinon renvoie None.
Plus généralement, nous appelons extenseur toute fonction OCaml etend (h:hanjie) (p:presolution) (z:int) (c:couleur) : presolution option ainsi spécifiée: Précondition : Le numéro est valide . La couleur appartient à . Postcondition : Si la valeur de retour vaut Some , alors
(i) est une extension admissible de avec
(ii) et toute présolution complète qui satisfait (i) est une extension de .
Sinon, si la valeur de retour est None, alors il n'existe pas de présolution complète vérifiant (i).
Nous définissons le type
type extenseur = hanjie -> presolution ->
int -> couleur -> presolution option
Nous souhaitons implémenter une recherche de solutions par une stratégie de retour sur trace dans laquelle les cases d'une présolution sont considérées par numéro croissant. - Compléter le code suivant afin que, si est une présolution dont au moins les premières cases appartiennent à , alors explore p z renvoie si possible une solution qui étend à partir du numéro à l'aide d'itérations sur l'extenseur ext et sinon renvoie la valeur None:
let resout (h:hanjie) (ext:extenseur) : presolution option =
let p0 = presolution_init () in
let rec explore (p:presolution) (z:int) : presolution option =
(* A COMPLETER *)
in
explore p0 0
3. Résolution autonome de lignes et extenseur
La stratégie d'extension de la question 14 est très naïve. Elle ignore les déductions intermédaires qui pourraient être faites grâce à une seule indication à partir d'une rangée partiellement complétée.
Soit le mot formé des inscriptions dans une rangée dont l'indication est avec . Nous notons l'ensemble des mots de de trace qui étendent . Lorsque l'ensemble n'est pas vide, nous posons, pour tout indice compris entre 0 et , l'ensemble des couleurs
Enfin nous posons, pour tout indice compris entre 0 et ,
Définition : Nous appelons plus grande extension commune du mot par rapport à l'indication le mot , lorsqu'il est défini.
Par exemple, si nous rencontrons la ligne
I
I
I
I
I
N
I avec l'indication [1,2,1],
N
B
N
I
B
B
N
B
La plus grande extension commune est dans ce cas
- Dans cette question uniquement, nous supposons que est de la forme , où est un entier naturel non nul, que l'indication est égale à avec occurrences de 1 et que vaut . Compter le nombre de mots du langage .
Nous notons le langage des mots de de trace quelconque. Nous supposons toujours que l'on a .
17 - Proposer une expression régulière qui dénote le langage . Aucune justification n'est attendue. - Dessiner un automate fini déterministe incomplet à états qui reconnaît le langage . Aucune justification n'est attendue.
19 - Dire combien d'états l'automate de Glushkov qui dérive de l'expression régulière de la question 17 possède et si cet automate coïncide avec celui dessiné à la question 18 .
Dans ce qui suit, nous nous intéressons à des automates finis déterministes incomplets qui ne possèdent qu'un seul état final et dont l'alphabet est toujours . Nous numérotons systématiquement les états de sorte que l'état initial soit 0 et l'unique état final soit , où est le nombre total d'états. Le terme transition désigne un triplet ( ) où et sont des états (avec ) et est une couleur (avec ). Nous représentons la fonction de transition par un tableau de longueur ; la case du tableau contient un dictionnaire qui, quand il existe une transition ( ), associe la couleur à l'état . Nous déclarons :
type automate = { r : int;
transitions : (couleur, int) Hashtbl.t array}
Définition : Le déploiement d'un automate ayant états par un mot de longueur est un nouvel automate, noté , qui possède états. Pour toute transition ( ) dans l'automate et pour tout indice compris entre 0 et ,
pour et ou encore pour , il y a dans l'automate une transition . - Dans cette question uniquement, on considère l'exemple avec et où est l'automate défini par
Dessiner le déploiement . Marquer les états accessibles. Marquer les états coaccessibles, c'est-à-dire les états à partir desquels il existe un chemin vers l'état final. Soient un automate et un mot. Écrire une fonction OCaml accessible (a:automate) (w:couleur array) : bool array dont la valeur de retour est un tableau de booléens tels que est vrai si et seulement si l'état de est accessible.
22 - Calculer la complexité en temps de la fonction accessible définie à la question 21.
23 - Soient un automate à états et un mot de longueur . Écrire une fonction coaccessible (a:automate) (w:couleur array) : bool array dont la valeur de retour est un tableau de booléens tels que est vrai si et seulement si l'état de est co-accessible.
Définition : Soient un automate à états et un mot de longueur . Nous supposons qu'il existe un mot de longueur reconnu par l'automate . Nous rappelons que l'automate émondé de est la copie de l'automate duquel ont été retirées toutes les transitions depuis ou vers des états qui ne sont pas à la fois accessibles et co-accessibles (nous ne chassons pas les états inutiles et conservons la numérotation des états). Nous notons l'ensemble des transitions restantes dans l'automate émondé. Nous notons, pour tout indice compris entre 0 et , l'ensemble des étiquettes
Nous posons, pour tout entier compris entre 0 et ,
Nous appelons mot projeté du déploiement le mot . - Avec les notations du paragraphe qui précède et lorsque l'automate est l'automate dessiné à la question 18, vérifier que le mot projeté est la plus grande extension commune du mot par rapport à l'indication (cf. définition p. 7). - Écrire une fonction projete (a:automate) (w:couleur array) : couleur array dont la valeur de retour est le mot projeté du déploiement .
Nous rappelons la formule de Stirling :
- Comparer la complexité en temps de la fonction projete (question 25) avec un calcul direct de la plus grande extension commune par énumération de l'ensemble . Argumenter en s'appuyant sur la question 16.
Nous nous donnons une fonction OCaml pgec_lig (h:hanjie) (p:presolution) (x:int) : presolution option, et respectivement pgec_col (h:hanjie) (p:presolution) (y:int) : presolution option, qui étend la ligne , respectivement la colonne , par la plus grande extension commune à l'image de la question 25 ou bien renvoie None si la plus grande extension commune n'est pas définie. - Écrire un extenseur etend_nontrivial (h:hanjie) (p:presolution) (z:int) (c:couleur) : presolution option qui modifie la couleur de au numéro et applique les fonctions pgec_lig et pgec_col aussi longtemps que cela permet de faire progresser la présolution. Il est demandé de détailler la stratégie de l'extenseur avant d'en fournir le code.
A. Annexe : aide à la programmation en OCaml
Opérations sur les tableaux : Le module Array offre les fonctions suivantes :
length : 'a array -> int
Return the length (number of elements) of the given array.
make : int -> 'a -> 'a array
Array. make n x returns a fresh array of length , initialized with . All the elements of this new array are initially physically equal to (in the sense of the predicate). Consequently, if is mutable, it is shared among all elements of the array, and modifying through one of the array entries will modify all other entries at the same time.
make_matrix : int -> int -> 'a -> 'a array array
Array.make_matrix dimx dimy e returns a two-dimensional array (an array of arrays) with first dimension and second dimension dimy. All the elements of this new matrix are initially physically equal to . The element of a matrix is accessed with the notation .
init : int -> (int -> 'a) -> 'a array
Array. init n f returns a fresh array of length , with element number initialized to the result of . In other terms, init n f tabulates the results of applied to the integers 0 to .
copy : 'a array -> 'a array
Array. copy a returns a copy of , that is, a fresh array containing the same elements as .
mem : 'a -> 'a array -> bool
mem a is true if and only if is structurally equal to an element of (i.e. there is an in such that compare a ).
for_all : ('a -> bool) -> 'a array -> bool
Array.for_all f [|a1; ...; an |] checks if all elements of the array satisfy the predicate . That is, it returns (f a1) && (f a2) && ... && (f an).
exists : ('a -> bool) -> 'a array -> bool
Array.exists f [|a1; ...; an |] checks if at least one element of the array satisfies the predicate . That is, it returns ( a1) || (f a2) || ... || (f an).
map : ('a -> 'b) -> 'a array -> 'b array
Array.map f a applies function to all the elements of , and builds an array with the results returned
by a. (0); f a.(1); ...; f a.(length a - 1) |].
iter : ('a -> unit) -> 'a array -> unit
Array.iter a applies function in turn to all the elements of . It is equivalent to
a.(1); ...; f a. (length a - 1); ().
Hashtbl. create n creates a new, empty hash table, with initial size . For best results, should be on the order of the expected number of elements that will be in the table. The table grows as needed, so is just an initial guess.
add : ('a, 'b) t -> 'a -> 'b -> unit
Hashtbl.add tbl key data adds a binding of key to data in table tbl.
remove : ('a, 'b) 'a -> unit
Hashtbl.remove tbl x removes the current binding of in , restoring the previous binding if it exists. It does nothing if is not bound in .
mem : ('a, 'b) 'a -> bool
Hashtbl.mem tbl x checks if is bound in .
iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
Hashtbl.iter f tbl applies to all bindings in table . receives the key as first argument, and the associated value as second argument. Each binding is presented exactly once to .
La plus grande extension commune est dans ce cas 
