X-ENS 2023 PSI 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 2023, filière PSI, en 2 heures. Thème : Gestion de versions de grands textes : différentiels, distance d'édition et plus courts chemins.
Ce que traite le sujet, partie par partie
- Partie I : Différentiels par positions fixes. Textes de même longueur vus comme des listes de caractères : égalité, nombre de positions différentes, test de caractères communs avec un dictionnaire, calcul et application d'un différentiel en tranches, différentiel inverse et texte versionné avec une pile d'historique.
- Partie II : Différentiels sur des positions variables. Tranches de longueurs différentes, poids d'un différentiel, distance de Levenshtein par programmation dynamique, reconstruction d'un différentiel de poids minimal en remontant la matrice, puis détection de conflit et fusion de deux différentiels.
- Partie III : Calcul de différentiels par calcul de plus courts chemins. Grille des préfixes vue comme un graphe orienté pondéré, successeurs d'un sommet, variante de l'algorithme de Dijkstra et sa complexité comparée à la programmation dynamique, puis algorithme A* avec une heuristique admissible.
Chapitres à revoir avant de traiter ce sujet
- Chaînes de caractères et algorithmes sur les textes
- Tuples, dictionnaires et ensembles
- Piles, files et deques
- 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.