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

DEUXIÈME ÉPREUVE D'INFORMATIQUE

Durée de l'épreuve : 4 heures

Préliminaires

Travail attendu

1. Flots de données

1.1. Motivation

type 'a list = [] | (::) of 'a * 'a list

let list_finite = [ 1; 2; 3 ] (* liste finie a 3 elements *)
let rec list_ones = 1 :: list_ones (* liste infinie toute a 1 *)

let list_fibo : int list =
    let rec list_fibo_with_internal_state (a:int) (b:int) : int list =
        a :: (list_fibo_with_internal_state b (a+b))
    in
    list_fibo_with_internal_state 0 1

1.2. Définition des flots de données

type 'a stream = Nil | Cons of 'a * (unit -> 'a stream)

let rec (ones : int stream) = Cons (1, fun () -> ones)
let fibo : int stream =
    let rec fibo_with_internal_state a b =
        Cons (a, fun () -> fibo_with_internal_state b (a+b))
    in
    fibo_with_internal_state 0 1

1.3. Quelques manipulations de base des flots de données

let rec product_wrong u1 u2 =
    match u1,u2 with
    | _, Nil | Nil, _ -> Nil
    | Cons(hd1, tl_begetter1), Cons(hd2, tl_begetter2) ->
        let part1 = product_wrong (tl_begetter1 ()) u2 in
        let part2 = map (fun y -> (hd1, y)) (tl_begetter2 ()) in
        Cons((hd1, hd2), fun () -> intertwin part1 part2)

1.4. Filtre d'un flot

• si la chaîne de caractères est le code source d'une expression OCaml et si l'exécution du code se termine sans erreur en moins de étapes élémentaires de calcul, alors run x n a pour valeur de retour l'entier 0 ;
• sinon, run x n a pour valeur de retour l'entier 1.
  17 - Décrire la construction ou bien réfuter l'existence d'une fonction OCaml filter (f : 'a -> bool) (u : 'a stream) -> 'a stream dont la valeur de retour est formé des éléments du flot satisfaisant le prédicat , l'ordre des éléments de étant préservé. Par exemple, let is_negative in filter is_negative ones vaut Nil.

2. Estimation du cardinal d'un flot de données

• Algorithme naïf : garnir à la volée une table de hachage avec les chaînes , puis renvoyer le compte des éléments présents dans la table. En voici le code :

let cardinality_nf (t:int) (u: string stream) : float =
    let htb = Hashtbl.create 1 in
    iter (fun x-> Hashtbl.add htb x ()) t u;
    float_of_int (Hashtbl.length htb)

• Algorithme de Flajolet-Martin, inspiré par les observations ci-dessus. En voici le code :

let cardinality_fm (t:int) (u: string stream) : float =
    let r = ref 0 in
    let update x = r:= max !r (ffs (String.hash x)) in
    iter update t u;
    float_of_int (1 lsl !r) (* calcule 2^r en flottant *)

• Algorithme HyperLogLog : Nous divisons les premiers termes du flot en sous-flots disjoints . Nous estimons le cardinal de chaque sous-flot comme le fait l'algorithme de Flajolet-Martin et obtenons des valeurs , où

let m = 16
let alpha16 = 0.6731 (* calcul numerique admis *)

let cardinality_hll (t:int) (u : string stream) : float =
    let r = Array.make m 0 in
    iter (hll_update r) t u;
    mean_estimate r

let cardinality_threadedhll u v =
    let r_u = Array.make m 0 in
    let f1 () = iter (hll_update r_u) Int.max_int u in
    let _ = Thread.create f1 () in
    let r_v = Array.make m 0 in
    let f2 () = iter (hll_update r_v) Int.max_int v in
    let _ = Thread.create f2 () in
    while true do
        let r = Array.init m (fun i -> max r_u.(i) r_v.(i)) in
        print_float (mean_estimate r);
        Thread.delay 5. (* mise en pause de 5 secondes *)
    done

3. Chiffrement par flot de booléens

type formula = | Var of int
    | Not of formula
    | And of formula * formula
    | Or of formula * formula

4. Énumération d'objets combinatoires

4.1. Flot des mots de Dyck

let rec dyck =
    let f (x,y) = "a" ^ x ^ "b" ~ y in
    Cons("", fun () -> map f (product dyck dyck))

4.2. Flot des permutations d'un tableau

Algorithme 1 : Algorithme de B. R. Heap
    Entrées : Entier $k$, tableau $t$ de longueur $\geqslant k$.
    Effet : Effectue des échanges en place dans le tableau $t$ et des
            affichages de $t$.
    Sortie : Aucune valeur de retour.
    si $k=1$ alors
        Afficher le tableau $t$.
    sinon
        pour $i=0$ à $k-1$ (inclus) faire
            Exécuter Heap $((k-1), t)$.
            si $k$ est pair alors
                Échanger $t[i]$ et $t[k-1]$
            sinon
                Échanger $t[0]$ et $t[k-1]$

A. Annexe : rappels de programmation

• max : 'a -> 'a -> 'a

• float_of_int : int -> float

• (lsl) : int -> int -> int
  n lsl m shifts to the left by bits.

• make : int -> 'a -> 'a array
  make n x returns a fresh array of length , initialized with .
• init : int -> (int -> 'a) -> 'a array
  init n f returns a fresh array of length , with element number initialized to the result of .
• exists : ('a -> bool) -> 'a array -> bool
  exists f [|a1; ...; an |] checks if at least one element of the array satisfies the predicate. That is, it returns (f a1) || (f a2) || ... || (f an).

• create : int -> ('a, 'b)

• add : ('a, 'b) t -> 'a -> 'b -> unit

• length : ('a, 'b) t -> int

• create : ('a -> 'b) -> 'a -> t

• delay : float -> unit
  delay d suspends the execution of the calling thread for seconds. The other program threads continue to run during this time.

• create : unit -> t

• lock : t -> unit

• unlock : t -> unit

B. Annexe : règles de la déduction naturelle