Informatique A

Notations et définitions.

Pour tout $n \in \mathbb{N}$, on note $[n]=\{0,\ldots,n-1\}$.

Le logarithme noté $\log$ est en base deux.

Les complexités sont des majorations dans le pire cas, sauf lorsqu’une espérance est explicitement étudiée.

Les programmes sont écrits en OCaml.

Une opération élémentaire sur un entier machine, un accès à un tableau et chacune des opérations sur les files rappelées dans le sujet ont un coût constant.

En particulier, Queue.length a un coût constant.

Les entiers ont une représentation sur $63$ bits ; les entiers positifs utilisent les $62$ bits de poids faible.

Soient $F \in \mathbb{N}^*$ et $T \in \mathbb{N}$.

Une musique $M$ de durée $T$ est représentée par un tableau de $F$ lignes et de $T$ colonnes.

Pour tout $(f,t)\in[F]\times[T]$, la case de coordonnées $(f,t)$ contient 'x' exactement lorsqu’une note de fréquence $f$ est présente au temps $t$.

La représentation concise contient les couples correspondant aux cases marquées, sans répétition.

Pour deux ensembles finis non vides $A$ et $B$, l’indice de Jaccard est défini par

Dans QI.3 à QI.5, un ensemble $A\subset[62]$ est représenté par l’entier

Pour les listes de QI.6, les éléments sont rangés dans l’ordre strictement croissant.

Les comparaisons entre éléments ont un coût constant.

Soit $\Delta\in\mathbb{N}^*$.

La signature $S_\Delta(M)$ est l’ensemble des triplets $(f_1,f_2,\delta)$ obtenus à partir de deux notes $(f_1,t)$ et $(f_2,t+\delta)$, avec $0<\delta\le\Delta$.

Un même triplet peut provenir de plusieurs couples de notes ; il ne constitue qu’un élément de cet ensemble.

Dans QI.8, la représentation concise est rangée par temps strictement croissants.

Tous les temps sont des entiers distincts.

Pour QI.9, chaque musique est représentée par un dictionnaire dont les clés sont les triplets de sa signature.

La valeur associée à une clé regroupe les temps de début des occurrences de ce triplet.

L’extrait $M$ et les deux musiques $A$ et $B$ vérifient

Pour tout $i\in\{1,2,3\}$, on note $t_i\in\mathbb{N}$ le temps de début dans $M$ de la correspondance considérée, et $t_i'^{(A)}\in\mathbb{N}$ et $t_i'^{(B)}\in\mathbb{N}$ les temps de début correspondants dans $A$ et dans $B$.

Les histogrammes comparent respectivement les trois écarts absolus $|t_i-t_i'^{(A)}|$ et les trois écarts absolus $|t_i-t_i'^{(B)}|$.

Enfin, soient $N\in\mathbb{N}^*$ et $E=[N]$.

Pour une application $h:E\to[N]$ et une partie non vide $A\subset E$, on pose

Dans QI.10 a), $h$ est choisie uniformément parmi les permutations de $E$.