Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Composition d'informatique 2h, filière PSI (sigle 'Info-B' en 2023). Sujet sur la réalisation d'un système de gestion de versions de grands textes et plus particulièrement la notion de différentiel entre textes. Trois parties : Partie 1 différentiels entre textes (même puis différentes tailles), algorithmes de gestion de versions. Partie 2 lien entre calcul d'un différentiel et recherche d'un plus court chemin dans un graphe. Partie 3 algorithme A* avec heuristique admissible.
Structure de l'épreuve
- Partie I — Partie 1 — Différentiels et gestion de versions(Q1-Q7)Difficile
Différentiels entre textes. Q1 oubli de tester l'égalité des longueurs. Q3 nombre de candidats échouent malgré la simplicité. Q4 distance de Levenshtein, récursion mal traitée.
- Partie II — Partie 2 — Distance d'édition (Levenshtein)(Q8-Q13)Très difficile
Calcul du poids d'un différentiel. Distance d'édition par récurrence (Levenshtein, programme officiel). Q9 candidats ne traitent pas correctement texte1[i+1] != texte2[j+1]. Q10 corner cases mal gérés.
- Partie III — Partie 3 — Plus court chemin (Dijkstra, A*)(Q14-Q17)Très difficile
Construction de la fonction successeur du graphe d'édition. Q15 connaissance fine de Dijkstra requise — presque jamais traitée. Q17 algorithme A* — aucune copie n'a proposé de solution correcte.
Analyse globale du jury
« Le sujet portait sur la réalisation d'un système de gestion de versions de grands textes. La partie 1 portait sur les différentiels entre textes de même taille. Puis, la partie 2 étudiait les différentiels entre textes de tailles différentes. Enfin, la partie 3 étudiait le lien entre le calcul d'un différentiel entre textes et la recherche d'un plus court chemin dans un graphe. Globalement, le niveau est assez faible, beaucoup de candidats ne semblent pas du tout maîtriser l'algorithmique et le langage Python. »
Top pièges sanctionnés
Code illisible (i,j,x,y monolettres, indentations approximatives)-2 pts
« Le jury rappelle que le code demandé sera lu. Il est donc nécessaire de produire du code lisible. En particulier les noms de variables doivent être judicieux et le code doit être commenté. Par exemple, les noms de variable à une lettre i,j,x,y sont à proscrire, au moins dès qu'on dépasse le cas simple de l'indice d'une boucle seule. »
Algorithme de Dijkstra et complexité non connus (Q15-Q16)-3 pts
« À un niveau supérieur, les quelques candidats qui ont atteint la partie 3 montrent une méconnaissance de l'algorithme de Dijkstra et de sa complexité, pourtant au programme. »
Algorithme A* : aucune solution correcte (Q17)-3 pts
« Enfin, cette question cherche à utiliser l'algorithme A* et demande d'exhiber une heuristique admissible. Un très petit nombre de candidats a eu l'idée de proposer une fonction linéaire en i et j. Aucune copie n'a proposé de solution correcte. »
Distance de Levenshtein (au programme) mal écrite (Q9)-3 pts
« Cette question demande une récurrence pour calculer la distance d'édition entre deux textes. Il s'agit en fait d'une question de cours, la distance de Levenstein étant au programme. Malgré cela, le cas texte1[i+1] != texte2[j+1] n'est presque jamais traité correctement. »
Corner cases (cas particuliers) systématiquement ignorés-2 pts
« Comme d'habitude, les corner cases ont rarement été traités correctement. Typiquement, lorsque les candidats se contentent d'insérer une tranche dès que texte1[i] == texte2[i] en oubliant la dernière tranche. »
Chapitres clés à maîtriser
Source : Rapport du jury X-ENS · Info PSI, session 2023 · PDF officiel ↗
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ
