É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 ;
• 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 [ [ correspondant au caractère ' d ' ;
• le caractère ' ' détermine alors le sous-intervalle [ [ de [ [ correspondant à la portion associée au caractère ' '.
• le caractère ' c ' détermine enfin l'intervalle [0.524; 0.540[.

Figure 2 - Encodage de '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 symboles , que nous allons représenter par une liste Python ,
• pour simplifier, on supposera que l'alphabet est un ensemble de entiers consécutifs commençant à 0 , de sorte que . Par exemple si et , un message valide reçu par Bob pourrait être .
• chacun des symboles observés correspond à l'altération d'un symbole envoyé par Alice. On note le message original ; pour reprendre l'exemple précédent, Alice pourrait avoir envoyé .
• on connaît, pour chaque paire , la probabilité que le canal altère le symbole en un symbole . On stocke ces probabilités dans une liste de listes E; autrement dit, est la probabilité conditionnelle d'observer le symbole sachant que le symbole a été émis.

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

• on crée un sommet pour chaque symbole possible et chaque indice d'observation . Chaque couche verticale dans le graphe correspond à un caractère dans le message. Chaque strate horizontale correspond à un symbole.
• au niveau de la -ème couche verticale, les sommets pour ont pour successeurs les états pour tous les symboles 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 , correspond au décodage de .

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

• les arcs issus de la source vers sont pondérés par la probabilité d'observer le symbole sachant que le symbole 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 et sont pondérés par la probabilité .

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 lignes par colonnes,
• T[i] [0] contient la valeur de ,
• contient la valeur -1 ,
• les autres valeurs de T et 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.