Mines Informatique optionnelle MP 2024

A2024 -- INFO MP

Cmb

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 2024

Durée de l'épreuve : 3 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

ÉPREUVE D'INFORMATIQUE MP

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 7 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.

COE)

Épreuve d'informatique d'option MP 2024

Préliminaires

L'épreuve est formée d'un problème unique, constitué de 25 questions, qui porte 
sur
l'algorithmique de quelques résultats mathématiques reliés à la notion de 
relation d'ordre. 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 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 n) et du point de vue informatique pour celle en romain avec espacement 
fixe (par
exemple n).

Des rappels des extraits du manuel de documentation de OCamil sont reproduits 
en annexe.
Ces derniers portent sur le module Array.

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 
exclusivement,
en reprenant l'en-tête de fonctions fourni par le sujet, sans s'obliger à 
recopier la déclaration
des types. Il est permis d'utiliser la totalité du langage OCami mais il est 
recommandé de
s'en tenir aux fonctions les plus courantes afin de rester compréhensible. 
Quand l'énoncé
demande de coder une fonction, sauf demande explicite, il n'est pas nécessaire 
de justifier
que celle-ci est correcte ou de tester que des préconditions sont satisfaites.

Le barème tient compte de la clarté et de la concision des programmes : il est 
attendu que
l'on choisisse des noms de variables intelligibles ou encore que l'on structure 
de longs codes
par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.

1. Relation d'ordre et tri topologique

Nous fixons un ensemble fini V et appelons n son cardinal. Nous notons 
systématiquement
Vo, V1, -.... Un_1 les éléments distincts de V.

Définition : Nous appelons relation d'ordre sur V toute relation binaire < qui est 1. réflexive, c'est-à-dire telle que, pour tout indice ? compris entre 0 et n -- 1, nous avons la relation v, < v;, 2. antisymétrique, c'est-à-dire telle que, pour tous indices ? et j compris entre 0 et n -- 1, si les relations v; < v; et v; < v; sont vérifiées, alors nous avons l'égalité v; -- v, 3. transitive, c'est-à-dire que, pour tous indices ?, 7 et k compris entre 0 et n -- I, si les relations v;,  v; et vu;  v, sont vérifiées, alors nous avons encore la relation v;  vg. Un ensemble fini muni d'une relation d'ordre s'appelle un ensemble ordonné et se note (V, ). Nous réservons le symbole < pour désigner l'ordre usuel sur les entiers. Indication OCaml : Nous représentons tout ordre sur un ensemble de cardinal n par une matrice carrée r de dimension n x n, de type 1. type order = bool array array Page 1 sur 7 Épreuve d'informatique d'option MP 2024 où le coefficient r.(i).(j) vaut true si et seulement si la relation v; < v; est vérifiée. [] 1 - Écrire une fonction OCaml check reflexivity (r:order) : bool qui vérifie si la relation r est une relation réflexive et qui relève du paradigme de programmation impérative. [] 2 - Écrire une fonction OCaml check reflexivity bis (r:order) : bool qui vérifie également si la relation r est une relation réflexive mais qui, par contraste avec la question 1, relève du paradigme de programmation fonctionnelle. Dans le reste du sujet, le choix du paradigme de programmation est libre. [] 3 -- Écrire une fonction OCaml check _antisymmetry (r:order) : bool qui vérifie si la relation r est une relation antisymétrique. [] 4 -- Écrire une fonction OCaml check _transitivity (r:order) : bool qui vérifie si la relation r est une relation transitive. [1 5 - Écrire une fonction OCaml is order (r:order) : bool qui vérifie si la relation r est une relation d'ordre en s'appuyant sur les questions 1, 3 et 4. Définition : Nous appelons graphe d'un ensemble ordonné (V, ), ou simplement graphe de la relation d'ordre <, le graphe orienté G = (V, E) dont l'ensemble des arcs est E = {(v;,v;) où (i,j) EUR [0,n -- 1]° et v, A v;}. Nous rappelons que le degré sortant d'un sommet v désigne le nombre d'arcs dont l'extrémité initiale vaut v. [1 6 -- Écrire une fonction OCaml outdegrees (r:order) : int array dont la valeur de retour est le tableau d des degrés sortants des sommets du graphe de la relation d'ordre r. Autrement dit, pour tout indice à compris entre 0 et n -- 1, l'entier d{i] est le degré sortant du sommet v;. [1 7 - Écrire une fonction OCaml argmin (d:int array) : int dont la valeur de retour est un indice valide ? tel que, pour tout indice j compris entre 0 et la longueur du tableau d'entiers d exclue, on a l'inégalité d[i] < d[j]. Définition : Étant donné un ensemble ordonné (V, <) de cardinal n, nous appelons tri topologique de V toute permutation 7 des entiers de l'intervalle [0,n -- 1] telle que, pour tous indices 2 et 3 compris entre 0 et n -- 1, si l'on à la relation v, A v;, alors on a l'inégalité T(i) < T(j). Pour tous indices à compris entre 0 et n -- 1, nous disons dans ce cas que le sommet vw; est le sommet de numéro T(i). CT 8 --- Montrer qu'il existe une constante entière 0) telle que, pour tout tri topologique 7, le sommet de numéro n -- 1, à savoir le sommet v,-1(,_1,, est de degré sortant 0, et le degré sortant des autres sommets est supérieur ou égal à 00. Page 2 sur 7 Épreuve d'informatique d'option MP 2024 [1 9 - Écrire une fonction OCaml topological sort (r:order) : int array dont la valeur de retour est un tri topologique de l'ensemble ordonné par r. Il est attendu que la fonction attribue les numéros par ordre décroissant et que, en cours d'exécution, elle s'appuie sur la question 8 pour identifier le prochain sommet à numéroter. [] 10 -- Énoncer un ensemble d'invariants qui démontre que la fonction topological_ sort de la question 9 est correcte. Il pourra s'agir d'invariants de boucle dans le cas d'un programme itératif ou de postconditions dans le cas d'un programme récursif. CT 11 -- Exprimer la complexité en temps de la fonction topological sort r en fonction du nombre d'éléments n ordonnés par la relation r. Dire comment on qualifie une telle complexité en fonction de l'espace en mémoire utilisé pour représenter l'argument d'entrée r. 2. Chaînes et antichaines Définition : Étant donné un ensemble ordonné (V, ), nous appelons chaîne toute partie C de V totalement ordonnée, c'est-à-dire, telle que pour tous éléments c et c EUR C, nous avons la relation c  c' ou la relation EUR < c. Indication OCaml : Nous représentons une chaîne par le type int list. Nous donnons le code suivant 2. let rec is chain (r:order) (c:int list) : bool = 3. match c with 4. | [] -> true

