Mines Option Informatique MP 2024Sujet et rapport du jury

É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

ÉPREUVE D'INFORMATIQUE MP

Préliminaires

Travail attendu

1. Relation d'ordre et tri topologique

1. réflexive, c'est-à-dire telle que, pour tout indice i compris entre 0 et n − 1, nous avons la relation v_i⊴v_i,
2. antisymétrique, c'est-à-dire telle que, pour tous indices i et j compris entre 0 et n − 1, si les relations v_i⊴v_j et v_j⊴v_i sont vérifiées, alors nous avons l'égalité v_i = v_j
3. transitive, c'est-à-dire que, pour tous indices i, j et k compris entre 0 et n − 1, si les relations v_i⊴v_j et v_j⊴v_k sont vérifiées, alors nous avons encore la relation v_i⊴v_k.
   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.

type order = bool array array

2. Chaînes et antichaînes

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

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.

type hp
val init : order -> int -> hp
val is_empty : hp -> bool
val push : hp -> int -> bool
val pop : hp -> bool

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 ())

3. Couverture par des chaînes

1. pour tous indices i et j compris entre 0 et n − 1, si le couple (w_i, w_(n + j)) ∈ W_0 × W_1 est une arête de M, alors les deux éléments v_i et v_j appartiennent à une même part C_ℓ,
   2 . le cardinal λ est aussi grand que possible.
   Montrer que pour tout indice ℓ compris entre 1 et λ, l'ensemble C_ℓ est une chaîne de ( V, ⊴ ).

A. Annexe : aide à la programmation en OCaml

• length : 'a array -> int

• make : int -> 'a -> 'a array

• make_matrix : int -> int -> 'a -> 'a array array

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

• copy : 'a array -> 'a array

• mem : 'a -> 'a array -> bool
  mem a l is true if and only if a is structurally equal to an element of l (i.e. there is an x in l such that compare a x = 0 ).
• for_all : ('a -> bool) -> 'a array -> bool

• exists : ('a -> bool) -> 'a array -> bool

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

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

• iter : ('a -> unit) -> 'a array -> unit

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

Fin de l'Épreuve