X-ENS 2026 MP Informatique A : sujet en PDF
Sujet de l'épreuve de Informatique A du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2026, filière MP, en 4 heures. Thème : Bases de données de vecteurs : reconnaissance d'extraits musicaux, listes à sauts et quantification de produit.
Ce que traite le sujet, partie par partie
- Partie I. Reconnaissance automatique d'extraits musicaux. Spectrogrammes creux, ensembles codés en vecteurs de bits, intersection et cardinal par opérations bit à bit avec invariant, intersection de listes triées, signatures en triplets calculées avec une file, indice de Jaccard et méthode minHash.
- Partie II. Listes à sauts et graphes hiérarchiques navigables. Listes chaînées triées à plusieurs étages, nombre moyen de valeurs par étage, recherche et coût moyen logarithmique par une récurrence, insertion, puis recherche gloutonne du plus proche voisin dans un graphe hiérarchique.
- Partie III. Quantification de produit. Matrice des distances, plus proche voisin naïf, algorithme des k-moyennes, découpage des vecteurs en sous-vecteurs quantifiés pour approcher les distances et gain apporté par un précalcul des tables de distances.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Architecture de l'ordinateur et représentation des nombres
- Espaces probabilisés
- Piles, files et deques
- Variables aléatoires discrètes
- Complexité des algorithmes itératifs et récursifs
- Apprentissage automatique : k plus proches voisins et k-moyennes
Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.