Mines-Ponts 2020 MP Informatique option MP : sujet en PDF

Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2020, filière MP, en 3 heures. Thème : Comptage des lettres d'un texte et arbre de code optimal.

Lire le sujet 10 pages · sujet sans corrigé, reproduit sans retouche−+Télécharger le PDF (0,7 Mo)

Ce que traite le sujet, partie par partie

• Parties 1.1 et 1.2 : tableau exhaustif et table modulaire. Distribution des fréquences des lettres d'un texte sur l'alphabet Unicode : fonction récursive à typer et à prouver par récurrence, répartition sous forme de liste et ses complexités, puis table modulaire d'ordre m dont la complexité moyenne s'obtient par une espérance conditionnelle, avec le choix de m pour un courriel.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Récursivité, Complexité des algorithmes itératifs et récursifs, Dictionnaires et principes du hachage
• Partie 1.3 : tableau creux. Tableau creux de comptage formé de trois tableaux non initialisés et de la valence du mot : propriétés de la structure, test de présence d'une lettre avec terminaison et correction, incrémentation, construction, complexités en temps et en espace et réalisme pour l'alphabet Unicode.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Spécifier, tester, prouver : terminaison et correction, Complexité des algorithmes itératifs et récursifs
• Parties 2.1 et 2.2 : codage et arbre de code optimal. Code binaire des lettres représenté par un arbre binaire ordonné selon l'alphabet, fonction d'encodage et sa complexité, profondeur pondérée, relation de récurrence sur les sous-alphabets et algorithme en O(λ^3) qui construit un arbre de code optimal.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Complexité des algorithmes itératifs et récursifs
• Partie 2.3 : un arbre de code optimal calculé plus rapidement. Encadrement r(u,v) <= r(u,v+1) <= r(u+1,v+1) des racines optimales qui ramène l'algorithme à O(λ^2), démontré par récurrence à l'aide de la profondeur pondérée vue comme fonction affine par morceaux d'un poids.
  À revoir : Complexité des algorithmes itératifs et récursifs

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Récursivité
• Complexité des algorithmes itératifs et récursifs
• Dictionnaires et principes du hachage
• Spécifier, tester, prouver : terminaison et correction

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.