J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Mines Option Informatique MP 2024

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo mines
🔗 Explorer
Banque
Mines
Année
2024
Filière
MP
Matière
Info
Mines MPMines 2024MP InfoInfo 2024
2025_08_29_853e383c0636dfa95e20g

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

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 ) 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 OCaml 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 OCaml 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 et appelons son cardinal. Nous notons systématiquement les éléments distincts de .
Définition : Nous appelons relation d'ordre sur toute relation binaire qui est
  1. réflexive, c'est-à-dire telle que, pour tout indice compris entre 0 et , nous avons la relation ,
  2. antisymétrique, c'est-à-dire telle que, pour tous indices et compris entre 0 et , si les relations et sont vérifiées, alors nous avons l'égalité
  3. transitive, c'est-à-dire que, pour tous indices et compris entre 0 et , si les relations et sont vérifiées, alors nous avons encore la relation .
    Un ensemble fini muni d'une relation d'ordre s'appelle un ensemble ordonné et se note ( ). 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 par une matrice carrée de dimension , de type
1.
type order = bool array array
où le coefficient r. (i). (j) vaut true si et seulement si la relation est vérifiée.
- Écrire une fonction OCaml check_reflexivity (r:order) : bool qui vérifie si la relation est une relation réflexive et qui relève du paradigme de programmation impérative.
- Écrire une fonction OCaml check_reflexivity_bis (r:order) : bool qui vérifie également si la relation 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.
- Écrire une fonction OCaml check_antisymmetry (r:order) : bool qui vérifie si la relation est une relation antisymétrique.
- Écrire une fonction OCaml check_transitivity ( r :order) : bool qui vérifie si la relation est une relation transitive.
- Écrire une fonction OCaml is_order ( :order) : bool qui vérifie si la relation est une relation d'ordre en s'appuyant sur les questions 1,3 et 4.
Définition : Nous appelons graphe d'un ensemble ordonné ( ), ou simplement graphe de la relation d'ordre , le graphe orienté dont l'ensemble des arcs est
ù
Nous rappelons que le degré sortant d'un sommet désigne le nombre d'arcs dont l'extrémité initiale vaut .
- Écrire une fonction OCaml outdegrees (r:order) : int array dont la valeur de retour est le tableau des degrés sortants des sommets du graphe de la relation d'ordre . Autrement dit, pour tout indice compris entre 0 et , l'entier est le degré sortant du sommet .
- Écrire une fonction OCaml argmin (d:int array) : int dont la valeur de retour est un indice valide tel que, pour tout indice compris entre 0 et la longueur du tableau d'entiers exclue, on a l'inégalité .
Définition : Étant donné un ensemble ordonné de cardinal , nous appelons tri topologique de toute permutation des entiers de l'intervalle telle que, pour tous indices et compris entre 0 et , si l'on a la relation , alors on a l'inégalité . Pour tous indices compris entre 0 et , nous disons dans ce cas que le sommet est le sommet de numéro .
- Montrer qu'il existe une constante entière telle que, pour tout tri topologique , le sommet de numéro , à savoir le sommet , est de degré sortant et le degré sortant des autres sommets est supérieur ou égal à .
- Écrire une fonction OCaml topological_sort (r:order) : int array dont la valeur de retour est un tri topologique de l'ensemble ordonné par . 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.
11 - Exprimer la complexité en temps de la fonction topological_sort r en fonction du nombre d'éléments ordonnés par la relation . Dire comment on qualifie une telle complexité en fonction de l'espace en mémoire utilisé pour représenter l'argument d'entrée .

2. Chaînes et antichaînes

Définition : Étant donné un ensemble ordonné ( ), nous appelons chaîne toute partie de totalement ordonnée, c'est-à-dire, telle que pour tous éléments et , nous avons la relation ou la relation .
Indication OCaml : Nous représentons une chaîne par le type int list.
Nous donnons le code suivant
let rec is_chain (r:order) (c:int list) : bool =
    match c with
    | [] -> true
    | v::cc -> List.for_all (fun x -> x > v || x < v) cc
        && is_chain r cc
où nous avons recouru à la fonction for_all du module List ainsi décrite dans la documentation de OCaml :
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.
12 - Confirmer ou réfuter la spécification suivante : la fonction is_chain r c codée comme ci-dessus teste si la liste de sommets est une chaîne au sens de la relation d'ordre . Dans le premier cas, on fournira une démonstration; dans le second cas, on modifiera la fonction is_chain afin qu'elle soit correcte.

