X-ENS 2024 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 2024, filière PC, en 2 heures. Thème : Logimage : vérification et résolution d'une grille à partir des clés de lignes et de colonnes.
Ce que traite le sujet, partie par partie
- Partie I - Préliminaires et vérification d'une solution. Nombre de cases noires codées par les clés, compatibilité des clés de lignes et de colonnes, taille minimale d'une ligne et recherche d'exemples qui mettent en défaut une fonction de vérification fournie.
- Partie II - Résolution systématique. Remplissage case par case, énumération récursive de toutes les grilles avec vérification et complexité exponentielle, puis élagage dès qu'une ligne ou une colonne a trop de cases noires.
- Partie III - Placements possibles d'un bloc. Cases en conflit avec le placement d'un bloc dans une ligne partiellement remplie, plus petite position en conflit en O(s) et première position valide d'un bloc en O(nc).
- Partie IV - Placements possibles de tous les blocs d'une ligne. Matrice des premières positions possibles remplie par programmation dynamique en O(nc^2), cas du premier bloc, positions au plus tôt et au plus tard de chaque bloc et déduction des cases forcément noires ou blanches.
Chapitres à revoir avant de traiter ce sujet
- Bases de Python : expressions, types, instructions, fonctions
- Spécifier, tester, prouver : terminaison et correction
- Récursivité
- Listes et algorithmes de recherche (séquentielle, dichotomique)
- Programmation dynamique
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.