Statistiques jury
Comment les candidats s'en sont sortis
Notes brutes officielles publiées par le jury — non harmonisées.
Moyenne
9.05
Médiane
9.1
Écart-type
3.52
Q1 (25%)
6.7
Q3 (75%)
11.4
Candidats présents
857
Analyse
Ce qu'a observé le jury
Synthèse Hadamard du rapport officiel — citations, chiffres et conseils du jury.
Présentation du sujet
Sujet OCaml conçu pour être traité linéairement, en 3 parties. Partie I (préliminaires) : introduction des arbres binaires de recherche et AVL — propriétés élémentaires (nombre d'arbres à n nœuds, hauteur logarithmique). Partie II (très longue) : insertion et suppression de nœuds avec rééquilibrage (rotations) — analyse fine de correction et complexité, fonctions split/join. Partie III : application AVL pour localisation d'un point dans une subdivision planaire par…
Structure de l'épreuve
- Partie I — Partie I — Préliminaires : arbres binaires et AVL(Q1-Q5)Niveau attendu
Énumération d'arbres (Q1 oubli des symétries), équivalence ABR / séquence infixe triée (Q2), hauteur logarithmique (Q3-Q4 télescopage de 2^(h-1)). Q5 : programmation classique. Q1-Q4 : 100 % traitée, taux de réussite 21-67 %.
- Partie II — Partie II — Insertion, suppression, rééquilibrage(Q6-Q17)Très difficile
Fonction de rééquilibrage (centrale, analyse fine de correction et complexité). Q6 mal traitée (« non-plantage ≠ termination ≠ AVL »). Q8 : 1-3 % de réussite — démontrent l'inégalité de hauteur mais oublient de vérifier que c'est un AVL. Q13 (split complexité O(log n)) : 0-2 % réussite. Fonctions...
- Partie III — Partie III — Localisation d'un point (géométrie algorithmique)(Q18-Q22)Très difficile
Subdivision planaire par polygones aux arêtes ne se croisant pas. Comparaison de segments à abscisse fixée. Q18 : 22 % réussite — oubli des contraintes de l'énoncé. Q19 : 7-9 % — formules fausses, comparaison incorrecte. Q20 : 2-7 % — réponses vagues sans préciser structures de données.
Analyse globale du jury
« Sujet OCaml linéaire sur les AVL et leur application en géométrie algorithmique. La 2ème partie sur les algorithmes d'insertion/suppression nécessitait une analyse fine. MP : 857 candidats français + internationaux, moyenne 9,05/20 (σ=3,52). MPI : 320 candidats, 10,68/20 (σ=3,71). Lecture rigoureuse de l'énoncé : distinguer ABR/AVL, écrire algorithme ET analyser sa complexité (la seconde partie d'une question vaut 30-50 % des points). Codes attendus < 10 lignes (sauf Q22). Distinction stricte listes/tableaux. Analyse de code souvent vague — référer aux numéros de lignes. Récurrences avec invariants, ne pas négliger le cas de base. »
Top pièges sanctionnés
Oublier de prouver une direction dans les équivalences (Q2)-2 pts
« Trop de candidats ont oublié de prouver une direction de l'équivalence. Par ailleurs, beaucoup de candidats n'ont pas utilisé la définition d'arbre équilibré du sujet (séquence infixe triée) et se sont contentés de preuves vagues. »
Affirmation informelle « le dernier niveau est au moins à moitié rempli ⇒ 2^(h-1) nœuds » (Q4)-2 pts
« Trop de candidats ignorent l'indication et affirment informellement que « le dernier niveau d'un AVL est au moins à moitié rempli et contient donc au moins 2^(h-1) nœuds ». En plus d'être fausse, une preuve à base d'arguments trop informels ne saurait rapporter des points. »
Démontrer l'inégalité de hauteur mais oublier de vérifier que c'est un AVL (Q8)-3 pts
« La plupart des candidats se sont contentés de démontrer l'inégalité sur la hauteur, mais n'ont pas vérifié que l'arbre est bien un AVL ! »
Confondre non-plantage, termination et correction AVL (Q6)-3 pts
« Cette question demandait de la rigueur et a été très mal traitée dans l'ensemble. Trop de candidats ne justifient soit que la termination, soit que le « non-plantage », ou bien un mélange des deux qui les arrange ! Par ailleurs, beaucoup de copies oublient que join_right effectue un appel récursif à la ligne 9, ce qui nécessite donc un argument. »
Justification vague de complexité par « on voit bien que ça décroît » (Q9)-2 pts
« Cette question assez facile est mal traitée par beaucoup de candidats. La formule de complexité attendue étant fournie par l'énoncé, il est souhait que les candidats justifient précisément celle-ci. En aucun cas, un raisonnement vague du type « on voit bien cette quantité décroît » ne peut suffire. »
Chapitres clés à maîtriser
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ
