Prepa HelpMines-Ponts 2023 MPI Informatique 2 : sujet en PDF
Sujet de l'épreuve de Informatique 2 du Concours commun Mines-Ponts, France, session 2023, filière MPI, en 4 heures. Thème : Complexité de Kolmogoroff : codage de Huffman, grammaires et termes de De Bruijn en OCaml.
Ce que traite le sujet, partie par partie
- Section 1 : complexité de Kolmogoroff. Descriptions d'une chaîne par un programme OCaml, exponentiation par diviser pour régner, bijection entre entiers et chaînes, non-calculabilité de la complexité et majoration par décompresseur.
- Section 2 : estimation grâce au décompresseur de Huffman. Typage et évaluation d'une expression OCaml, comptage des occurrences avec une table de hachage, arbre de Huffman et longueur de la chaîne compressée.
- Section 3 : interlude. Portée de références dans trois fonctions censées produire des chaînes inédites, test qui écarte la fonction erronée.
- Section 4 : estimation grâce au décompresseur de De Bruijn. Grammaires, expression régulière et automate de Glushkov, analyse syntaxique, non-ambiguïté, entiers incarnés, variables libres, termes de De Bruijn et codage binaire injectif, substitution, réduction et interpréteur.
Chapitres à revoir avant de traiter ce sujet
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.