Mines Informatique MP-PC-PSI 2024

A2024 -- IC

Cm

Concours commun

Mines-Ponts

É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

L'usage de la calculatrice ou de tout autre dispositif électronique est 
interdit.

Cette épreuve est commune aux candidats des filières MP, PC et PSI.

Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

INFORMATIQUE COMMUNE

L'énoncé de cette épreuve comporte 12 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur 
d'énoncé,
il le signale sur sa copie et poursuit sa composition en expliquant les raisons 
des initiatives
qu'il est amené à prendre.

Les sujets sont la propriété du GIP CCMEP. Ils sont publiés sous les termes de 
la licence
Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de 
Modification 3.0 France.
Tout autre usage est soumis à une autorisation préalable du Concours commun 
Mines Ponts.

Rappels concernant le langage Python : il n'est pas possible d'utiliser des
fonctions internes à Python sur les listes ou les chaînes de caractères telles 
que min, max.
count, remove ... Seules les instructions basiques telles que len (liste), 
liste.append(e)
sont autorisées. Le tranchage ou slicing ainsi que la concaténation sont 
également permis.
Les programmes doivent être commentés lorsque c'est nécessaire pour justifier 
les choix.
Il n'est pas utile de rappeler la signature des fonctions demandées dans les 
différentes
questions.

Introduction à deux problèmes en communication numérique

Introduction

On s'intéresse au problème de communication entre deux personnes, nommées Alice 
et
Bob qui cherchent à s'envoyer un message au travers d'un canal de communication 
(une
bande de fréquences radio par exemple).

Avant d'être lu par Bob, le message original d'Alice passe par plusieurs étapes 
que
nous allons séparer de la manière suivante :

-- 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 :

message
message compression encodage message

. > COM- > ,
original ; envoyé

pressé
transmission
ÿ

message | décompression | message décodage message

final _ décodé | reçu

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

Dans cette épreuve, nous allons nous intéresser uniquement à deux phases : la 
com-
pression du message d'origine par Alice en un message compact et le décodage 
par Bob
d'un message transmis, potentiellement entaché d'erreurs.
1 Compression du message d'Alice : codage arithmé-
tique
Le codage ASCII (American Standard Code for Information Interchange) définit une

norme où 128 caractères sont codés sur 7 bits. Ce codage est illustré par les 
quelques lignes
suivantes :

Caractère | Codage binaire | Équivalent numérique
'a' 110 O001 97
'b' 110 0010 98
PA 111 1010 122

Lorsqu'une chaîne de caractères n'utilise pas l'intégralité des 128 caractères 
proposés
par le codage ASCII, il est possible de convenir d'une représentation 
différente, plus
économique en nombre de symboles. Considérons la chaîne de caractères 
s='abaabaca.
On peut proposer de coder celle-ci à l'aide du tableau suivant :

Caractère | Code
'a! (010
'b' 01
'c' 10

Dans ce cas, la chaîne de caractères s est codée sur 16 bits par :
00 O1 O0 00 O1 00 10 O0

(où des espaces ont été introduits pour faciliter la lecture).

Dans un souci de compression de l'information, il est intéressant de 
représenter les
caractères les plus fréquents par des expressions courtes et de ne plus 
nécessairement coder
avec des codes de longueur constante chaque caractère. Dans l'exemple 
précédent, il est
possible de coder le caractère 'a' avec 1 bit, et les caractères 'b' et 'c' 
avec 2 bits afin
de coder la chaîne s sur seulement 11 bits en tout.

LH Q1 -- Proposer une telle représentation en expliquant pourquoi celle-ci 
pourra être
décodée sans ambiguïté. Vous ferez en sorte que la représentation binaire de 
'a' soit
inférieure à celle de 'b', elle-même inférieure à celle de 'c'.

La représentation précédente emploie la même longueur pour coder les caractères 
'b'
et 'c' alors que le caractère 'b' est deux fois plus présent que le caractère 
'c' dans la
chaîne s.

