X-ENS 2023 MP Informatique A : sujet en PDF
Sujet de l'épreuve de Informatique A du Concours d'admission de l'École polytechnique et des ENS (X-ENS), France, session 2023, filière MP, en 4 heures. Thème : Compression entropique : codes préfixes, arbres de Huffman, arbres canoniques et alphabétiques, codage arithmétique.
Ce que traite le sujet, partie par partie
- Partie I. Comptage d'occurrences. Calcul du nombre d'occurrences de chaque lettre d'un mot représenté par une liste d'entiers, puis passage en temps O(|S|) à un tableau des seules lettres présentes avec leur effectif.
- Partie II. Arbres binaires. Arbres binaires dont les feuilles sont les lettres de l'alphabet : dénombrement pour quatre lettres, coût pondéré par les profondeurs, chemin de bits vers une feuille et construction d'un arbre de codes de profondeur bornée.
- Partie III. Codes préfixes. Unicité du décodage d'une suite de bits par un arbre, fonction de décompression avec détection des suites invalides et complexité, lien entre le coût pondéré et la longueur du mot compressé.
- Partie IV. Arbres optimaux. Propriétés des arbres optimaux, lettre très fréquente à profondeur 1, fusion des deux lettres les moins fréquentes, algorithme de Huffman par insertion dans une liste triée et version en temps linéaire.
- Partie V. Arbres canoniques. Arbres dont les feuilles sont rangées par profondeur puis par ordre alphabétique, représentation compacte par deux tableaux et reconstruction de l'arbre avec sa complexité.
- Partie VI. Arbres alphabétiques. Arbres dont les feuilles suivent l'ordre alphabétique, relation de récurrence et programmation dynamique en O(n^3) pour un arbre alphabétique optimal, puis reconstruction d'un arbre à partir de son codage préfixe en bits en temps linéaire.
- Partie VII. Codes arithmétiques. Comparaison avec un arbre optimal sur un exemple, dénombrement des mots ayant des effectifs fixés, codage d'un mot par un entier avec division euclidienne et décodage, puis renormalisation par suppression de bits de poids faible pour éviter les grands entiers.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Complexité des algorithmes itératifs et récursifs
- Récursivité
- Spécifier, tester, prouver : terminaison et correction
- Programmation dynamique
- Arithmétique dans l'ensemble des entiers relatifs
- Architecture de l'ordinateur et représentation des nombres
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.