5. | viicc -> List.for all (fun x -> x > v || x < v) cc 6. && is chain r cc où nous avons recouru à la fonction for all du module List ainsi décrite dans la documen- tation de OCamil : val for all : ('a -> bool) -> 'a list -> bool

for_all f [ai; ...; an] checks if all elements of the list satisfy the 
predicate f.
That is, it returns (f a1) && (£ a2) && ... && (f an) for a non-empty list and
true if the list is empty.

CT 12 -- Confirmer ou réfuter la spécification suivante : la fonction is_ chain 
r ec codée comme
ci-dessus teste si la liste de sommets c est une chaîne au sens de la relation 
d'ordre r.

Dans le premier cas, on fournira une démonstration ; dans le second cas, on 
modifiera la
fonction is_ chain afin qu'elle soit correcte.

CT 13 -- Déterminer la complexité en temps de la fonction is_ chain r c codée 
comme ci-dessus
en fonction de la longueur y de la liste c. Justifier le calcul.

Page 3 sur 7
Épreuve d'informatique d'option MP 2024

Nous nous proposons d'écrire une fonction is chain bis r c obéissant à la 
spécification de
la question 12 et de complexité en temps O(7log y) où 7 est la longueur de la 
liste c. À cette
fin, nous nous préparons à introduire une structure de donnée mutable à 
capacité bornée
permettant de stocker une collection d'éléments de (V, 4) à travers l'interface 
suivante :

7. type hp

8. val init : order -> int -> hp
9. val is empty : hp -> bool

10. val push : hp -> int -> bool
11. val pop : hp -> bool

L'appel init r gamma doit permet d'initialiser une collection vide, informée de 
la relation
d'ordre r, et de capacité 7. L'appel is_ empty q doit indiquer si la collection 
q est vide. L'appel
push q i doit insérer l'élément vw, EUR V à la collection g; l'appel pop a doit 
retirer un élément
de la collection q. Nous envisageons que les appels à push et de pop puissent 
échouer, ce qui est
signalé par la valeur de retour de ces fonctions. Nous écrivons la fonction is 
chain bis r c
sous la forme suivante :

12. let is chain bis (r:order) (c:int list) : bool =

13. let q = init r (List.length c) in
14. let rec insert c : bool =

15. match c with

16. | [] -> true

17. | hd::t1 -> (push q hd) && insert tl1l
18. in

19. let rec extract all () : bool =

20. if is empty q then true

21. else (pop q) && (extract all ())
22. in

23. (insert c) && (extract all ())

Cette fonction insère les éléments de la liste c à une collection initialement 
vide q, de type hp,
puis les retire de cette collection q.

CT 14 -- Compléter la description du type hp en nommant une structure de 
donnée, dont on rap-
pellera brièvement l'invariant de bonne constitution, de sorte que la fonction 
is chain bis r c
obéisse à la spécification de la question 12 et s'exécute en temps O(7log y), 
où 7 est la
longueur de la liste c. Justifier la réponse.

Définition : Étant donné un ensemble ordonné (V, <), nous appelons antichaîne toute collection de sommets À EUR V dont les éléments sont deux à deux incomparables, c'est-à-dire, telle que pour tous éléments distincts a et a' EUR À, aucune des relations a < a" ou a" < a n'est vérifiée. Indication OCaml : Nous représentons une antichaîne par le type int list. CT 15 --- Modifier la fonction is chain introduite à la question 12 afin d'écrire une fonction OCaml is antichain obéissant à la spécification : la fonction is antichain r a teste si la liste de sommets a est une antichaîne pour la relation d'ordre r. En déduire que la fonction is_antichain admet pour complexité en temps la même complexité que celle obtenue à la question 13. Page 4 sur 7 Épreuve d'informatique d'option MP 2024 C1 16 -- Confirmer ou réfuter l'existence d'une fonction is antichain bis r a obéissant à la même spécification que celle de la question 15 et de complexité en temps O(a log, &), où a est la longueur de la liste a. 3. Couverture par des chaînes Définition : Nous disons qu'une famille finie (Cy)14, 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 n, initialized with x. AI 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.

make matrix : int -> int -> 'a -> ?'a array array

Array.make matrix dimx dimy e returns à two-dimensional array (an array of 
arrays) with first
dimension dimx and second dimension dimy. AI the 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).

