Corrigé X-ENS 2026 Informatique A MP — Partie I (I.1 à I.10) : Reconnaissance d'extraits musicaux : vecteurs de bits, signatures, minHash

I.1. C'est la recherche d'un motif dans un texte, sur l'alphabet des colonnes : une colonne du spectrogramme est un mot de $F$ caractères, la musique est un texte de $T$ colonnes et l'extrait un motif de $D$ colonnes. L'extrait figure dans la musique s'il existe un décalage $s\in \{0,\dots ,T-D\}$ tel que pour tous $t\in [D]$ et $f\in [F]$, la case $(f,t)$ de l'extrait est égale à la case $(f,s+t)$ de la musique.

La recherche naïve essaie les $T-D+1$ décalages et, pour chacun, compare au plus $D$ colonnes de $F$ cases, en s'arrêtant à la première différence : au plus $(T-D+1)DF$ comparaisons, soit une complexité en $O((T-D+1)DF)$, donc en $O(TDF)$. Cette borne est atteinte : une musique silencieuse (que des espaces) et un extrait silencieux sauf sa dernière case $(F-1,D-1)$ font comparer, pour chaque décalage, $DF$ cases avant de trouver la différence, soit exactement $(T-D+1)DF$ comparaisons. Pour $D\le T/2$, c'est $\Theta (TDF)$.

I.2. On parcourt toutes les cases en ajoutant en tête de liste ; en balayant les instants décroissants, la liste obtenue est triée par instants croissants (puis par fréquences croissantes), ce qui servira en I.8.

let to_sparse (s : spectrogram) : sparse =
  let nf = Array.length s in
  if nf = 0 then []
  else begin
    let nt = Array.length s.(0) in
    let acc = ref [] in
    for t = nt - 1 downto 0 do
      for f = nf - 1 downto 0 do
        if s.(f).(t) = 'x' then acc := (f, t) :: !acc
      done
    done;
    !acc
  end

Chaque case est lue une fois et produit au plus une cellule de liste : complexité $O(FT)$. Invariant de la boucle externe : après le traitement de l'instant $t$, !acc est la liste des cases 'x' d'instant au moins $t$, dans l'ordre croissant. Sur la matrice de la figure 1 (en numérotant les fréquences de bas en haut, comme le clavier), la fonction renvoie [(0,0); (1,1); (2,2); (0,3); (0,4); (1,5); …; (2,14); (4,14)], 20 couples.

I.3. L'élément $i$ correspond à l'entier $2^i$, c'est-à-dire 1 lsl i ; on réunit ces bits par un « ou » bit à bit.

let convert (l : int list) : int =
  List.fold_left (fun acc i -> acc lor (1 lsl i)) 0 l

Par récurrence sur la longueur du préfixe déjà traité, l'accumulateur code l'ensemble des éléments de ce préfixe : acc lor (1 lsl i) met à 1 le bit $i$ sans toucher aux autres. Comme la liste est sans doublons, on pourrait aussi bien additionner les $2^i$. Pour $i\le 61$, $2^i\le 2^{61}$ reste un entier positif sur 63 bits. Complexité $O(k)$ pour une liste de longueur $k$. Exemple exécuté : convert [0; 2; 5] vaut $1+4+32=37$.

I.4. Un élément est dans l'intersection si et seulement si son bit vaut 1 dans les deux codes : c'est le « et » bit à bit.

let inter (a : int) (b : int) : int = a land b

Temps constant ; par exemple inter 6 3 vaut 2 ($\{1,2\}\cap \{0,1\}=\{1\}$).

I.5. (a) À chaque tour, on retire de $b$ son bit à 1 de plus faible poids, isolé par b land (-b), et l'on compte les tours.

let size (n : int) : int =
  let b = ref n and c = ref 0 in
  while !b <> 0 do
    b := !b - (!b land (- !b));
    incr c
  done;
  !c

Justification de l'indication. Si $b\ne 0$ s'écrit en binaire $u10^j$ (le bit $j$ est son bit à 1 de plus faible poids), le complément à deux donne $-b=\overline{b}+1$, où $\overline{b}=\overline{u}01^j$, donc $-b=\overline{u}10^j$. Le « et » avec $b$ vaut $0\cdots 010^j=2^j$. Donc b - (b land (-b)) vaut $u00^j$ : c'est $b$ privé de son bit $j$.

Complexité : chaque tour retire exactement un bit à 1 ; si l'ensemble codé par $n$ a $s$ éléments, la boucle fait exactement $s$ tours, chacun en $O(1)$ (une négation, un « et », une soustraction, un test, une incrémentation). La complexité est $O(s+1)$, linéaire en la taille de l'ensemble (et non en 62, comme un parcours de tous les bits).

(b) Notons $E(x)$ l'ensemble codé par l'entier $x\ge 0$. Invariant : $E(b)\subset E(n)$ et $c+|E(b)|=|E(n)|$. Il est vrai à l'entrée ($b=n$, $c=0$). Si $b\ne 0$ avant un tour, soit $j=\min E(b)$ : d'après (a), le tour remplace $b$ par le code de $E(b)\setminus \{j\}$ (donc $E(b)$ reste inclus dans $E(n)$ et perd exactement un élément) et augmente $c$ de 1 : l'invariant est conservé. Terminaison : $|E(b)|$ est un entier naturel qui décroît strictement à chaque tour. À la sortie, $b=0$ donc $E(b)=\varnothing$ et l'invariant donne $c=|E(n)|$ : la fonction renvoie le cardinal. Vérifié sur 1000 parties aléatoires de $[62]$, sur $0$ et sur $[62]$ tout entier (résultat 62).