Mines-Ponts 2024 MP Informatique commune : sujet en PDF

Sujet de l'épreuve de Informatique commune du Concours commun Mines-Ponts, France, session 2024, filière MP, en 2 heures. Thème : Communication numérique : codage arithmétique et décodage de Viterbi.

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

Ce que traite le sujet, partie par partie

• Partie 1 (1.1 et 1.2) : analyse du texte source et base de données. Codage binaire préfixe de longueur variable, comptage des occurrences des caractères d'une chaîne, complexité selon la longueur et le nombre de caractères distincts, version linéaire avec un dictionnaire, puis requêtes SQL de fréquences sur un corpus de livres.
  À revoir : Chaînes de caractères et algorithmes sur les textes, Complexité des algorithmes itératifs et récursifs, Dictionnaires et principes du hachage
• Partie 1 (1.3 et 1.4) : compression et décodage arithmétiques. Codage d'une chaîne par emboîtement de sous-intervalles de [0, 1[ proportionnels aux fréquences, décodage d'un flottant, ambiguïté levée par un caractère de fin et limite liée à la mantisse des flottants.
  À revoir : Architecture de l'ordinateur et représentation des nombres, Bases de Python : expressions, types, instructions, fonctions
• Partie 2 (2.1) : modélisation du canal par un graphe. Matrices d'émission et de transition, graphe en couches des symboles possibles, nombre de sommets, d'arcs et de chemins, pondération par les probabilités et impossibilité d'une exploration exhaustive.
  À revoir : Complexité des algorithmes itératifs et récursifs
• Partie 2 (2.2 et 2.3) : stratégie gloutonne et algorithme de Viterbi. Maximum et premier argument du maximum d'une liste, décodage glouton et contre-exemple à son optimalité, lien avec un plus court chemin, puis programmation dynamique de Viterbi avec tableau des prédécesseurs et complexités en temps et en espace.
  À revoir : Complexité des algorithmes itératifs et récursifs, Listes et algorithmes de recherche (séquentielle, dichotomique)

Chapitres à revoir avant de traiter ce sujet

• Chaînes de caractères et algorithmes sur les textes
• Complexité des algorithmes itératifs et récursifs
• Dictionnaires et principes du hachage
• Architecture de l'ordinateur et représentation des nombres
• Bases de Python : expressions, types, instructions, fonctions
• Listes et algorithmes de recherche (séquentielle, dichotomique)

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.