2025 – EPITA – Sciences numériques MPI
Le sujet est composé d’un problème et d’un questionnaire à choix multiples. Le questionnaire à choix multiples devra être inséré dans votre copie.
Les arbres de preuve demandés dans ce sujet devront utiliser les règles de la déduction naturelle listées en annexe. 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 Queue pourront être utilisées sans restrictions.
La documentation de certaines de ces fonctions est rappelée en annexe.
Problème – Pavage d’une surface avec des dominos
On considère une surface quadrillée composée de n rangées de p colonnes que l’on souhaite recouvrir avec des dalles de taille 1 par 2 que nous appellerons dominos.
Les dominos ne peuvent être disposés que verticalement ou horizontalement. On fait de plus l’hypothèse que certaines cases du quadrillage peuvent comporter un obstacle (symbolisé par une croix) et ne sont donc pas à recouvrir.
L’objectif de ce problème est de déterminer un pavage de la surface, c’est-à-dire un recouvrement intégral, avec des dominos, des cases ne comportant pas d’obstacles.
Voici un exemple de surface de taille n = 3 par p = 5 comportant 3 obstacles :
On peut paver cette surface à l’aide de 6 dominos A, B, C, D, E et F de la façon suivante :
1 Dénombrement et déduction naturelle
On considère à présent la surface suivante dont on a numéroté les cases sans obstacles :
Notons a la variable propositionnelle indiquant si un même domino est placé sur les cases 0 et 1, b celle indiquant si un même domino est placé sur les cases 1 et 2 et c celle indiquant si un même domino est placé sur les cases 2 et 3.
2 Recherche d’un couplage maximum dans un graphe biparti
On fait l’hypothèse, pour tout le reste du problème, que les graphes manipulés sont connexes.
On rappelle qu’un graphe G = (S, A) est biparti s’il existe une partition de S en deux ensembles {S_1} et {S_2} tels que les arcs de A ont une de leurs extrémités dans {S_1} et l’autre dans {S_2}.
On rappelle également qu’un graphe est bicolorable s’il est possible d’attribuer une couleur à chacun de ses sommets de façon à utiliser au plus 2 couleurs différentes et que deux sommets adjacents n’aient jamais la même couleur.
Quitte à renuméroter les sommets des graphes considérés, on choisit de représenter les graphes bipartis par le type :
|
1 2 3 4 5 6 7 |
type b_graph = { n1 : int; n2 : int; voisins : int list array } ;; |
où n1 est le cardinal de {S_1}, n2 celui de {S_2} et voisins est la représentation par listes d’adjacence du graphe.
Les sommets de {S_1} étant alors renumérotés de 0 à {n_1-1} et ceux de {S_2} de {n_1} à {n_1+n_2-1}. La renumérotation des sommets sera représentée par un tableau de {n_1+n_2} entiers de sorte que la case d’indice i contienne le nouveau numéro du sommet i.
Par exemple :
Ainsi {n1=3; n2=3; voisins = [|[4];[3;4;5];[3];[1;2];[0;1];[1]|]} pourra représenter le graphe de l’exemple ci-dessus et [|0;3;1;4;2;5|] la renumérotation qui lui est associée.
On rappelle qu’un couplage d’un graphe est un ensemble d’arêtes du graphe deux à deux non incidentes (c’est-à-dire n’ayant pas de sommet en commun).
Par exemple l’ensemble des arêtes {1, 4} et {2, 3} est un couplage du graphe biparti suivant :
Le cardinal d’un couplage est le nombre d’arêtes qui le composent.
Un couplage d’un graphe est dit maximum lorsqu’il n’existe pas de couplage du graphe dont le cardinal lui serait strictement supérieur. On choisit de représenter les couplages par un tableau indexé par les sommets du graphe.
Le contenu de la case d’indice i contient le numéro du sommet avec lequel i est couplé, et -1 sinon.
On rappelle qu’un sommet est libre vis-à-vis d’un couplage s’il n’est l’extrémité d’aucune arête du couplage.
Le graphe d’augmentation associé à un couplage C d’un graphe biparti G est le graphe orienté obtenu à partir de G en appliquant les transformations suivantes : 1. orientation des arêtes :
— les arêtes appartenant au couplage C sont orientées des sommets de {S_2} vers ceux de {S_1} ;
— les arêtes n’appartenant pas au couplage C sont orientées des sommets de {S_1} vers ceux de {S_2} ; 2. ajout de sommets : on ajoute deux nouveaux sommets s et t, respectivement numérotés {n_1+n_2} et {n_1+n_2+1} ; 3. ajout d’arcs :
— on ajoute pour chaque sommet x de {S_1} et libre vis-à-vis de C, un arc allant de s vers x ;
— on ajoute pour chaque sommet y de {S_2} et libre vis-à-vis de C, un arc allant de y vers t.
Les graphes d’augmentation seront également représentés par le type b_graph.
On prendra soin de retourner un graphe indépendant de celui passé en paramètre.
On appelle chemin augmentant tout chemin du graphe d’augmentation menant de s à t.
Lorsqu’il existe un chemin menant de s à t, la fonction renverra la liste des sommets rencontrés dans l’ordre de parcours du chemin (sans s et t).
Si un tel chemin n’existe pas, la fonction renverra la liste vide.
3 Retour au problème de pavage
On considère le problème de décision Pavable qui, à partir des dimensions d’une surface quadrillée et de la liste de ses obstacles, indique si la surface peut ou non être pavée.
On choisit de numéroter de gauche à droite et de haut en bas l’ensemble des m cases sans obstacle par les entiers consécutifs de 0 à m−1. On représente la surface par un graphe non orienté et non pondéré.
L’ensemble des sommets est l’ensemble des numéros des cases sans obstacles et on considère que deux sommets sont adjacents si et seulement si les cases qu’ils représentent se touchent horizontalement ou verticalement.
Les graphes seront représentés par leurs listes d’adjacence au moyen du type int list array (la case i contient la liste des voisins du sommet i). En voici un exemple :
Le graphe sera alors représenté par le tableau [|[1];[0;2];[1;3];[2]|].
Pour simplifier on fera l’hypothèse, comme précisé dans la partie précédente, que l’on ne manipulera que des graphes connexes.
La fonction retournera une représentation de ce graphe sous le type b_graph ainsi que la renumérotation adoptée pour l’ensemble de ses sommets.
QCM – MPI
Document à insérer dans votre copie d’examen 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 la fonction, écrite en langage C, suivante :
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int mystere(int m, int n) { int t=1; if (n>0) { t = mystere(m,n/2); t = t*t; if (n%2==1) t=m*t; } return t; } |
□ effectue un nombre linéaire d’appels récursifs en n quand n est une puissance de 2 ;
□ effectue un nombre quadratique d’appels récursifs en n quand n est une puissance de 2 ;
□ permet de calculer les puissances d’un nombre ;
□ permet de calculer le produit de deux nombres.
□ par intersection finie ;
□ par union finie ;
□ par union infinie ;
□ par passage au complémentaire.
□ déterminer les composantes fortement connexes d’un graphe orienté ;
□ déterminer un plus court chemin entre tout couple de sommets d’un graphe orienté ;
□ déterminer un arbre couvrant de poids minimal d’un graphe non orienté pondéré ;
□ déterminer un automate fini acceptant le langage dénoté par une expression régulière.
□ l’algorithme de Kruskal ;
□ l’algorithme de Boyer-Moore ;
□ l’algorithme de Quine ;
□ l’algorithme de Dijkstra.
□ est sous forme normale conjonctive ;
□ est sous forme normale disjonctive ;
□ est satisfiable ;
□ est équivalente à {(a\land b)\lor(a\land c)\lor(b\land c)}.
Annexe A – règles de la déduction naturelle
On se donne les règles suivantes de la déduction naturelle où {\varphi,\varphi_1,\varphi_2} et {\psi} désignent des formules logiques et {\Gamma} un ensemble de formules logiques.
De plus {\top} désigne la tautologie et {\bot} l’antilogie (ou contradiction).
On s’autorisera également l’emploi des deux règles suivantes sans en fournir d’arbre de preuve :
Annexe B – extraits de la documentation OCaml 1
Extraits concernant le module Array pour manipuler des tableaux
|
1 |
val length : 'a array -> int |
Return the length (number of elements) of the 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 will modify all other entries at the same time.
|
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 the elements of a.
It is equivalent to f a.(0); f a.(1); …; f a.(length 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 [|a1; …; an|] checks if all elements of the array satisfy the predicate f.
That is, it returns (f a1) && (f a2) && … && (f an). 1. Sources : https://ocaml.org/manual/5.2/api/Array.html, https://ocaml.org/manual/5.2/api/List.html et https://ocaml.org/manual/5.2/api/Queue.html
|
1 |
val exists : ('a -> bool) -> 'a array -> bool |
exists f [|a1; …; an|] checks if at least one element of the array satisfies the predicate f. That is, it returns (f a1) || (f a2) || … || (f an).
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 -> unit) -> 'a list -> unit |
iter f [a1; …; an] applies function f in turn to [a1; …; an].
It is equivalent to f a1; f a2; …; f an.
|
1 |
val map : ('a -> 'b) -> 'a list -> 'b list |
map f [a1; …; an] applies function f to a1, …, an, and builds the list [f a1; …; 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 [a1; …; an] checks if all elements of the list satisfy the 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 f [a1; …; 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 Queue pour manipuler des files
|
1 |
val create : unit -> 'a t |
Return a new queue, initially empty.
|
1 |
val push : 'a -> 'a t -> unit |
push x q adds the element x at the end of the queue q.
|
1 |
val pop : 'a t -> 'a |
pop q removes and returns the first element in queue q, or raises Queue.Empty if the queue is empty.
|
1 |
val is_empty : 'a t -> bool |
Return true if the given queue is empty, false otherwise.
Fin du sujet