X-ENS 2022 PC Informatique B : sujet en PDF
Sujet de l'épreuve de Informatique B du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2022, filière PC, en 2 heures. Thème : Spéléo-logique : remplissage d'une grotte par une source d'eau à partir de son profil.
Ce que traite le sujet, partie par partie
- Partie I : Validité d'un profil. Profil codé par une liste de pas haut, bas, gauche, droite : test d'absence de rebroussement, reconnaissance d'une vallée, voisins d'un point, liste des points parcourus et test de profil simple avec sa complexité.
- Partie II : Vallée. Fond d'une vallée, liste des plateaux en temps linéaire, décomposition du volume en rectangles triés de bas en haut et hauteur de l'eau à un instant donné pour un débit unitaire.
- Partie III : Grottes à ciel ouvert. Profil normalisé découpé en rectangles de hauteur 1 organisés en hiérarchie parent-enfants construite avec une pile, ordre de remplissage depuis l'origine, hauteurs d'eau à l'instant t, volumes des sous-arbres et algorithme pour une source placée n'importe où.
Chapitres à revoir avant de traiter ce sujet
- Bases de Python : expressions, types, instructions, fonctions
- Listes et algorithmes de recherche (séquentielle, dichotomique)
- Piles, files et deques
- Récursivité
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.