Mines Informatique 2 MPI 2023Sujet 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 2023

DEUXIÈME ÉPREUVE D'INFORMATIQUE

Cette épreuve concerne uniquement les candidats de la filière MPI.

Préliminaires

Travail attendu

1 Complexité de Kolmogoroff

• si la chaîne x, de type string, est le code source d'une expression OCaml y de type string et si l'exécution du code x se termine sans erreur, alors eval x se termine et a pour valeur de retour la valeur de y;
• sinon, eval x ne se termine pas.

1.1 Un premier exemple

1.2 Quelques propriétés

2 Estimation de la complexité grâce au décompresseur de Huffman

• Hashtbl.create ( n : int) : ('a, 'b) Hashtbl.t crée un dictionnaire vide de taille initiale n.
• Hashtbl.add (d : ('a, 'b) Hashtbl.t) (k : 'a) (v : 'b) : unit ajoute une association entre la clé k et la valeur v au dictionnaire d.
• Hashtbl.find_opt (d : ('a, 'b) Hashtbl.t) ( k : ^′ a ) : ' b option vaut Some v sile dictionnaire d possède une association entre la clé k et la valeur v et vaut None sinon.
  ◻12 - Écrire une fonction OCaml count (x : string) : (char, int) Hashtbl.t dont la valeur de retour est un dictionnaire qui associe chaque caractère σ ∈ Σ présent dans la chaîne x à son nombre d'occurrences |x|_σ.

3 Interlude

let inc s = s := "a" ~ (!s); !s (* Commun aux 3 propositions *)
let new_string1 = (* Proposition 1 *)
    let seed1 = ref "#" in
    fun () -> inc seed1
let new_string2 () = (* Proposition 2 *)
    let seed2 = ref "#" in
    inc seed2
let seed3 = ref "#" (* Proposition 3 *)
let new_string3 () =
    inc seed3

4 Estimation de la complexité grâce au décompresseur de De Bruijn

4.1 Construction syntaxique d'un langage

type ada = V of string | A of (ada * ada) | F of (string * ada)

((aaa#->aab#->aab#(aba#->aba#abb#))(baa#->bab#bba#)) }\mp@code{(}\mathcal{G}

admet pour arbre d'analyse :

24 - Écrire une fonction OCaml parseT (w : char list) : ada * char list dont la spécification suit :
Pré-condition : Il existe une décomposition du motw en w = ps avec p ∈ L(G) et s ∈ Σ^∗, dans laquelle le préfixe p est de longueur maximale.
Valeur de retour : Couple ( a, s ) où a est l'arbre d'analyse de p et s est le suffixe restant.
Effet : Une exception SyntaxError est levée si la pré-condition n'est pas satisfaite.

4.2 Réécriture des variables et sérialisation

• StringSet.mem : string -> StringSet.t -> bool qui teste l'appartenance d'un élément à un ensemble.
• StringSet.remove : string -> StringSet.t -> StringSet.t qui retourne un ensemble privé d'un élément.
• StringSet.singleton : string -> StringSet.t qui construit un singleton à partir d'un élément.
• StringSet.union : StringSet.t -> StringSet.t -> StringSet.t qui construit l'union de deux ensembles.

• si l'arbre d'analyse a est de la forme V v , où v ∈ L(G_0), alors VL(a) est le singleton {v};
• si l'arbre d'analyse a est de la forme A (a1, a2), où a_1 et a_2 sont deux arbres d'analyse, alors VL(a) est la réunion VL(a_1) ∪ VL(a_2);
• si l'arbre d'analyse a est de la forme F (v, a1), où v ∈ L(G_0) et a_1 est un arbre d'analyse, alors VL(a) est l'ensemble VL(a_1)∖{v}.
  ◻29 - Écrire une fonction OCaml free_vars (a : ada) : StringSet.t dont la valeur de retour est l'ensemble des variables libres de l'arbre d'analyse a.

Nous déclarons un nouveau type
type tdb = Vdb of int | Adb of ( tdb∗tdb ) | Fdb of tdb
Nous notons 𝒯 l'ensemble des termes de De Bruijn.
Voici un exemple de construction d'un terme de De Bruijn (à droite) à partir d'un arbre d'analyse (à gauche) du mot
(aa#->ab#->ba#->bb#->(ab#((bb#aa#)ab#))bb#->(bb#aa#->(bb#->bb#aa#))):

• si le terme t ∈ 𝒯 est de la forme Vdb u, avec u ∈ ℕ^⋆, alors tˆ est la chaîne de caractères 11..10 (avec le symbole 1 répété u fois).
• si le terme t ∈ 𝒯 est de la forme Adb(t1, t2), t_1 et t_2 étant deux termes de De Bruijn, alors t^ est la chaîne de caractères 01t_1^t_2^.
• si le terme t ∈ 𝒯 est de la forme Fdb t1, où t_1 est un terme de De Bruijn, alors tˆ est la chaîne de caractères 00t_1 ˆ.
  ◻32 - Soient n un entier naturel et t le terme de De Bruijn associé au mot ⌈n⌉ et obtenu à la question 30. Calculer la longueur |t^| de la chaîne de caractères qui encode t.
  ◻33 - Vérifier que le codage binaire des termes de De Bruijn est une application injective.
  Nous utilisons le type string avec les caractères '0' et '1' afin de représenter des codages binaires de termes de De Bruijn.

4.3 Interpréteur et décompresseur de De Bruijn

• Si l'arbre b ∈ 𝒜 est de la forme V v1, avec v_1 ∈ L(G_0), alors

• Si l'arbre b ∈ 𝒜 est de la forme A (b1, b2), où b_1 ∈ 𝒜 et b_2 ∈ 𝒜 sont deux arbres d'analyse, alors

• Si l'arbre b ∈ 𝒜 est de la forme F(v1, b1), avec v_1 ∈ L(G_0) et b_1 ∈ 𝒜, alors

• Si l'arbre a ∈ 𝒜 est de la forme V v , où v ∈ L(G_0), alors la valeur ▹(a) n'est pas définie.
• Si l'arbre a ∈ 𝒜 est de la forme A (a1, a2), où a_1 ∈ 𝒜 et a_2 ∈ 𝒜 sont deux arbres d'analyse, alors

• Si l'arbre a ∈ 𝒜 est de la forme F (v, a1), où v ∈ L(G_0) et a_1 ∈ 𝒜, alors

let decompB (z : string) : string =
    "string_of_int }\mp@subsup{}{|}{}(int\_of_ada\sqcup(interpret\lrcorner(ada_of_tdb\lrcorner(decodeப" ^ z ^ "))))"

Fin de l'épreuve