Concours CPGE 2026 - X-ENS - Épreuve d’informatique - Filière MP – Bases de données de vecteurs / Cycles et unification

publié le 02 mai 2026 par Olivier TOURVIEILLE

MP X ENS Info 2026 - Bases de données de vecteurs

MP X ENS Info 2026 - Cycles et unification

Groupe principal

Description

INFORMATIQUE A

Bases de données de vecteurs

La partie I s’intéresse au cas des vecteurs de bits avec une application à la reconnaissance automatique d’extraits musicaux : la similarité entre deux tels vecteurs dépend du nombre de bits qu’ils ont en commun. La partie II s’intéresse à une structure de données appelée liste à sauts permettant la recherche efficace d’éléments à l’aide de pointeurs à plusieurs étages permettant d’accélérer la recherche. Dans cette partie, on s’intéresse aussi à la recherche de plus proches voisins dans des graphes hiérarchiques où chaque nœud correspond à un vecteur et le voisinage est défini à plusieurs étages. Enfin, la partie III s’intéresse à une approximation de la distance euclidienne entre deux vecteurs.

Partie I. Reconnaissance automatique d’extraits musicaux

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

Partie III. Quantification de produit

INFORMATIQUE B

Cycles et unification

Contexte

Soit G un graphe orienté dont les arcs sont étiquetés par des entiers naturels. On suppose que :

A0 : Les arcs sortants d’un sommet donné sont étiquetés par des entiers consécutifs en partant

de 0.

A1 : G est acyclique.

Le graphe G est représenté en Python par une variable globale G. C’est un dictionnaire dont

les clés sont les sommets et les valeurs sont des listes représentant les arcs sortants. L’étiquette

d’un arc correspond à son indice dans la liste. En particulier, les étiquettes des arcs sont implicites

et l’hypothèse A0 est automatiquement satisfaite. Dans ce problème, certaines des fonctions étudiées modifient G en ajoutant de nouveaux arcs. L’hypothèse A1 est un invariant qui sera maintenu en toute circonstance.

Organisation du sujet

La première partie étudie finement un parcours en profondeur pour pouvoir vérifier efficacement qu’un nouvel arc ne crée pas de cycles dans G. La deuxième partie étudie les notions de forme normale et d’unification dans G. Cette partie peut être traitée indépendamment de la première. La troisième partie étudie la notion de forme normale dans le contexte d’une base de données relationnelle.

Partie I. Détection de cycles

Partie II. Unification

Partie III. Représentation relationnelle

Le sujet et le corrigé de cette épreuve sont également disponibles sur le site de l’UPSTI (Union des Professeurs de Sciences et Techniques Industrielles) :

https://www.upsti.fr/espace-etudiants/annales-de-concours

Fichiers et liens