Îl est possible d'aller un cran plus loin et le codage arithmétique présenté 
dans cette
étude permet un gain de compression comme s'il parvenait à représenter un 
caractère avec
un nombre non entier de bits au prorata de sa fréquence d'apparition.

Ce principe de compression est notamment utilisé par la norme JPEG2000 de 
compression
des images. Nous ne le présenterons cependant ici que dans le cadre de l'étude 
de chaînes
de caractères.
1.1 Analyse du texte source

L'objet de cette partie est d'analyser le contenu d'une chaîne de caractères s 
afin de
déterminer :

-- Îles caractères utilisés par la chaîne s ;

-- Je nombre d'occurrences de chacun.

Qi Q2 - Écrire une fonction nommée nbCaracteres(c:str,s:str)->int qui prend 
comme
argument un caractère c, une chaîne s et qui renvoie le nombre d'occurrences 
(c'est-à-dire
le nombre d'apparitions) de c dans s. La fonction doit avoir une complexité 
linéaire en n,
la longueur de la chaïne s.

LU Q3 --- Pour déterminer la liste des caractères utilisés à l'intérieur d'une 
chaîne s on
utilise la fonction définie ci-dessous :

. def listeCaracteres(s:str) :

2 listeCar = []

3 n -- len(s)

4 for i in range (n) :

5 c = slil

6 if not(c in listeCar):
7 listeCar.append(c)
8 return listeCar

Que renvoie cette fonction lorsque s='abaabaca' ? Expliquer succinctement le 
principe de
fonctionnement de cette fonction.

D Q4 --- En fonction de la longueur n de la chaîne et du nombre k de caractères 
distincts
dans celle-ci, déterminer la complexité asymptotique dans le pire des cas de la 
fonction
de la question Q3. Par exemple pour s='abaabaca',on a n -- 8 et k& -- 3. On 
négligera
la complexité des append mais pas celle des tests d'appartenance de la forme i 
in L.
Autrement dit, la ligne 7 est considérée comme étant de complexité constante et 
la ligne 6
de complexité linéaire en la longueur de la liste listeCar.

LU Q5 - On définit alors une fonction analyseTexte(s:str)-2>list

. def analyseTexte(s:str) :

2 R = {]

3 1 = listeCaracteres(s)

4 for i in range(len (1) ) :

5 c = lli]

6 R.append((c, nbCaracteres(c, s)))
7 return R

Expliquer ce que fait cette fonction et donner la valeur renvoyée par la 
commande
analyseTexte('babaaaabca').

LH Q6 -- En fonction de la longueur n de s et du nombre k de caractères 
distincts présents
dans s, (autrement dit k est la longueur de listeCaracteres(s)), donner une 
estimation
de la complexité asymptotique dans le pire des cas de la fonction analyseTexte.

1 Q7 --- Adapter la fonction de la question Q5 pour qu'elle utilise (et 
renvoie) un
dictionnaire. Elle devra avoir une complexité.

i. linéaire en la longueur n des,

ii. indépendante de £ nombre de caractères distincts présents dans s.

De plus, cette fonction devra impérativement ne parcourir qu'une seule fois la 
chaîne
de caractères. On admettra qu'un test d'appartenance d'une clé à un 
dictionnaire se fait à
coût constant. Par exemple, analyseTexte('abracadabra') renverra
{'a':5, 'b':2, 'r':2, 'c':1, 'd':1}.

1.2 Exploitation d'analyses existantes

On peut éviter de réaliser une analyse de la chaîne de caractères à coder en 
exploi-
tant des données statistiques disponibles. La numérisation de larges corpus 
littéraires a
permis la création de bases de données contenant des informations relatives au 
nombre
d'occurrences des différents caractères alphanumériques dans diverses langues. 
Nous allons
supposer disposer d'une base de données constituée de trois tables (les clefs 
primaires sont
soulignées) :

-- caractere(idCar, symbole, typeCaractere, codeHTML) :

-- corpus(idLivre, titre, auteur, annee, nombreCaracteres, langue) :

