2024-Mines-Info-Mpi2-Corrigé

Préliminaires

L’épreuve est composée d’un problème unique, comportant 36 questions. Le problème est divisé en quatre sections. Dans la première section (page 1), nous introduisons une forme paresseuse de listes, les flots de données, et construisons quelques fonctions de base utiles tout au long du sujet.

Dans la deuxième section (page 4), nous nous intéressons à un algorithme de détermination à la volée du cardinal d’un flot, dont l’inspiration est probabiliste. Dans la troisième section (page 7), nous nous appuyons sur des raisonnements de logique pour analyser le chiffrement par flot.

Dans la quatrième section (page 9), nous traitons quelques questions de combinatoire énumérative à l’aide d’une grammaire ou simplement d’un procédé manuel de dérécursification. Les sections 2, 3 et 4 peuvent être vues comme des exercices indépendants qui ne dépendent que de la première section.

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 portant sur des extraits du manuel de documentation de OCaml et sur les règles de la déduction naturelle sont fournis en annexe.

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 : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.

Les termes de la suite de Fibonacci {(F_n)_{n\in\mathbb N}} obéissent aux relations : {F_0=0,\quad F_1=1,\quad\forall n\in\mathbb N,\ F_{n+2}=F_n+F_{n+1}.} Nous nous enhardissons à définir la liste des termes de la suite de Fibonacci {(F_n)_{n\in\mathbb N}} en écrivant la déclaration récursive suivante :

Cependant, à l’évaluation de cette expression par un interpréteur (ou toplevel ou encore REPL), le système renvoie le message d’erreur suivant :

Nous recopions le code fautif dans un fichier fibo.ml et — horresco referens — nous nous apprêtons à appeler successivement depuis un terminal les commandes ocamlopt fibo.ml -o fibo pour la compilation de la source vers un exécutable puis ./fibo pour l’exécution.

1.2. Définition des flots de données

Définition : Un flot de données est une suite, finie ou infinie, d’éléments de même type. Indication OCaml : Afin de représenter les flots de données, nous fixons le type suivant :

Le constructeur Nil qualifie le flot vide.

Définir la suite infinie constante égale à 1 en tant que int stream demeure possible. Nous parvenons de surcroît à déclarer la suite de Fibonacci en tant que int stream sans encombre. En voici le code :

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

Nous nous proposons d’écrire une fonction product (u1 : ’a stream) (u2 : ’b stream) : (’a * ’b) stream dont la valeur de retour est un flot qui énumère tous les couples tirés du flot {u_1} et du flot {u_2} dans un ordre non spécifié. Nous écrivons le code suivant :

1.4. Filtre d’un flot

Pour répondre à la question 17, on pourra admettre sans justification l’existence d’une machine universelle à chronomètre, c’est-à-dire une fonction OCaml run : string -> int -> int qui se termine toujours et telle que : — si la chaîne de caractères x est le code source d’une expression OCaml et si l’exécution du code x se termine sans erreur en moins de n é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.

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

Définition : Nous appelons cardinal d’un flot de données le cardinal de l’ensemble des valeurs distinctes appartenant à ce flot. Ce cardinal peut être fini même si le flot est infini.

Dans cette section, nous cherchons à estimer le cardinal s d’un flot de chaînes de caractères {(u_n)_{n\in\mathbb N}} de cardinal fini avec peu de mémoire et en supposant que {0\le s\lt2^{62}}.

Définition : Nous appelons premier bit activé d’un entier {h\in\{0,\ldots,2^{62}-1\}}, et notons {\varrho(h)}, le plus grand entier {i} tel que les {i-1} bits les plus à droite dans la représentation binaire de {h} sont tous nuls. Par convention, nous fixons {\varrho(0)=63}.

Par exemple, nous avons {\varrho(1)=\varrho(00001_{(2)})=1}, {\varrho(6)=\varrho(00110_{(2)})=2}, ou encore {\varrho(8)=\varrho(01000_{(2)})=4}.

Indication OCaml : Nous disposons d’une fonction de hachage H à valeur dans l’intervalle entier {\{0,\ldots,2^{62}-1\}} que nous réalisons à l’aide de String.hash : string -> int. Soit s un entier naturel non nul.

Nous tirons s chaînes de caractères aléatoirement et notons {(H_j)_{1\le j\le s}} leur haché par la fonction de hachage H. Pour tout indice j compris entre 1 et s, nous supposons que chaque variable aléatoire {H_j} est distribuée selon une loi uniforme dans l’intervalle entier {\{0,\ldots,2^{62}-1\}}.

Nous posons {R=\max_{1\le j\le s}\varrho(H_j).} Une analyse mathématique, que nous admettons, montre alors que les variables aléatoires {\varrho(H_j)} sont tirées selon des lois géométriques et que la variable {R} est proche de {\log_2s}, si bien que la quantité {2^R} est une bonne approximation de s.

Soit {(u_n)_{n\in\mathbb N}} un flot de chaînes de caractères de cardinal s, l’entier s étant inconnu.

