X-ENS 2025 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 2025, filière PC, en 2 heures. Thème : Le jeu de Röckse : chemin de pénalité minimale dans une grille avec sauts et cases bonus.
Ce que traite le sujet, partie par partie
- Partie I : Sauts et chemins. Poids d'un chemin, application d'une suite de sauts, vérification qu'un chemin n'utilise que des sauts autorisés compte tenu des bonus et condition de positivité lexicographique qui exclut les cycles.
- Partie II : Recherche exhaustive. Longueur maximale d'un chemin, recherche récursive du chemin de poids minimal avec un horizon limité, complexité et amélioration par mémorisation des résultats.
- Partie III : Recherche gloutonne. Algorithme glouton qui joue la meilleure suite locale de k sauts, essais sur l'exemple pour plusieurs horizons et programmation de la recherche.
- Partie IV : Recherche par programmation dynamique. Codage binaire des ensembles de bonus activés, relation de récurrence sur le poids optimal, ordre de calcul des masques par inclusion décroissante obtenu avec une file, puis remplissage des tableaux et reconstruction d'un chemin optimal.
Chapitres à revoir avant de traiter ce sujet
- Bases de Python : expressions, types, instructions, fonctions
- Tuples, dictionnaires et ensembles
- Récursivité
- Programmation dynamique
- Architecture de l'ordinateur et représentation des nombres
- Piles, files et deques
- Dictionnaires et principes du hachage
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.