2026 – EPITA – Sciences informatiques MPI
Le sujet est composé d’un problème et d’un questionnaire à choix multiples. Le questionnaire à choix multiples devra être inéséré dans votre copie. Les fonctions à produire dans ce sujet devront être rédigées en OCaml.
Il est possible d’écrire des fonctions auxiliaires non explicitement demandées à condition de les documenter et de les définir avant d’en faire usage. Seules les primitives du langage OCaml ainsi que les fonctions des modules List, Array et Random pourront être utilisées sans restrictions.
La documentation de certaines de ces fonctions est rappelée en annexe.
Problème – Labyrinthes
Un labyrinthe est une grille à n lignes et p colonnes (avec n et p supérieurs ou égaux à 3) dont les cases sont soit vides soit remplies (murs). Deux cases situées sur le bord de la grille sont définies comme entrée et sortie.
On impose de plus les conditions suivantes : 1. Chaque case située sur le bord de la grille est un mur, à l’exception de l’entrée et de la sortie qui sont vides ; 2. Il n’existe aucun carré 2 × 2 constitué uniquement de cases vides ou uniquement de murs ; 3. Si deux murs se trouvent sur une diagonale d’un carré 2 × 2, alors les deux autres cases ne sont pas vides toutes les deux ; 4. Aucun mur n’est complètement isolé : chaque mur doit être voisin d’au moins un autre mur ; 5. Il existe au moins un chemin (sans murs) reliant l’entrée à chaque case vide.
Voici un exemple de labyrinthe à 5 lignes et 5 colonnes :
Structure d’union-find
On rappelle que la structure d’union-find permet de manipuler les ensembles disjoints d’une partition d’un ensemble de la forme {\llbracket0,n-1\rrbracket} avec {(n\geq1)}.
Initialement la structure représente la partition formée par les ensembles disjoints {\{0\},\{1\},\ldots,\{n-1\}}. On attribue à chacun de ces ensembles un représentant qui sera un élément de cet ensemble. Au départ l’ensemble {\{i\}} aura donc pour représentant i.
On définit alors le représentant d’un élément comme étant celui de son ensemble.
On se donne en général les deux opérations de manipulation suivantes :
— find : fonction qui étant donné un élément de {\llbracket0,n-1\rrbracket} renvoie son représentant ;
— union : fonction qui étant donné deux éléments i et j de {\llbracket0,n-1\rrbracket}, transforme la partition en réalisant l’union de l’ensemble contenant i et de celui contenant j.
L’évolution de la structure sera décrite dans les questions suivantes.
On implémente cette structure en représentant chaque ensemble de la partition par un arbre dont les sommets sont étiquetés par les éléments de l’ensemble considéré et dont la racine est étiquetée par le représentant de l’ensemble.
On choisit de représenter ces arbres par un tableau parent de longueur n tel que parent.(i) contienne le parent de l’élément i. Lorsque i sera l’étiquette de la racine de l’arbre, on considèrera que parent.(i) vaut i.
Par exemple le tableau parent [|2;1;1;3;2;3|] représente les ensembles disjoints {0, 1, 2, 4} (de représentant 1) et {3, 5} (de représentant 3) au moyen des deux arbres suivants dont la racine est représentée en haut :
On définit également pour chaque élément un rang qui représente une approximation de la hauteur du sous-arbre dont il serait la racine.
On stocke ce rang dans un tableau de longueur n de sorte à ce que rang.(i) contienne le rang de l’élément i. Initialement la structure représente des singletons donc chaque élément sera représenté par lui-même et son rang vaudra 0. L’évolution de ce rang sera décrite dans les questions suivantes.
Pour implémenter cette structure, on définit le type OCaml suivant :
|
1 |
type union_find = {parent : int array; ran : int array} |
On fera également en sorte que tous les éléments situés sur le chemin allant de i au représentant (la racine de l’arbre), voient leur parent modifié par la valeur du représentant de i. Cela permettra un accès plus rapide au représentant lors des prochains appels de la fonction.
Cette fonction ne modifiera pas le rang des éléments.
Si les racines des deux arbres n’ont pas le même rang, on choisira de rattacher la racine de l’arbre de rang le moins élevé à la racine de l’autre.
Dans le cas contraire, on rattachera l’une des deux arbres (sans préférence) à la racine de l’autre et on incrémentera d’une unité le rang de la racine du nouvel arbre obtenu.
Génération de labyrinthe
Dans cette partie on se place dans le cas où n et p sont des nombres impairs supérieurs ou égaux à 3.
Pour générer un labyrinthe on propose de partir d’une grille où une ligne sur deux et une colonne sur deux ne contiennent que des murs, en commençant par murer la première ligne et la première colonne. Par exemple pour n=7 et p=9, on part de la grille suivante :
On définit le bord d’une grille comme étant l’ensemble des cases situées en première ligne première colonne, dernière ligne et dernière colonne. Deux cases sont considérées comme voisines lorsqu’elles se touchent horizontalement ou verticalement.
On représentera les cases par un couple d’entiers indiquant leur numéro de ligne et de colonne. La case supérieure gauche sera donc la case (0, 0) et la case inférieure droite sera la case (n−1, p−1).
On présente l’algorithme de mélange aléatoire de Fisher-Yates (aussi appelé mélange de Knuth) qui, pour chaque entier i allant de l’indice de la dernière case du tableau à la seconde, permute l’élément d’indice i d’un tableau avec un élément aléatoirement choisi parmi ceux d’indice inférieurs ou égal à i.
On pourra utiliser la fonction Random.int prenant un entier k en entrée et renvoyant un entier aléatoire de {\llbracket0,k-1\rrbracket} .
Cette fonction ne prendra pas de grille en paramètre et retournera le tableau des cases voisines de c.
On définit l’identifiant d’une case n’étant pas sur le bord d’une grille par un entier obtenu en numérotant de gauche à droite et de haut en bas les cases, voici par exemple les identifiants des cases pour une grille à 7 lignes et 9 colonnes :
À présent les cases n’étant pas sur le bord de la grille seront repérées par leur identifiant au sein d’une structure d’union-find permettant de stocker les copomsantes connexes du graphe dont les sommets sont les cases de la grille et les sommets reliés par une arête sont ceux correspondant à des cases voisines.
Si le mur en case c est voisin d’au moins deux cases vides de la grille dont tous les représentants sont différents dans uf, on transformera c en case vide et on réunira les ensembles disjoints contenant c et celles des cases voisines non vides correspondantes.
Dans le cas contraire, la fonction ne fera rien.
On choisit de représenter un labyrithme par une grille, son entrée et sa sortie au moyen du type suivant :
|
1 |
type labyrinthe = {grille : bool array; entree : int*int; sortie : int*int} |
On pourra utiliser la fonction Array.of_list pour transformer une liste en tableau.
Langage associé à un labyrinthe
On décrit à présent les déplacements d’une case au sein d’un labyrinthe par les caractères suivants :
– H lors d’un déplacement vers le haut ; – G lors d’un déplacement vers le gauche ;
– B lors d’un déplacement vers le bas ; – D lors d’un déplacement vers le droite. Un chemin dans un labyrinthe peut être vu comme une succession de déplacements ; en concaténant les caractères qui les représentent, on obtient un mot sur {\Sigma=\{H,B,G,D\}} qui décrit le chemin.
Par exemple, dans le labyrinthe exemple on peut aller de l’entrée à la sortie du labyrithme en suivant le chemin décrit par le mot {DBBDHDDDDBBGGB=DB^2D^2HD^4B^2G^2B}.
Dans un labyrinthe, l’ensemble des mots décrivant un chemin menant de l’entrée à la sortie et n’ayant pas comme facteur les mots HB, BH, GD et DG est appelé langage associé au labyrinthe.
Ce langage peut-il être fini ?
Élément de preuve de réduction
On définit le problème de décision Maze Generation (MG) de la façon suivante : Une instance du problème {MG} est un quintuplet (G, E, S, M, V ) où G est un ensemble de cellules (couples d’entiers ligne-colonne) représentant une grille, E et S sont deux cellules distinctes de G, et W et E sont des sous-ensembles de G.
Le problème {MG} est alors définit comme suit : étant donné un quintuplet (G, E, S, M, V ), existe-t-il un labyrinthe de la même taille que G dont E et S sont respectivement son entrée et sa sortie et tel que les cellules de M sont les murs et celles de V sont des cases vides ?
Lorsque la réponse au problème sera positive, on dira que l’instance est satisfiable. Les cases marquées d’un « ? »représentent les cases de G qui ne sont ni dans M ni dans V .
Le problème {MG} a été prouvé comme étant NP-complet à partir d’une réduction depuis le problème SAT. Cette réduction nécessite entre autre la construction de labyrinthes encodant des opérateurs logiques.
On définit alors l’instance {MG_1(x,y,z)} où les ? ont été remplacés par des littéraux de la variable x, y ou z. Les cases étant évaluées à vrai seront des murs et les autres seront de cases vides.
Lorsque l’on évalue x, y et z, on obtient une grille intégralement déterminée en termes de murs et de cases vides.
En déduire une condition nécessaire et suffisante sur x, y et z pour que {MG_1(x,y,z)} soit satisfiable.
Annexe – extraits de la documentation OCaml1
Extraits concernant le module Array pour manipuler des tableaux
|
1 |
val length : 'a array -> int |
Return the length (number of elements) of given array.
|
1 |
val make : int -> 'a -> 'a array |
make n x returns a fresh array of length n, initialized with x.
All the elements of this new array are initially physically equal to x (in the sense of the == predicate).
Consequently, if x is mutable, it is shared among all elements of the array, and modifying x through one of the array entries would modifiy all other entires at the same time.
|
1 |
val make_matrix : int -> int -> 'a -> 'a array array |
make_matrix dimx dimy e returns a two-dimensionnal array (an array of arrays) with first dimension dimx and second dimension dimy.
All elements of this new matrix are initially physically equal to e. The element (x,y) of a matrix m is accessed with the notation m.(x).(y).
|
1 |
val copy : 'a array -> 'a array |
copy a returns a copy of a, that is, a fresh array containing the same elements as a.
|
1 |
val iter : ('a -> unit) -> 'a array -> unit |
iter f a applies function f in turn to all elements of a.
It is equivalent to f a.(0); f a.(1); …; f a.(lenght a -1); ().
|
1 |
val map : ('a -> 'b) -> 'a array -> 'b array |
map f a applies function f to all the elements of a, and builds an array with the results returned by f : [|f a.(0); f a.(1); …; f a.(length a -1)|]
|
1 |
val for_all : ('a -> bool) -> 'a array -> bool |
for_all f [|a_1; a2;…; a_n|] checks if all elements of the array satisfy predicate f.
That is, it returns (f a1) && (f a2) && … && (f an).
|
1 |
val exists : ('a -> bool) -> 'a array -> bool |
exists [|a1; a2; ..; an|] checks if at least one element of the array satisfies the predicate f. that is, it returns (f a1) || (f a2) || … || (f an).
|
1 |
val to_list : ' array -> 'a list |
to_list a returns the list of all the elements of a.
|
1 |
val of_list : 'a list -> 'a array |
of_list a returns a fresh array containing the elements of l. 1Sources : https://ocaml.org/manual/5.2/api/Array.html, https://ocaml.org/manual/5.2/api/List.html, https://ocaml.org/ manual/5.2/api/Queue.html et https://ocaml.org/manual/5.2/api/Random.html
Extraits du module List pour manipuler des listes
|
1 |
val length : 'a list -> int |
Return the length (number of elements) of the given list.
|
1 |
val hd : 'a list -> 'a |
Return the first element of the given list.
|
1 |
val tl : 'a list -> 'a list |
Return the given list without its first element.
|
1 |
val rev :'a list -> 'a list |
List reversal.
|
1 |
val iter : ('a list -> unit) -> 'a list -> unit |
iter f [a1; a2; …; an] applies function f in turn to [a1;…;an].
It is equivalent to f a1;…; f an.
|
1 |
val map : ('a -> 'b) -> 'a list -> 'b list |
map f [a1; a2;…; an] applies function f to a1,…,an, an builds the list [f a1; f a2;… f an] with the results returned by f.
|
1 |
val fold_left :('acc ->'a -> 'acc) -> 'acc -> 'a list -> 'acc |
fold_left f init [b1; …; bn] is f (…(f (f init b1) b2)…) bn.
|
1 |
val for_all : ('a -> bool) -> 'a list -> bool |
for_all f [a_1; a2;…; a_n] checks if all elements of the list satisfy predicate f.
That is, it returns (f a1) && (f a2) && … && (f an) for a non-empty list and true if the list is empty.
|
1 |
val exists : ('a -> bool) -> 'a list -> bool |
exists [a1; a2; ..; an] checks if at least one element of the list satisfies the predicate f. that is, it returns (f a1) || (f a2) || … || (f an) for a non-empty list and false if the list is empty.
|
1 |
val mem : 'a -> 'a list -> bool |
mem a set is true if and only if a is equal to an element of set.
Extraits concernant le module Random pour générer des nombres aléatoires
|
1 |
val int : int -> int |
Random.int bound returns a random integer between 0 (inclusive) and bound (exclusive). bound must be greater than 0 and less than {2^{30}}.
|
1 |
val float : float -> float |
Random.float bound returns a random floating-point number between 0 and bound (inclusive).
If bound is negative, the result is negative or zero. If bound is 0, the result is 0.
|
1 |
val bool : unit -> bool |
Random.bool () returns true or false with probability 0.5 each.
QCM-MPI
Dans ce questionnaire à choix multiples, chaque question comporte une ou plusieurs bonnes réponses. Chaque réponse correcte fait gagner des points, mais chaque réponse fausse annule tous les points de la question.
Les questions peuvent être formulées au pluriel par commodité d’expression. Cela n’implique pas nécessairement qu’elles admettent plusieurs réponses correctes. On considère les deux fonctions, écrites en langage C, suivantes :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
void mystere1(int *a, int *b) { *a = *a + *b; *b = *a - *b; *a = *a - *b; } int mystere2(int n) { int s = 0; int p = 1; while (n > 0) { s += (n % 2) * p; p = 10 * p; n = n / 2; } return s; } |
*a != *b, alors à l’issue de la fonction mystere1 :
□ a et b pointent vers la même adresse ;
□ a et b pointent vers la meme valeur ;
□ l’adresse pointée initialement par a est pointée par b et inversement ;
□ les valeurs pointées par a et b ont été échangées.
□ mystere2(1) renvoie 0 ;
□ mystere2(42) renvoie 101010 ;
□ mystere2(314) renvoie 717007 ;
□ Le chiffre 3 peut apparaître dans l’écriture décimale de mystere2(n) pour {n\in\llbracket0,1023\rrbracket}.
□ est toujours déterministe ;
□ n’est jamais déterministe ;
□ se construit à partir d’une expression régulière ;
□ ne possède jamais plus d’un état final.
□ {m}□ {2m}
□ {n.m}
□ {m^2}
Par exemple : 101 et 011 sont reliés, mais 101 et 111 ne le sont pas. Parmi les assertions suivantes, indiquer celles qui sont correctes :
□ Les sommets du graphe sont tous de même degré ;
□ Le graphe ne contient pas de cycles ;
□ Le graphe n’est pas connexe ;
□ Il est possible d’attribuer une couleur à chaque sommet du graphe de sorte que deux sommets reliés aient toujours des couleurs différentes ; ce en utilisant seulement 3 couleurs.