X-ENS 2024 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 2024, filière MP, en 4 heures. Thème : Arbres AVL et localisation d'un point dans une subdivision du plan.
Ce que traite le sujet, partie par partie
- Partie I. Préliminaires. Arbres binaires de recherche, dénombrement des arbres à trois éléments, caractérisation récursive, condition d'équilibre AVL, majoration logarithmique de la hauteur et recherche d'un élément en O(log n).
- Partie II. Construire des arbres AVL. Étude de la fonction join et des rotations : terminaison, hauteur du résultat, équilibre et complexité. Insertion par découpage split puis join, partage de mémoire entre arbres persistants, puis suppression via l'extraction du maximum et la concaténation.
- Partie III. Application : localisation d'un point dans le plan. Découpage du plan en tranches verticales aux abscisses des sommets, arêtes ordonnées dans chaque tranche par un AVL, construction des tranches en O(N log N) et double recherche dichotomique pour trouver la zone d'un point.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Complexité des algorithmes itératifs et récursifs
- Spécifier, tester, prouver : terminaison et correction
- Listes et algorithmes de recherche (séquentielle, dichotomique)
- Tri par fusion et tri rapide
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.