-- occurrences(idCar, idLivre, nombreOccurrences) :

dont voici quelques extraits :

Table caractere :
| idCar | symbole | typeCaractere | codeHTML |

69 'A' 'lettre' '&H#6E ;
48 'O' 'nombre! '&H48 ; '
Table corpus :
| idLivre | titre | auteur | annee | nombreCaracteres | langue |
1 'Germinal 'Zola' | 1885 1152365 'Français!
2 'Les Misérables' | 'Hugo' | 1862 2245300 'Français'

Table occurrences :

| idCar | idLivre | nombreOccurrences |
62 31 155
37 21 1550

QG Q8 - Écrire en langage SQL une requête permettant d'obtenir la liste sans 
doublon
des auteurs présents dans la table corpus.

© Q9 - Écrire une requête SQL permettant d'obtenir la fréquence d'occurrences 
(donc
comprise entre 0 et 1) de chaque caractère en ''Français'. Plus précisément, la 
requête

4
devra renvoyer une table à deux attributs : une colonne contenant le symbole de 
chaque
caractère, et une autre colonne contenant le rapport entre le nombre total 
d'occurrences
du caractère et le nombre total de caractères des textes de tout le corpus.

1.3 Compression

La compression par codage arithmétique consiste à représenter une chaîne de 
caractères
s par un nombre réel déterminé à l'intérieur de l'intervalle [0;1{.

Initialement, on attribue à chaque caractère utile une portion de l'intervalle 
[0;1|
proportionnelle à sa fréquence d'occurrences. Par exemple, pour un alphabet à 5 
lettres
'abcde', on pourrait avoir un tableau comme ci-dessous :

Caractère 'a! 'b' 'c' 'd' 'e!
Fréquence 0.2 0.1 0.2 0.4 0.1
Intervalle | [0;0.2! | [0.2;0.3[ | [0.3; 0.5[ | [0.5; 0.9[ | [0.9; 1!

La chaîne de caractères s est codée en partant de l'intervalle {0;1|. À chaque 
caractère
successif de celle-ci, on affine cet intervalle en ne considérant que la 
portion correspondant
au caractère lu.

Si par exemple la chaîne à coder est s = 'dac' :

-- 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! correspon-

dant à la portion associée au caractère 'a'.
-- le caractère 'c' détermine enfin l'intervalle [0.524; 0.540{.
La figure qui suit illustre ce processus.

1 0.9 0.58
e e e

0.9 0.86 0.576
d d d

0.5 0.7 0.54
C C C

0.3 0.62 0.524
b b b

0.2 0.58 0.516
à à a

0 0.5 > 05

FIGURE 2 -- Encodage de s = 'dac!
LH Q10 - En considérant la table des fréquences précédente, proposer 
l'intervalle corres-
pondant à la chaîne s='bac'.

On suppose disposer d'une fonction codeCar(car:str,g:float,d:float)-> (float , 
float)
qui prend en argument un caractère car et les deux extrémités d'un intervalle 
[9, d|
et qui renvoie un tuple composé des extrémités du sous-intervalle de |g,d| 
déterminé
par le caractère car. En reprenant l'illustration précédente codeCar('b',0,1) 
produit
(0.2,0.3) et codeCar('a',0.5,0.9) produit (0.5,0.58).

© Q11 - Écrire une fonction codage(s:str) ->(float float) prenant en argument 
la chaîne
s et fournissant en réponse le tuple (g,d) constitué des deux extrémités de 
l'intervalle
19, d\ produit par l'algorithme de codage précédent.

Le codage arithmétique consiste alors à coder la chaîne s par un flottant x 
choisi
arbitrairement à l'intérieur de l'intervalle [g, d|.

1.4 Décodage

Pour effectuer le décodage d'un flottant x, il suffit de repérer dans quelle 
succession
d'intervalles celui-ci se trouve.
À titre d'exemple, reprenons le tableau précédent et considérons le nombre 
x=0.123

Caractère 'a! 'b' 'c' 'd' 'e!
Fréquence 0.2 0.1 0.2 0.4 0.1
Intervalle | [0;0.2! | [0.2;0.3[ | [0.3; 0.5[ | [0.5; 0.9[ | [0.9; 1!

Puisque x appartient à l'intervalle {[0;0.2/, le premier caractère est un ''a'. 
Puisque x
appartient au sous-intervalle [0.10; 0.18{, le caractère suivant est un "d', 
etc.

LH Q12 --- Déterminer le caractère qui suit ''ad' dans la chaîne codée par 
x=0.123 en
spécifiant le sous-intervalle qui a permis de décoder ce caractère.

LU Q13 --- Dans le cadre de l'exemple de cette partie, indiquer deux chaînes 
qui peuvent
correspondre au flottant 0.2. Expliquer par une phrase ce qui est à l'origine 
de cette
ambiguité.

Une solution possible pour résoudre le problème précédent consiste à introduire 
un
caractère nouveau signifiant la fin de la chaîne de caractères.

Nous conviendrons de désigner ce caractère par '#'. Ce caractère se voit 
attribuer une
plage non vide au voisinage de 0. Dans la suite, on suppose que la table des 
fréquences est
adaptée de sorte à prendre en compte la présence de ce nouveau caractère.

On suppose disposer, en plus de la fonction codeCar(car,g,d) précédente, d'une 
fonc-
tion decodeCar(x:float ,g:float ,d:float)->str qui détermine le caractère 
correspondant
à la valeur x quand celle-ci est comprise dans la plage de [g, d].

Par exemple decodeCar(0.123,0,1) donne 'a' tandis que decodeCar(0.123,0,0.2)
donne le caractère "d'.
D 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).

Le codage précédent ne fonctionne que sous l'hypothèse illusoire d'exactitude 
des
calculs jusqu'à une très grande précision. Cette précision est cependant 
limitée par la
taille de la mantisse représentant un réel et il ne peut être mis en oeuvre 
sous la forme
précédente qu'avec des chaînes relativement courtes. Pour résoudre cette 
difficulté, on
adopte un codage en arithmétique entière : au lieu de considérer un intervalle 
flottant |0, 1{,
c'est un intervalle entier 000; 999] qui est utilisé. Cette technique ne sera 
pas abordée
dans le cadre de cette épreuve de durée limitée.

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

Dans cette partie, nous allons désormais considérer que le message compressé 
par Alice
a été envoyé au travers d'un canal de communication. À cette fin, et 
indépendamment de
la phase de compression étudiée dans la première partie, le message a subi une 
deuxième
phase de transformation, dite d'encodage (cf Figure 1).

Le message envoyé sur le canal est une suite de symboles à valeurs dans un 
alphabet,
noté », comportant X symboles. Le choix d'un alphabet efficace n'est pas 
l'objet de notre
étude et constitue un sujet à part entière.

Suite au passage dans le canal de communication, le message envoyé subit une 
alté-
ration de sorte que Bob reçoit une séquence de symboles de Ï qui ne correspond 
pas
nécessairement à celle qui a été émise.

Dans cette partie, nous allons voir une approche permettant à Bob de décoder le
message reçu et de potentiellement corriger quelques erreurs liées à la 
transmission du
message et à la connaissance a priori de la propension du canal de 
communication à altérer
les symboles du message lors de la transmission.

La modélisation proposée est la suivante :

-- Bob observe une suite de V symboles obso,...,0bsn_1, que nous allons 
représenter
par une liste Python Obs --{[obs5, ...obsn_1|,

-- pour simplifier, on supposera que l'alphabet À est un ensemble de Æ entiers
consécutifs commençant à 0, de sorte que Y = ]0, X -- 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,01].

-- chacun des symboles observés obs, correspond à l'altération d'un symbole s, 
envoyé
par Alice. On note {$5,...sn_1] le message original; pour reprendre l'exemple
précédent, Alice pourrait avoir envoyé [2,0,0,2,1,1,2,01].

-- on connaît, pour chaque paire (4, j) EUR X*, la probabilité E;; que le canal 
altère le
symbole j en un symbole 5. On stocke ces probabilités dans une liste de listes 
E:
autrement dit, Eli] [j] est la probabilité conditionnelle d'observer le symbole 
2
sachant que le symbole 7 a été émis.
0.7 0.2 0.3
Ici (par exemple) on pourrait considérer : E = [0.2 0.7 0.1 |, représentée par
0.1 O.1 0.6
la liste de listes : E = [[0.7,0.2,0.3],[0.2,0.7,0.1]1,[0.1,0.1,0.6]].

Le fait que E|2[[0] vaille 0.1 signifie donc que la probabilité que le symbole
observé par Bob soit un 2 sachant qu'Alice a émis un 0 est de 0.1.

-- on suppose également que le symbole courant 5; envoyé par Alice a une 
incidence
sur le symbole suivant s,,, 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'.

Ainsi pour chaque couple de symboles (1, j) EUR X°, on suppose que l'on connaît
la probabilité d'émettre le symbole 7 à l'instant t + 1 sachant que symbole 2 a 
été
émis à l'instant {. On suppose également que cette probabilité ne dépend pas de 
£.

L'information concernant ces probabilités de transition d'un symbole à l'autre
peut se stocker dans une matrice P de taille À X K°, que l'on représente 
informa-
tiquement par une liste de listes P. Chaque entrée P[i] 1j] donne la probabilité
qu'Alice émette le symbole 7 à l'instant { + 1 sachant qu'elle à émis le 
symbole à à
l'instant t. En d'autres termes, P[i]|j] = P,,-;(s;11 = 3).

0.3 0.2 0.5
On prendra ici à titre d'exemple : P = [0.4 0.4 0.2 |, représentée par la liste
0.2 0.3 0.5
de listes : P=[[0.8,0.2,0.5],[0.4,0.4,0.2],[0.2,0.3,0.5]].

Le fait que P|2[[0] vaille 0.2 signifie donc que la probabilité que le symbole
envoyé par Alice à l'instant { + 1 soit un 0 sachant que celui envoyé à 
l'instant t est
un 2 vaut 0.2.

Nous allons désormais nous intéresser au problème du décodage : étant donné la 
liste

Obs = [obs9,...,obsx_1| des symboles observés par Bob, quelle séquence 
80,...,8n_1 est
la plus probable ?

En d'autres termes, $0,...,S5n_1 est l'estimation la plus probable faite par 
Bob du
message d'origine 59,...,S8n_1. étant donné les observations 0b50,...,0bSN-1.

La modélisation précédente peut se représenter à l'aide d'un graphe défini 
comme suit
(voir Figure 3 pour un exemple) :

-- on crée un sommet S;; pour chaque symbole possible 0 < 4 < K°-- TI et chaque indice d'observation 0 < 7j < 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 $;; pour 7 < N -- I ont pour successeurs les états S,,.1 pour tous les symboles £ possibles, -- par commodité, on ajoute un état source o correspondant au début du message décodé et un état cible 7 correspondant à la fin du message, ces états étant respectivement reliés à la première et la dernière couche, -- Je décodage du message envoyé par Alice correspond à un chemin entre © et 7 dans ce graphe. À chaque sommet du chemin correspond une lettre décodée. Par exemple, le chemin passant par 50,0, S21, S0.2, S13, Correspond au décodage de |0,2,0, 1}. symbole 0 symbole 1 @ -@ eo e ee e >@
ne 51,2 ra?
symbole 2 (> =) =) -- e
52,2 S2,N-1
| | | En
| | | |
obSo Obs: ObS9 ObSN 1

FIGURE 3 -- lilustration du modèle de décodage considéré ici.

À chacune des observations obs; on peut faire correspondre Æ états. Chacun de 
ces états
correspond à l'un des symboles potentiellement émis par Alice (ici K -- 3). Les 
états sont
organisés en {V couches successives. Chaque état est noté 5; ;; 7 correspond à 
l'indice dans
la suite des symboles émis et ? au symbole correspondant. Les états de la 
couche 7 et les
états de la couche 7 + 1 sont reliés par un arc de j vers 7 + 1. On ajoute 
également, par
commodité, un état source © et un état cible 7 respectivement reliés à la 
première et à la
dernière couche.

LU Q15 - En fonction de NN et de K, donner le nombre de sommets et d'arcs du 
graphe
illustré par la Figure 3. On ne comptera pas les sommets source o et cible 7, 
ni les arcs
partant du sommet source o ni ceux arrivant à la cible 7.

On choisit désormais de pondérer chaque arc par la probabilité de transiter par 
cet arc.
Autrement dit :
-- les arcs issus de la source à vers S;0 sont pondérés par E4,: la probabilité 
d'observer
le symbole obs, sachant que le symbole a été émis par Alice :
-- les arcs arrivant à la cible 7 sont pondérés par 1 (en fin de message, on 
transite
forcément vers l'état final),
-- les arcs internes entre 5; ; et 57,41 sont pondérés par la probabilité Es, 
Pi.
La probabilité d'un chemin 05,055, 1...5;, ..N-17 entre © et 7 est le produit 
des
probabilités des arcs qui le composent.
L'objectif va être de trouver le chemin de probabilité maximale dans ce graphe 
entre
le sommet source © et le sommet cible 7.

LH Q16 --- On suppose que Bob a observé la séquence [2,0]. En utilisant les 
matrices E et
P données dans l'énoncé (avec K -- 3), construire le graphe pondéré associé à 
ce message
de longueur NV = 2. Les arcs entre les sommets devront être pondérés par les 
probabilités
correspondantes.

LU Q17 -- On revient dans le cas général, N et K sont désormais quelconques. 
Indiquer
combien il existe de chemins entre © et 7 (un ordre de grandeur utilisant la 
notation © ou
O est accepté). Préciser si un algorithme d'exploration exhaustive est 
envisageable dans ce
CAS.
2.2 Stratégie gloutonne

Pour pouvoir implémenter correctement la recherche du chemin de probabilité 
maximale,
il est utile de disposer d'une fonction auxiliaire qui sera utilisée dès que 
nécessaire.

LU Q18 - Pour une liste liste, on appelle argument du maximum et on note argMax 
tout
indice 2? tel que lListe[i] soit maximal. Proposer une fonction
maximumListe(liste:/[float])->(float,int) qui prend en entrée une liste de 
nombres et
qui renvoie la valeur du maximum de la liste ainsi que le plus petit argument 
du maximum.
i.e. le premier indice auquel cette valeur maximale apparaît.

On souhaite appliquer un algorithme glouton pour trouver le chemin de 
probabilité
maximale entre le sommet source © et le sommet cible 7. On rappelle qu'un 
algorithme
glouton cherche, à chaque étape, à faire le choix localement optimal. Ici, si à 
une étape on
se retrouve au sommet S;,;, il s'agit de choisir l'arc de plus forte 
probabilité partant de ce
sommet.

Dans un premier temps on écrit une fonction

initialiserGlouton(Obs:/[[int]], E:[[float]], K:int)->int qui permet d'initiali-
ser l'algorithme glouton en trouvant le sommet le plus probable parmi $;0 pour 
? variant
entre 0 et À -- 1. Pour cela il faut regarder la colonne Obs [O0] de E et 
relever l'indice de la
plus grande valeur.

: def initialiserGlouton(Obs, E, K):

2 probasInitiales = [E[Obs[0][i]] for i in range(K)]
3 s, Symbole = maximumListe(probasInitiales)
4 return symbole

LU Q19 - Proposer une fonction
glouton(Obs: [int] ,P: [[float]],E: [[float]] ,K:int,N:int)-> [int] qui renvoie 
la liste
d'états obtenue par l'approche gloutonne. Même si cela n'est pas nécessaire, À, 
N seront
des arguments de cette fonction.

LU Q20 - En fonction de K et de N, quelle est, en ordre de grandeur, la 
complexité
temporelle asymptotique de l'approche gloutonne ?

LU Q21 - Indiquer le chemin renvoyé par l'algorithme glouton appliqué à la 
Figure 4.
Conclure quant à l'optimalité de l'approche.

symbole 0 e 0.5 |
0.6
O.Ï
e (D
0.4 il
symbole 1 >
ù So ©

FIGURE 4 -- Que donne l'algorithme glouton ici ?

10
2.3 Stratégie de programmation dynamique

LU Q22 - Expliquer en quoi rechercher un chemin de probabilité maximale 
pourrait se
transformer en un problème de recherche de plus court chemin dans un graphe 
pondéré à
poids positifs. Préciser alors quel algorithme pourrait être utilisé.

Les algorithmes évoqués à la question précédente ne sont cependant pas optimaux 
dans
ce cas. L'algorithme optimal est dû à Andrew Viterbi et date de 1967. IL repose 
sur le
paradigme de la programmation dynamique.

On appelle T;; la valeur de probabilité maximale entre la source et l'état 
$;,;. On peut
alors établir l'équation de programmation dynamique suivante :

Ti; -- LDex {Te5-1 X Fri X Eos, à} SN---12>7>0
Lio -- Eobso.i

Comme on cherche également à obtenir la valeur des états correspondant au chemin
optimal, on maintient également le tableau des prédécesseurs suivant :

arglT;; = argmax 47%,;_1 X Ph; X Emssit SN--1237>0
>] >] , VE
kEÏ0,K--1]

arglLio = --1
La valeur --1 du deuxième tableau est purement conventionnelle et ne sert qu'à
représenter l'état source o qui ne correspond pas à une observation.

On suppose avoir codé une fonction
initialiserViterbi(E:[[float]], ObsO:int, K:int, N:int)->([[float]],[[int]]) qui
prend en entrée la matrice E d'émission, la valeur de la première observation 
Obs0, le
nombre d'éléments K de Y, le nombre d'observations N et qui renvoie deux 
tableaux (liste
de listes) T et argT vérifiant les caractéristiques suivantes :
-- Tet argT sont de dimensions À lignes par N colonnes,
-- Tli] [0] contient la valeur de Es à,
-- argT{i] [0] contient la valeur --1,
-- les autres valeurs de T et argT sont à 0.

En voici une implémentation possible :

: def initialiserViterbi(E, ObsO, K, N):

2 probasInitiales = [E[ObsO][i] for i in range(K)]
3 T = [[O for j in range(N)] for i in range(K)]

' argT = [[0 for j in range(N)] for i in range(K)]
5 for i in range (K) :

6 T[i][0] = probasInitiales{il]

7 argT[i][O] = -1

8 return T, argT

1 Q23 - Proposer une fonction (méthode de bas en haut de programmation 
dynamique)
construireTableauViterbi(Obs:[int], P:[[float]], E:[[float]], K:int, N:int)
--->([[float]],[{int]]) qui prend comme arguments la liste des observations 
Obs, la matrice
des probabilités de transition P et la matrice des probabilités E et renvoie 
les deux listes
de listes T et argT de taille À x N.

LU Q24 --- L'alsorithme de Viterbi codé en Python et appliqué à un message en 
entrée

11
donne les tableaux T et argT suivants. Indiquer la séquence d'états la plus 
probable.

0.1 0.084 O.018 0.000353 O.00021 8.Je -- 05 8.7e -- 035 1.8e -- 05
T= | 0.1 0.036 O.0054 O.OO04T O.O0I1 0.000351 2.5e -- 05 3.5e -- 06
0.6 0.09 O.014  0.0053 0.00026 2.2e -- 035 19e --035 1.3e -- 05

--1 20 0 2 I 1 O0

argl = | --1 2 2 2 2
2

= Ha
= Ha
© ©

D Q25 --- En fonction de K et de NW, donner l'ordre de grandeur de la 
complexité temporelle
de l'approche de programmation dynamique, ainsi que la complexité spatiale.

Fin de l'épreuve.

12