Analyse du sujet d'Informatique A X/ENS/ESPCI 2026 : bases de données de vecteurs, listes à sauts et quantification de produit

Partie I : Reconnaissance automatique d'extraits musicaux

La représentation des musiques et la similarité de Jaccard

La première partie aborde la reconnaissance automatique de musique, une application concrète des bases de données de vecteurs. Le point de départ est le spectrogramme d'une musique, représenté en OCaml par une matrice de caractères de type char array array. La case (f, t) de cette matrice vaut le caractère 'x' si et seulement si la musique contient une note à la fréquence f au temps t.

La question I.1 demande une analyse de complexité sans code : étant donné un extrait de durée D et une musique de durée T avec T > D, à quel problème classique se ramène la détermination si l'extrait est présent dans la musique, et quelle est la complexité dans le pire cas ? Il s'agit d'une recherche naïve de sous-chaîne bidimensionnelle, dont la complexité est en O(F * T * F * D), ce qui se simplifie en O(F² * T * D) selon les notations du sujet, F étant le nombre de fréquences possibles. Les candidats qui ont reconnu cette structure de recherche de motif et su en exprimer la complexité rigoureusement disposaient d'un bon point de départ.

Les questions I.2 à I.6 introduisent la représentation concise (sparse) du spectrogramme, qui ne liste que les cases non vides, et l'indice de Jaccard entre deux ensembles A et B, défini comme le quotient de la taille de leur intersection par la taille de leur union. La question I.2 demande d'écrire la fonction to_sparse qui convertit un spectrogramme en représentation concise, exercice direct de parcours de tableau. La question I.3 demande d'écrire convert qui représente un sous-ensemble de [62] comme un entier OCaml par encodage de vecteur de bits, en utilisant le décalage à gauche lsl. La question I.4 demande inter, le ET bit à bit de deux tels entiers, ce qui donne directement l'encodage de l'intersection.

La question I.5 est la plus technique de cette sous-partie : elle demande d'écrire size, qui compte le nombre de bits à 1 dans un entier OCaml encodant un ensemble, avec une complexité linéaire dans la taille de l'ensemble représenté (et non dans le nombre de bits total). La partie (a) demande le code avec justification de complexité, et la partie (b) demande de prouver la correction par un invariant. L'indication fournie sur l'opération b land (-b), qui isole le bit de poids faible, guidait vers une boucle qui retire un bit à 1 à chaque itération, donnant une complexité proportionnelle au nombre de bits à 1. Cette question demandait une rigueur de raisonnement que peu de candidats mobilisent spontanément en conditions d'examen.

La question I.6 demande sparse_inter, qui calcule le nombre d'éléments communs dans deux listes triées en ordre strictement croissant, avec une complexité linéaire dans la longueur des deux listes. L'algorithme attendu est le classique à deux pointeurs sur listes triées, bien connu des candidats ayant travaillé les algorithmes de fusion.

Les signatures musicales et le minHash

Les questions I.7 et I.8 introduisent la notion de signature d'une musique, définie comme l'ensemble des triplets (f1, f2, delta) tels que la fréquence f1 est présente au temps t et la fréquence f2 est présente au temps t + delta pour un certain t. La question I.7 demande d'implémenter tosignature avec une complexité en O(n²) où n est la longueur de la représentation concise, en convertissant d'abord cette représentation en tableau de paires. La question I.8 est plus subtile : elle demande signature_size, qui calcule la taille de la signature par un seul parcours de l'argument, en supposant la représentation concise triée par l'ordre lexicographique et tous les ti distincts. L'indication de se servir d'une file était décisive : en maintenant dans une file les fréquences encore actives au temps courant et en la vidant au fur et à mesure, on peut compter les triplets sans les énumérer explicitement.

La question I.9 est une question d'analyse sans code : étant donné un extrait M et deux musiques A et B ayant chacune trois triplets en commun avec la signature de M, laquelle des deux musiques correspond le mieux à M ? La réponse repose sur les histogrammes fournis en figure 2 : pour A, les trois triplets partagés ont des décalages temporels proches de 0 (les notes apparaissent au même moment dans M et dans A), ce qui indique une vraie correspondance, tandis que pour B les décalages sont élevés et dispersés (les triplets sont partagés mais les musiques ne sont pas alignées dans le temps). La musique A correspond donc bien mieux à M.

