Mines Informatique Commune MP PC PSI 2024Sujet, corrigé et rapport du jury

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARIS, TÉLÉCOM PARIS, MINES PARIS, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.
Concours Mines-Télécom, Concours Centrale-Supélec (Cycle International).

CONCOURS 2024

ÉPREUVE D'INFORMATIQUE COMMUNE

Durée de l'épreuve : 2 heures

INFORMATIQUE COMMUNE

Introduction à deux problèmes en communication numérique

Introduction

• une phase de compression, durant laquelle Alice cherche à trouver la représentation la plus compacte possible du message,
• une phase d'encodage durant laquelle le message compressé est transformé en une succession de symboles transmissibles au travers du canal de communication utilisé,
• une phase de transmission durant laquelle le message encodé circule sur le canal de communication et est susceptible de subir une altération,
• une phase de décodage durant laquelle Bob décode le message qu'il a reçu, le message lui apparaît alors sous la forme compressée,
• une phase de décompression durant laquelle Bob applique l'opération réciproque de la compression opérée par Alice.
  Ce modèle est décrit par le schéma de la Figure 1 :

Figure 1 - Schématisation du modèle de communication considéré ici.

1 Compression du message d'Alice : codage arithmétique

1.1 Analyse du texte source

• les caractères utilisés par la chaîne s;
• le nombre d'occurrences de chacun.

def listeCaracteres(s:str):
    listeCar = []
    n = len(s)
    for i in range(n):
        c = s[i]
        if not(c in listeCar):
            listeCar.append(c)
    return listeCar

def analyseTexte(s:str):
    R = []
    l = listeCaracteres(s)
    for i in range(len(l)):
        c = l[i]
        R.append((c, nbCaracteres(c, s)))
    return R

1.2 Exploitation d'analyses existantes

• caractere(idCar, symbole, typeCaractere, codeHTML);
• corpus(idLivre, titre, auteur, annee, nombreCaracteres, langue) ;
• occurrences(idCar, idLivre, nombreOccurrences);
  dont voici quelques extraits :

1.3 Compression

• on obtient d'abord l'intervalle [ 0.5; 0.9 [ correspondant au caractère ' d ' ;
• le caractère ' a ' détermine alors le sous-intervalle [ 0.50; 0.58 [ de [ 0.5; 0.9 [ correspondant à la portion associée au caractère ' a '.
• le caractère ' c ' détermine enfin l'intervalle [0.524; 0.540[.

Figure 2 - Encodage de s = 'dac'

1.4 Décodage

• Q14 - Écrire une fonction decodage(x: float)->str produisant la chaîne de caractères s déterminée par la valeur de x (avec le caractère ' # ' compris).

2 Décodage du message reçu par Bob à l'aide de l'algorithme de Viterbi

2.1 Modélisation du canal de communication par un graphe

• Bob observe une suite de N symboles obs_0, …, obs_(N − 1), que nous allons représenter par une liste Python Obs = [obs_0, …obs_(N − 1)],
• pour simplifier, on supposera que l'alphabet Σ est un ensemble de K entiers consécutifs commençant à 0 , de sorte que Σ = [ [0, K − 1] ]. Par exemple si K = 3 et N = 8, un message valide reçu par Bob pourrait être [2, 0, 0, 2, 1, 1, 0, 0].
• chacun des symboles observés obs_t correspond à l'altération d'un symbole s_t envoyé par Alice. On note [s_0, …s_(N − 1)] le message original ; pour reprendre l'exemple précédent, Alice pourrait avoir envoyé [2, 0, 0, 2, 1, 1, 2, 0].
• on connaît, pour chaque paire (i, j) ∈ Σ^2, la probabilité E_(i, j) que le canal altère le symbole j en un symbole i. On stocke ces probabilités dans une liste de listes E; autrement dit, E[i][j] est la probabilité conditionnelle d'observer le symbole i sachant que le symbole j a été émis.

• on suppose également que le symbole courant s_t envoyé par Alice a une incidence sur le symbole suivant s_(t + 1) qu'elle peut envoyer, au même titre que dans une langue comme le français, la probabilité d'observer un ' t ' dans un mot, n'est pas la même suivant que le caractère précédent est un ' e ' ou un ' z '.

• on crée un sommet S_(i, j) pour chaque symbole possible 0 ⩽ i ⩽ K − 1 et chaque indice d'observation 0 ⩽ j ⩽ N − 1. Chaque couche verticale dans le graphe correspond à un caractère dans le message. Chaque strate horizontale correspond à un symbole.
• au niveau de la j-ème couche verticale, les sommets S_(i, j) pour j < N − 1 ont pour successeurs les états S_(k, j + 1) pour tous les symboles k possibles,
• par commodité, on ajoute un état source σ correspondant au début du message décodé et un état cible τ correspondant à la fin du message, ces états étant respectivement reliés à la première et la dernière couche,
• le décodage du message envoyé par Alice correspond à un chemin entre σ et τ dans ce graphe. A chaque sommet du chemin correspond une lettre décodée. Par exemple, le chemin passant par S_(0, 0), S_(2, 1), S_(0, 2), S_(1, 3), correspond au décodage de [0, 2, 0, 1].

Figure 3 - Illustration du modèle de décodage considéré ici.

• les arcs issus de la source σ vers S_(i, 0) sont pondérés par E_(obss_0, i) la probabilité d'observer le symbole obs_0 sachant que le symbole i a été émis par Alice;
• les arcs arrivant à la cible τ sont pondérés par 1 (en fin de message, on transite forcément vers l'état final),
• les arcs internes entre S_(i, j) et S_(k, j + 1) sont pondérés par la probabilité E_(obs_(j + 1), k)P_(i, k).

2.2 Stratégie gloutonne

def initialiserGlouton(Obs, E, K):
    probasInitiales = [E[Obs[O][i]] for i in range(K)]
    s, symbole = maximumListe(probasInitiales)
    return symbole

Figure 4 - Que donne l'algorithme glouton ici?

2.3 Stratégie de programmation dynamique

• T et argT sont de dimensions K lignes par N colonnes,
• T[i] [0] contient la valeur de E_(obs_0, i),
• argT[i][0] contient la valeur -1 ,
• les autres valeurs de T et argT sont à 0 .

def initialiserViterbi(E, ObsO, K, N):
    probasInitiales = [E[ObsO] [i] for i in range(K)]
    T = [[0 for j in range(N)] for i in range(K)]
    argT = [[O for j in range(N)] for i in range(K)]
    for i in range(K):
        T[i][0] = probasInitiales[i]
        argT[i][0] = -1
    return T, argT

Fin de l'épreuve.