init : int -> (int -> ?'a) -> ?'a array

Array.init n f returns a fresh array of length n, with element number à 
initialized to the result
of f(i). In other terms, init n f tabulates the results of f applied to the 
integers 0 to n -- 1.

copy : 'a array -> 'a array

Array.copy a returns a copy of à, that is, a fresh array containing the same 
elements as a.

mem : a -> 'a array -> bool

mem a Lis true if and only if a is structurally equal to an element of { (i.e. 
there is an x in { such that
compare a x = O).

for_all : ('a -> bool) -> 'a array -> bool

Array.for all f [lai; ...; an] checks if all elements of the array satisfy the 
predicate f. That
is, it returns (f ai) && (f a2) && ... && (f an).

exists : ('a -> bool) -> ?'a array -> boo!l

Array.exists f [lal; ...; an] checks if at least one element of the array 
satisfies the predicate f.
That is, it returns (£ a1) || (Cf a2) || ... || (C£ an).

map : ('a -> 'b) -> ?'a array -> 'b array

Array.map f a applies function f to all the elements of a, and builds an array 
with the results returned
by f: [1 f a.(0); f a.(1); ...; f a.(length a - 1) |].

mapi : (int -> 'a -> ?'b) -> 'a array -> 'b array

Same as Array.map, but the function is applied to the index of the element as 
first argument, and the
element itself as second argument.

iter : ('a -> unit) -> ?'a arraÿ -> unit

Array.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); ().

iteri : (int -> 'a -> unit) -> ?'a array -> unit

Same as Array.iter, but the function is applied to the index of the element as 
first argument, and
the element itself as second argument.

D'après https://v2.ocaml.org/api/Array.html

FIN DE L'ÉPREUVE

Page 7 sur 7