Nous proposons deux algorithmes qui estiment le cardinal s par l’observation des t premiers termes du flot, en supposant que les s valeurs distinctes apparaissent parmi les t premiers termes. — Algorithme naïf : garnir à la volée une table de hachage avec les chaînes {(u_n)_{n\le t}}, puis renvoyer le compte des éléments présents dans la table.

En voici le code :

où l’on réutilise la fonction iter de la question 10 et des fonctions du module Hashtbl rappelées en annexe. — Algorithme de Flajolet-Martin, inspiré par les observations ci-dessus. En voici le code :

Nous rappelons que la moyenne harmonique de m réels {z_1,\ldots,z_m} strictement positifs se calcule par la formule {\operatorname{Harm}(z_1,\ldots,z_m)=m\left(\sum_{j=1}^m\frac1{z_j}\right)^{-1}.}

La suite de chaînes de caractères {(u_n)_{n\in\mathbb N}} et l’entier m étant fixés, pour tout entier i compris entre 0 et m − 1 et pour tout entier naturel t, nous notons {U_t^i} l’ensemble de chaînes de caractères {U_t^i=\{u_n\text{ où }n\le t\text{ et }H(u_n)\equiv i\pmod m\}.} Afin d’obtenir une estimation de cardinal du flot {(u_n)_{n\in\mathbb N}} plus robuste et de diminuer la variabilité associée à l’unicité du point de mesure, nous proposons une amélioration de la fonction cardinality_fm qui utilise un effet de moyenne. — Algorithme HyperLogLog : Nous divisons les premiers termes du flot {(u_n)_{n\in\mathbb N}} en {m} sous-flots disjoints {U_t^0,\ldots,U_t^{m-1}}.

Nous estimons le cardinal de chaque sous-flot comme le fait l’algorithme de Flajolet-Martin et obtenons des valeurs {(2^{r_i})_{0\le i\le m-1}}, où {r_i=\max_{u\in U_t^i}\varrho(H(u)/m),} qui, intuitivement, forment chacune une estimation grossière du quotient s/m.

Nous calculons la moyenne harmonique {\operatorname{Harm}(2^{r_0},\ldots,2^{r_{m-1}})}, qui, intuitivement, constitue une estimation robuste du quotient s/m. Une analyse mathématique poussée confirme notre intuition.

Il s’avère que le cardinal s est très bien approché par la quantité {s\simeq\alpha_m\,m\,\operatorname{Harm}(2^{r_0},\ldots,2^{r_{m-1}})\quad(\clubsuit)}où {\alpha_m} est une constante, valant ici {\alpha_m=\left(m\int_0^\infty\left(\log_2\frac{2+u}{1+u}\right)^m\mathrm du\right)^{-1}.}On utilisera l’équation {(\clubsuit)} sans la démontrer durant l’épreuve.

Indication OCaml : Nous fixons les constantes globales pour le reste de la section 2.

L’algorithme HyperLogLog se présente alors sous la forme

où les fonctions hll_update et mean_estimate seront écrites aux questions 21 et 22.

Nous nous plaçons finalement dans la situation où deux flots de chaînes de caractères {(u_n)_{n\in\mathbb N}} et {(v_n)_{n\in\mathbb N}} nous parviennent simultanément.

Nous chargeons deux fils d’exécution auxiliaires distincts de construire indéfiniment leurs tableaux respectifs de maxima de bit activés tandis que le fil d’exécution principal déclenche toute les cinq secondes l’affichage du cardinal.

Voici une ébauche de code :

dans laquelle Int.max_int représente le plus grand entier représentable.

3. Chiffrement par flot de booléens

Dans cette partie, nous nous appuyons sur des variables booléennes {(x_j)_{j\le k}} et sur les constantes {\top} (tautologie) et {\bot} (antilogie) pour former des formules, à l’aide des trois connecteurs {\neg} (négation), {\land} (conjonction) et {\lor} (disjonction).

Pour toutes formules de logique {\varphi} et {\psi}, nous notons X({\varphi}, {\psi}) la nouvelle formule {X(\varphi,\psi)=(\varphi\lor\psi)\land(\neg\varphi\lor\neg\psi).} Les règles d’inférence de la déduction naturelle sont rappelées dans l’annexe B.

Nous admettons que, pour toutes formules de logique {\varphi} et {\psi}, il existe des arbres de preuve qui démontrent les séquents {X(X(\varphi,\varphi),\psi)\vdash\psi} et {\psi\vdash X(X(\varphi,\varphi),\psi)}. Définitions : Nous notons B = {V, F } l’ensemble des valeurs de vérité.

Nous introduisons la fonction booléenne {\oplus} : {B\times B\to B} telle que {\oplus(x,y)} est l’évaluation de la formule X(x, y).

Nous admettons, plus généralement, que la fonction booléenne {\oplus} : {B\times B\to B} est commutative et associative. Pour tout entier {m\ge1} et pour tous booléens {(b_i)_{1\le i\le m}}, la somme {\bigoplus_{i=1}^m b_i} est définie comme {\oplus(\cdots\oplus(\oplus(b_1,b_2),b_3),\ldots,b_m)} mais peut être calculée dans n’importe quel ordre.

