Statistiques jury
Comment les candidats s'en sont sortis
Notes brutes officielles publiées par le jury — non harmonisées.
Moyenne
9.68
Médiane
9.7
Écart-type
3.60
Q1 (25%)
7.3
Q3 (75%)
12.1
Candidats présents
880
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 en 7 parties largement indépendantes sur la compression entropique de textes. Partie I : comptage des occurrences. Partie II : représentation d'un alphabet par arbre binaire (feuilles étiquetées). Partie III : codes préfixes pour encoder/décoder. Partie IV : construction d'un arbre optimal (Huffman simplifié, sans files de priorité). Parties V-VI : arbres canoniques et alphabétiques pour limiter le coût de stockage de l'arbre. Partie VII : codes arithmétiques…
Structure de l'épreuve
- Partie I — Partie I — Comptage des occurrences(Q I.1-I.2)Abordable
Fonction q de S vers ℕ comptant les lettres d'un mot. Q1.1 : 98 % traitée, 84 % réussie. Q1.2 : tableau trié par ordre décroissant attendu mais souvent inversé.
- Partie II — Partie II — Arbres binaires d'étiquetage(Q II.1-II.4)Niveau attendu
Représentation d'un alphabet comme feuilles d'un arbre binaire. Q II.1 : cardinal de T_[1,n] (90 % traitée, 76 % réussie en MP). Q II.4 : étiquette de chaque feuille (55 %, 13 %).
- Partie III — Partie III — Codes préfixes pour (dé)compression(Q III.1-III.2)Difficile
Tout arbre binaire décrit un code préfixe utilisable pour encoder/décoder. Q III.1 : 89 % traitée, 15 % réussie — preuve d'unicité par récurrence souvent confondue avec déterminisme. Q III.2 : 82 %, 12 % — gestion de la liste vide pour le mot vide.
- Partie IV — Partie IV — Arbre optimal (Huffman simplifié sans files de priorité)(Q IV.1-IV.6)Difficile
Construction d'un arbre optimal pour la taille du texte encodé. Approche similaire à Huffman mais sans files de priorité (contre-productif ici). Q IV.6 (code optionnel) : 20 % MP, 3 % réussite.
- Partie V — Partie V — Arbres canoniques (représentation compacte)(Q V.1-V.x)Très difficile
Arbres canoniques limitant le coût de stockage de l'arbre lui-même. Q V.1 : 33 % MP, 3 % réussite — codes longs sans explication.
- Partie VI — Partie VI — Arbres alphabétiques (encore plus compacts)(Q VI.1-VI.2)Très difficile
Compression encore plus de l'arbre, au prix d'un moindre taux de compression. Q VI.1 : 21 % MP, 2 % réussite — programmation dynamique avec parcours dans le mauvais sens.
- Partie VII — Partie VII — Codes arithmétiques rANS (approche alternative)(Q VII.1-VII.2)Très difficile
Approche complètement différente : codes arithmétiques de type rANS pour s'approcher davantage du taux de compression théorique optimal. Largement non abordée.
Analyse globale du jury
« Sujet OCaml de compression entropique en 7 parties indépendantes. Pour la note maximale, il n'était pas nécessaire de traiter l'intégralité du sujet. MP : 880 candidats français, moyenne 9,68/20, σ=3,60. MPI : 228 candidats, 11,60/20, σ=3,43. Trop de codes inutilement complexes (>10 lignes vs attendues 5-10) et listes/tableaux confondus. Distinction stricte attendue entre listes et tableaux : l[i] sur une liste, ou x::t sur un tableau, sanctionnés. Concaténation de listes n'est pas O(1). Beaucoup de candidats raisonnent par récurrence en disant 'ainsi de suite' sans préciser sur quoi. Beaucoup ont prouvé que l'algorithme III.2 est déterministe au lieu de l'unicité de la décomposition. »
Top pièges sanctionnés
Tableau trié par ordre décroissant alors que croissant demandé (Q I.2)-1 pts
« Beaucoup de candidats ont écrit une fonction qui renvoie un tableau trié par ordre décroissant, contrairement à ce qui est demandé dans le sujet. »
Confondre listes et tableaux : l[i] avec l liste, ou x::t avec t tableau, en O(1)-2 pts
« Trop de candidats, probablement inspirés de Python, ne font pas la différence entre listes et tableaux et se permettent d'écrire l[i] avec l une liste, ou x::t avec t un tableau. De plus, ces opérations sont alors souvent considérées comme étant en temps constant, ce qui a évidemment été sanctionné. »
Concaténation de liste considérée O(1) — c'est en O(taille de la gauche)-2 pts
« La concaténation de liste n'est pas une opération élémentaire ; sa complexité est linéaire en la taille de la liste de gauche ! »
Récurrence par 'ainsi de suite' / 'on procède récursivement' sans poser la quantité d'induction (Q III.1)-2 pts
« Beaucoup de candidats raisonnent par récurrence en indiquant simplement 'et ainsi de suite' ou 'on procède récursivement', sans même indiquer sur quoi procède la récurrence ; cela a été sanctionné. Par ailleurs, beaucoup trop de copies ont en réalité prouvé que l'algorithme de la question III.2 est déterministe, ce qui est vrai mais n'implique en rien l'unicité de la décomposition et ne répond donc pas à la question. »
O(n) appels récursifs ⇒ complexité totale O(n) — faux si chaque appel n'est pas O(1)-2 pts
« Concernant les analyses de complexité, le fait qu'une fonction effectue O(n) appels récursifs n'implique en rien que la complexité temporelle totale soit aussi en O(n). Encore faut-il pouvoir garantir que le nombre d'opérations élémentaires effectuées à chaque appel est borné. »
Chapitres clés à maîtriser
Ressources
Téléchargements
Sujet officiel, corrigé Hadamard et rapport jury — tout en un endroit.
FAQ