La question I.10, qui clôt la première partie, introduit la méthode minHash pour comparer des ensembles par hachage. La partie (a) demande de démontrer que si h est une numérotation aléatoire des éléments de E, alors la probabilité que minHash(h)(A) égale minHash(h)(B) est exactement l'indice de Jaccard J(A, B). La preuve repose sur le fait que le minimum d'une permutation aléatoire sur A ∪ B est également dans A ∩ B si et seulement si l'élément de rang minimal dans A ∪ B appartient à A ∩ B, événement de probabilité |A ∩ B| / |A ∪ B|. La partie (b) demande d'en déduire une méthode pour trouver les musiques les plus proches d'un extrait audio, en utilisant plusieurs fonctions de hachage indépendantes pour approcher l'indice de Jaccard sans calculer explicitement la signature complète. Cette question de synthèse récompensait les candidats ayant compris la logique probabiliste de la partie.

Partie II : Listes à sauts et graphes hiérarchiques navigables

Les listes à sauts : structure et algorithmes

La deuxième partie est la plus algorithmiquement riche du sujet. Elle s'ouvre sur les skip lists (listes à sauts), une structure de données probabiliste qui généralise les listes chaînées triées en ajoutant des pointeurs à plusieurs étages pour accélérer la recherche. Chaque noeud contient une valeur entière strictement positive et un tableau de successeurs, un par étage. La présence d'une valeur à un étage implique sa présence à tous les étages inférieurs.

La question II.1 demande d'écrire skip_length, qui compte le nombre de valeurs dans la skip list (sans compter le noeud factice de valeur 0). C'est un simple parcours de la liste chaînée à l'étage 0, exercice direct.

La question II.2 est une question d'analyse probabiliste : si la skip list contient n valeurs et que chaque valeur est présente à l'étage l avec probabilité p^l (indépendamment), combien de valeurs sont en moyenne présentes à l'étage l ? La réponse est n * p^l, par linéarité de l'espérance. Cette question préparait le terrain pour l'analyse de complexité de la recherche.

La question II.3 est centrale dans la partie : elle demande d'écrire la fonction search qui détermine si une valeur v est présente dans la skip list en partant du noeud factice à l'étage init_level et en exploitant les successeurs de chaque étage pour avancer aussi loin que possible avant de descendre. La partie (a) demande le code, la partie (b) la correction (invariant de recherche : la valeur cherchée est dans l'intervalle entre le noeud courant et son successeur à l'étage courant, ou absente), et la partie (c) la complexité dans le pire cas. La complexité dans le pire cas est O(n * L) où n est le nombre de valeurs et L le nombre d'étages, mais l'intérêt de la structure est sa complexité moyenne.

Les questions II.4 et II.5 établissent la complexité moyenne de recherche. La question II.4 introduit le chemin inversé de la recherche et définit C_l comme le nombre moyen d'étapes pour remonter de l'étage 0 à l'étage l dans tout chemin de recherche inversé. Elle demande de montrer par récurrence que C_l = l/p, où p est le paramètre de la fonction random_level. La question II.5 en déduit que le nombre d'étapes en moyenne d'une recherche dans une skip list à n valeurs est O(log n), résultat central de la théorie des skip lists qui explique leur intérêt pratique. Ces deux questions demandaient une rigueur probabiliste inhabituelle en prépa et constituaient un vrai point de différenciation.

La question II.6 demande d'écrire la fonction insert qui insère une valeur absente dans la skip list. La partie (a) demande combien de successeurs il suffit de modifier au maximum (L successeurs, un par étage où le nouveau noeud est présent). La partie (b) demande le code, en signalant que l'essentiel consiste à identifier les prédécesseurs du nouveau noeud à chaque étage concerné, puis à insérer le nouveau noeud entre chacun d'eux et leur successeur actuel.

Des listes à sauts aux graphes hiérarchiques navigables

La suite de la partie II généralise la structure de skip list aux graphes hiérarchiques non orientés, où la relation de voisinage est définie à plusieurs étages. Un graphe hiérarchique G = (V_l, E_l)_{0<=l<L} à n noeuds est représenté en OCaml par une matrice de listes d'adjacence de taille n × L. Si un noeud est présent à un étage, il est présent à tous les étages inférieurs. Les coordonnées des vecteurs associés aux noeuds sont données par la matrice db.