La somme vide vaut, par convention, la valeur de vérité F .

Définition : Nous appelons registre à décalage à rétroaction linéaire (ou encore LFSR d’après l’anglais linear feedback shift register ) de longueur {m}, de germe {(b_i)_{0\le i\lt m}\in B^m} et de connexion {C\subseteq\{0,\ldots,m-1\}}, le flot de booléens {(b_n)_{n\in\mathbb N}} défini par la relation de récurrence {\forall n\in\mathbb N,\quad b_{n+m}=\bigoplus_{i\in C}b_{n+i}} Indication OCaml : Nous utilisons le type bool array pour représenter le germe et le type int list pour représenter la connexion d’un LFSR.

La longueur s’obtient avec Array.length.

Indication OCaml : Nous représentons les formules de logique à l’aide du type

Pour toute formule de logique {\varphi} définie à partir des variables booléennes {(x_j)_{1\le j\le k}} et pour tout k-upplet de valeurs de vérité {b=(b_1,\ldots,b_k)\in B^k}, nous notons {\varphi}(b1, . . . , bk) l’évaluation de la formule {\varphi} en b.

Dans la question 29, deux personnages, Alice et Bob, se sont accordés, lors de leur tout premier tête-à-tête et à l’abri de toute écoute par un tiers, au sujet de k germes et de k connexions de LFSR ainsi qu’au sujet d’une formule de logique {\psi_0(x_1,\ldots,x_k)}.

Nous notons {(b_n^{(1)})_{n\in\mathbb N}}, …, {(b_n^{(k)})_{n\in\mathbb N}} les {k} flots de données booléens associés aux LFRS. À présent, Alice souhaite communiquer à Bob la suite de bits {c=(c_n)_{n\in\mathbb N}} via un canal public. Elle transmet à Bob la suite des évaluations {(X(\psi_0(b_n^{(1)},\ldots,b_n^{(1)}),c_n))_{n\in\mathbb N}}.

4. Énumération d’objets combinatoires

4.1. Flot des mots de Dyck

Soit {\Sigma} l’alphabet binaire {\Sigma=\{a,b\}}. Nous nous intéressons à la constante OCaml dyck définie par le code suivant

où la fonction product a été introduite à la question 14. Nous notons {D\subseteq} {\Sigma^*} le langage constitué des mots appartenant au flot de données dyck.

4.2. Flot des permutations d’un tableau

Nous partageons une variante d’un algorithme dû à B. R. Heap sous la forme du pseudocode suivant. Dans ce pseudo-code, les positions de tableau sont numérotées à partir de l’indice 0.

Algorithme 1 : Algorithme de B. R. Heap Entrées : Entier k, tableau t de longueur {\ge k}. Effet : Effectue des échanges en place dans le tableau t et des affichages de t. Sortie : Aucune valeur de retour.

A. Annexe : rappels de programmation

(D’après https://v2.ocaml.org/api/index.html) Opérations générales : Le module Stdlib, chargé par défaut, offre les fonctions suivantes : — max : ’a -> ’a -> ’a Return the greater of the two arguments.

The result is unspecified if one of the arguments contains the float value nan. — float_of_int : int -> float Convert an integer to floating-point. — (lsl) : int -> int -> int n lsl m shifts n to the left by m bits.

Opérations sur les tableaux : Le module Array offre les fonctions suivantes : — make : int -> ’a -> ’a array make n x returns a fresh array of length n, initialized with x. — init : int -> (int -> ’a) -> ’a array init n f returns a fresh array of length n, with element number i initialized to the result of f (i). — 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).

Opérations sur les tables de hachage : Le module Hashtbl offre les fonctions suivantes : — create : int -> (’a, ’b) t Hashtbl.create n creates a new, empty hash table, with initial size n. — add : (’a, ’b) t -> ’a -> ’b -> unit Hashtbl.add t k d adds a binding of key k to data d in table t. — length : (’a, ’b) t -> int Hashtbl.length tt returns the number of bindings in t.

It takes constant time. Multiple bindings are counted once each.

Opérations sur les fils d’exécution : Le module Thread offre les fonctions suivantes : — create : (’a -> ’b) -> ’a -> t Thread.create f x creates a new thread of control, in which the function application f (x) is executed concurrently with the other threads of the domain.

The application of Thread.create returns the handle of the newly created thread. — delay : float -> unit delay d suspends the execution of the calling thread for d seconds. The other program threads continue to run during this time.

Opérations sur les verrous : Le module Mutex offre les fonctions suivantes : — create : unit -> t Return a new mutex. — lock : t -> unit Lock the given mutex. Only one thread can have the mutex locked at any time.

A thread that attempts to lock a mutex already locked by another thread will suspend until the other thread unlocks the mutex. — unlock : t -> unit Unlock the given mutex. Other threads suspended trying to lock the mutex will restart.

The mutex must have been previously locked by the thread that calls Mutex.unlock.

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

Dans les tableaux suivants, la lettre {\Delta} désigne un ensemble de formules de logique ; les lettres A, B et C désignent des formules de logique.