Top piège du sujet
Oublier de prouver une direction dans les équivalences (Q2)
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
Comparaison
Comment ce sujet se compare aux autres
Moyenne en baisse de -0.63 par rapport à 2023 (9.05 vs 9.68). Écart-type stable (σ=3.52). Sujet plus exigeant que la session précédente.
Calculateur
Où je me situe sur ce sujet ?
Entrez votre note brute. Le percentile et la position se mettent à jour en temps réel.
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
Bosse chaque chapitre sur d'autres sujets de concours qui le couvrent.
Contexte
L'épreuve en quelques chiffres
Accompagnement personnalisé
Travaillez ce sujet avec un prof de l'équipe
Nos professeurs anciens taupins (Polytechnique, ENS, Centrale) reprennent ce sujet avec toi en cours particulier — corrigé ligne par ligne, méthode, pièges évités.
Trouvez le prof qu'il vous faut
Échangez avec notre équipe pour trouver le professeur idéal selon vos besoins.
Stratégie
Notre approche pour ce sujet
- Partie I, Préliminaires : arbres binaires et AVL (Q1-Q5 · moyen)
- Partie II, Insertion, suppression, rééquilibrage (Q6-Q17 · tres-dur)
- Partie III, Localisation d'un point (géométrie algorithmique) (Q18-Q22 · tres-dur)
Conseils du jury
Pièges sanctionnés par le rapport
- Oublier de prouver une direction dans les équivalences (Q2) : « 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) : « 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) : « 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) : « 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... »
- Justification vague de complexité par « on voit bien que ça décroît » (Q9) : « 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... »
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