La question II.7 demande d'écrire closest, qui trouve l'indice dans db du vecteur candidat le plus proche d'un vecteur requête query en utilisant une méthode de recherche gloutonne dans le graphe hiérarchique. La méthode gloutonne part d'un noeud de départ à l'étage le plus haut, choisit à chaque tour le voisin à l'étage courant qui réduit strictement la distance à query, et descend à l'étage inférieur lorsqu'aucun voisin ne réduit la distance. La partie (a) demande le code, la partie (b) la complexité en fonction de n, |E|, L et d, et la partie (c) demande si des marquages de noeuds sont nécessaires pour garantir la terminaison. La réponse est non : le graphe est non orienté et chaque étape réduit strictement la distance, ce qui assure la terminaison sans cycle.

Partie III : Quantification de produit

L'algorithme des k-moyennes et ses composants

La troisième partie aborde la quantification de produit, une technique d'approximation de la distance euclidienne entre vecteurs de grande dimension. La partie s'ouvre par l'implémentation de l'algorithme des k-moyennes, dont les composants sont demandés un par un.

La question III.1 demande d'écrire compute_all_dist2 qui calcule la matrice carrée des carrés des distances euclidiennes entre tous les vecteurs de db, en utilisant Array.init_matrix et la fonction dist2 fournie. C'est une question directe de programmation matricielle.

La question III.2 demande la complexité de la recherche du plus proche voisin parmi n éléments de db pour un vecteur requête donné. La réponse est O(n * d) où d est la dimension des vecteurs, puisqu'il faut calculer la distance à chacun des n vecteurs, chaque calcul étant en O(d). Cette question ne demandait pas de code.

Les questions III.3 à III.6 construisent les briques de l'algorithme des k-moyennes. La question III.3 demande pick, qui pour chaque vecteur de db met à jour le tableau centroid_of avec l'indice du centroïde le plus proche. La question III.4 demande update, qui calcule les k nouveaux centroïdes comme la moyenne des vecteurs affectés à chaque centroïde. La question III.5 soulève une subtilité : est-il possible qu'update mette à jour moins de k centroïdes ? Oui, si aucun vecteur n'est affecté à un centroïde donné, celui-ci ne peut pas être recalculé comme moyenne. La question III.6 assemble le tout dans kmeans, qui effectue n_iteritérations de l'algorithme des k-moyennes en initialisant les centroïdes sur les k premiers vecteurs de db.

La quantification de produit et le gain du précalcul

La partie finale introduit la quantification de produit proprement dite. L'idée est de diviser chaque vecteur de dimension d en m paquets disjoints de taille d/m, d'appliquer l'algorithme des k-moyennes sur chaque paquet séparément pour obtenir k centroïdes par paquet, puis d'approcher chaque vecteur par la liste des indices de ses m centroïdes les plus proches. La distance approchée entre deux vecteurs est la somme sur les m paquets des distances au carré entre les centroïdes correspondants.

La question III.7 demande d'écrire approx_dist qui calcule la matrice des distances approchées entre tous les vecteurs de db. La fonction utilise submatrix (fournie) pour extraire les m sous-matrices correspondant aux m paquets, puis appelle kmeans sur chacun et combine les résultats.

La question III.8 porte sur le précalcul des valeurs d_l(a, b), le carré de la distance euclidienne entre le a-ième et le b-ième centroïde dans le l-ième paquet, pour toutes les paires (l, a, b). La partie (a) demande la complexité en temps de ce précalcul en fonction de k, d et m : il y a m * k² paires à calculer, chaque calcul prenant O(d/m), ce qui donne O(k² * d). La partie (b) demande de borner le nombre de valeurs distinctes que peuvent prendre les D'_ij pour (i, j) dans [n]² : chaque D'_ij est une somme de m termes, chacun prenant k² valeurs possibles, ce qui borne le nombre de valeurs distinctes par (k²)^m = k^(2m). La partie (c) demande la complexité de la recherche des plus proches voisins de db.(i) parmi les vecteurs de db une fois le précalcul effectué : elle est en O(m * n) puisque pour chaque vecteur candidat, la distance approchée se calcule en O(m) consultations du dictionnaire précalculé. La partie (d) généralise à un nouveau vecteur p extérieur à db, pour lequel il faut d'abord calculer les indices de centroïdes correspondants (en O(m * k * d/m) = O(k * d)) avant d'appliquer la même procédure, donnant une complexité totale en O(k * d + m * n).