13 - Déterminer la complexité en temps de la fonction is_chain r c codée comme ci-dessus en fonction de la longueur de la liste . Justifier le calcul.
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ù est la longueur de la liste . À 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 ( ) à travers l'interface suivante :
type hp
val init : order -> int -> hp
val is_empty : hp -> bool
val push : hp -> int -> bool
val pop : hp -> bool
L'appel init gamma doit permet d'initialiser une collection vide, informée de la relation d'ordre , et de capacité . L'appel is_empty q doit indiquer si la collection est vide. L'appel push q i doit insérer l'élément à la collection ; l'appel pop q doit retirer un élément de la collection . 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 :
let is_chain_bis (r:order) (c:int list) : bool =
    let q = init r (List.length c) in
    let rec insert c : bool =
        match c with
        | [] -> true
        | hd::tl -> (push q hd) && insert tl
    in
    let rec extract_all () : bool =
        if is_empty q then true
        else (pop q) && (extract_all ())
    in
    (insert c) && (extract_all ())
Cette fonction insère les éléments de la liste à une collection initialement vide , de type hp, puis les retire de cette collection .
- Compléter la description du type hp en nommant une structure de donnée, dont on rappellera 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ù est la longueur de la liste . Justifier la réponse.
Définition : Étant donné un ensemble ordonné ( ), nous appelons antichaîne toute collection de sommets dont les éléments sont deux à deux incomparables, c'est-à-dire, telle que pour tous éléments distincts et , aucune des relations ou n'est vérifiée.
Indication OCaml : Nous représentons une antichaîne par le type int list.
- 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 est une antichaîne pour la relation d'ordre . En déduire que la fonction is_antichain admet pour complexité en temps la même complexité que celle obtenue à la question 13.
- 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ù est la longueur de la liste .

3. Couverture par des chaînes

Définition : Nous disons qu'une famille finie de chaînes de l'ensemble ordonné est une couverture si la réunion est égale à l'ensemble .
- Soit une couverture de l'ensemble ordonné ( ) et soit une antichaîne de de cardinal . Démontrer l'inégalité
Définition : Étant donné un ensemble ordonné ( ), nous appelons graphe des poursuites d'un ensemble ordonné ( ) le graphe biparti non orienté où les ensembles de sommets et sont deux copies distinctes de , dont on note les éléments
et dont l'ensemble des arêtes est
ù
Indication OCaml : Nous représentons un graphe biparti à sommets par un tableau de longueur contenant des listes de voisins
type bipartite = int list array
Chaque arrête est notée deux fois en mémoire.
18 - Écrire une fonction OCaml bipartite_of_order (r:order) : bipartite dont la valeur de retour est le graphe des poursuites tiré de la relation d'ordre .
Définition : Nous appelons couplage tout ensemble d'arêtes dont les extrémités sont distinctes.
- Pour tout couplage du graphe des poursuites , nous construisons la partition de l'ensemble telle que
  1. pour tous indices et compris entre 0 et , si le couple est une arête de , alors les deux éléments et appartiennent à une même part ,
    2 . le cardinal est aussi grand que possible.
    Montrer que pour tout indice compris entre 1 et , l'ensemble est une chaîne de ( ).
Indication OCaml : Nous représentons un couplage dans le graphe des poursuites ( ) par un tableau de longueur , de type int array, tel que si le couple est une arête du couplage et si le sommet n'est pas l'extrémité d'une arrête du couplage.
- Déduire de la question 19 une fonction OCaml chains_of_matching (m:int array) : int list list dont la valeur de retour est une liste de chaînes disjointes tirée du couplage .
- Une couverture de l'ensemble ordonné ( ) par des chaînes disjointes étant fixée, expliquer comment construire un couplage tel que la construction de la question 19 conduit à la partition .
- Montrer que la construction de la question 19 fournit une couverture de l'ensemble par un nombre minimum de chaînes si et seulement si elle s'applique à un couplage de cardinal maximum.
- Écrire une fonction OCaml maximum_matching (p:bipartite) : int array qui calcule un couplage de cardinal maximum dans le graphe biparti .
- Écrire une fonction OCaml minimum_cover (r:order) : int list list qui calcule une couverture par une famille de chaînes disjointes de cardinal minimum.
- Déterminer la complexité en temps de la fonction minimum_cover r en fonction du nombre d'éléments ordonnés par la relation .

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 m. (x). (y).
  • 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) |].
  • 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 array -> unit
Array.iter f a applies function in turn to all the elements of . It is equivalent to 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

Mines Option Informatique MP 2024 - Version Web LaTeX | WikiPrépa | WikiPrépa