Mines-Ponts 2024 PSI Informatique commune : sujet en PDF

Sujet de l'épreuve de Informatique commune du Concours commun Mines-Ponts, France, session 2024, filière PSI, en 2 heures. Thème : Deux problèmes de communication numérique : codage arithmétique et algorithme 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

• 1.1 Analyse du texte source. Code binaire à longueur variable décodable sans ambiguïté, comptage des occurrences des caractères d'une chaîne, complexité selon la longueur et le nombre de caractères distincts, puis version linéaire avec un dictionnaire.
  À revoir : Chaînes de caractères et algorithmes sur les textes, Architecture de l'ordinateur et représentation des nombres, Dictionnaires et principes du hachage
• 1.2 Exploitation d'analyses existantes. Requêtes SQL sur une base de corpus littéraires : auteurs sans doublon et fréquence d'apparition de chaque caractère en français.
• 1.3 Compression et 1.4 Décodage. Codage arithmétique d'une chaîne par emboîtement d'intervalles de [0, 1[, fonction de codage, décodage d'un flottant, ambiguïté levée par un caractère de fin et limites dues à la précision des flottants.
  À revoir : Chaînes de caractères et algorithmes sur les textes, Architecture de l'ordinateur et représentation des nombres
• 2.1 Modélisation du canal de communication par un graphe. Graphe en couches des symboles émis, pondéré par les probabilités d'altération et de transition : nombre de sommets, d'arcs et de chemins, impossibilité d'une exploration exhaustive.
• 2.2 Stratégie gloutonne. Recherche du maximum et de son premier indice, décodage glouton du chemin le plus probable, complexité et contre-exemple montrant que l'approche n'est pas optimale.
  À revoir : Listes et algorithmes de recherche (séquentielle, dichotomique)
• 2.3 Stratégie de programmation dynamique. Lien avec un plus court chemin, puis algorithme de Viterbi de bas en haut : tableaux des probabilités maximales et des prédécesseurs, lecture de la séquence la plus probable et complexités temporelle et spatiale.

Chapitres à revoir avant de traiter ce sujet

• Chaînes de caractères et algorithmes sur les textes
• Architecture de l'ordinateur et représentation des nombres
• Dictionnaires et principes du hachage
• 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.