1A - Enoncé 8 novembre 2023-2024¶
Exercice 1 : décodage façon Morse¶
Une langue étrangère s’écrit avec 10 lettres ABCDEFGHUIJ. Chacune est représentée par 4 bits.
[13]:
code_def = """
A 0000
B 0001
C 0010
D 0011
E 0100
F 0101
G 0110
H 0111
I 1000
J 1001
"""
Ou encore.
[14]:
code_def = {
"A": "0000",
"B": "0001",
"C": "0010",
"D": "0011",
"E": "0100",
"F": "0101",
"G": "0110",
"H": "0111",
"I": "1000",
"J": "1001",
}
Q1 : Ecrire une fonction qui code une séquence de lettres en une séquence de 0 et 1.¶
[25]:
def code(text):
return "".join(code_def[c] for c in text)
assert code("AG") == "00000110"
Q2 : On s’intéresse au décodage d’un message.¶
Première étage : écrire une fonction qui retourne la première lettre correpondant au premier code qui commence un message codé.
[26]:
def first_letter(chaine):
for k, v in code_def.items():
if chaine.startswith(v):
return k
assert first_letter("10010001") == "J"
Q3 : Ecrire une fonction qui reçoit une séquence de 0 et de 1 et retourne la séquence de lettres correspondante.¶
[27]:
def decode(chaine):
res = ""
while len(chaine) > 0:
found = None
for k, v in code_def.items():
if chaine.startswith(v):
found = k
if found is None:
return None
res += found
chaine = chaine[len(code_def[found]) :]
return res
assert decode("00000110") == "AG"
On peut utiliser le fait que toutes les lettres sont représentées par des séquences de 4 bits mais la fonction est spécifique au premier code et ne marcherait pas dans les autres cas.
[17]:
code_def_inverse = {v: k for k, v in code_def.items()}
def decode_rapide(chaine):
res = ""
for i in range(0, len(chaine), 4):
res += code_def_inverse[chaine[i : i + 4]]
return res
assert decode_rapide("00000110") == "AG"
Q4 : On forme une classe avec les deux fonctions précédentes. Il faut compléter le code suivant.¶
[35]:
class Coding:
def __init__(self):
self.mapping = {
"A": "0000",
"B": "0001",
"C": "0010",
"D": "0011",
"E": "0100",
"F": "0101",
"G": "0110",
"H": "0111",
"I": "1000",
"J": "1001",
}
self.inverse = {v: k for k, v in self.mapping.items()}
def code(self, text):
return "".join(self.mapping[c] for c in text)
def first_letter(self, chaine):
for k, v in self.mapping.items():
if chaine.startswith(v):
return k
return None
def decode(self, chaine):
if len(chaine) == 0:
return ""
letter = self.first_letter(chaine)
if letter is None:
return None
suite = self.decode(chaine[len(self.mapping[letter]) :])
if suite is None:
return None
return letter + suite
cl = Coding()
assert cl.code("AG") == "00000110"
assert cl.decode("00000110") == "AG"
Q5 : On veut réduire la taille du message codé.¶
Les lettres de A à G sont maintenant codées sur 3 bits et les suivantes sur 5. On change juste le dictionnaire de la classe.
[36]:
class Coding35(Coding):
def __init__(self):
self.mapping = {
"A": "000",
"B": "001",
"C": "010",
"D": "011",
"E": "100",
"F": "101",
"G": "110",
"H": "11100",
"I": "11101",
"J": "11110",
}
self.inverse = {v: k for k, v in self.mapping.items()}
cl = Coding35()
assert cl.code("AH") == "00011100"
assert cl.decode("00011100") == "AH"
Q6 : Que fait la fonction suivante ?¶
Que suppose-t-elle sur la méthode decode pour qu’elle fonctionne.
[38]:
def which_coding(text, codings):
return [c for c in codings if c.decode(text) is not None]
codings = [Coding(), Coding35()]
assert which_coding("0000", codings) == codings[:1]
La fonction retourne la liste des codes qui peuvent décoder un message. Elle suppose que la méthode decode retourne None lorsqu’elle ne peut décoder un message.
Q7 : Dans ce langage, les lettres sont toutes équiprobables¶
Quel code est le plus court pour un texte aléatoire très grand et quantifier le gain ? Que se passe-t-il si la lettre J a une probabilité de 0.3 et toutes les autres lettres ont la même probabilité d’apparition ? Que suggérez-vous pour optimiser le Coding en terme de longueur ?
La probabilité des lettes est uniforme, donc égale 0.1. Avec le premier code, la longueur moyenne d’une lettre codé est 4. Avec le second c’est 
. Donc le second est plus efficace. Si J a une probabilité d’apparition de 0.3, le calcule devient : 
.
[20]:
7 * 3 * 0.5 / 9 + 2 * 5 * 0.5 / 9 + 5 * 0.5
[20]:
4.222222222222222
Pour optimiser, il faut donner le code le plus court aux lettres les plus probables.
[21]:
6 * 3 * 0.5 / 9 + 3 * 5 * 0.5 / 9 + 3 * 0.5
[21]:
3.3333333333333335
Q8 : On change le Coding des lettres A et B¶
A 00 et B 01.
Il faut créer une troisième classe héritant de la première. Que valent c.code("BGBB") et c.code("DEF") ? Que retourne votre méthode decode ?
[22]:
class Coding235(Coding):
def __init__(self):
self.mapping = {
"A": "00",
"B": "01",
"C": "010",
"D": "011",
"E": "100",
"F": "101",
"G": "110",
"H": "11100",
"I": "11101",
"J": "11110",
}
self.inverse = {v: k for k, v in self.mapping.items()}
c = Coding235()
assert c.code("BGBB") == "011100101"
assert c.code("DEF") == "011100101" # c'est la même chose
Q9 : Dans le cas précédent, la première lettre peut être soit B soit D.¶
Ecrire une méthode qui retourne toutes les options pour la première lettre d’un message codé.
[23]:
class Coding235(Coding):
def __init__(self):
self.mapping = {
"A": "00",
"B": "01",
"C": "010",
"D": "011",
"E": "100",
"F": "101",
"G": "110",
"H": "11100",
"I": "11101",
"J": "11110",
}
self.inverse = {v: k for k, v in self.mapping.items()}
def first_letters(self, chaine):
found = []
for k, v in self.mapping.items():
if chaine.startswith(v):
found.append(k)
return set(found)
c = Coding235()
assert c.first_letters("011100101") == {"B", "D"}
Q10 : Ecrire une méthode…¶
decode qui retourne toutes les solutions par récurrence.
[24]:
class Coding235(Coding):
def __init__(self):
self.mapping = {
"A": "00",
"B": "01",
"C": "010",
"D": "011",
"E": "100",
"F": "101",
"G": "110",
"H": "11100",
"I": "11101",
"J": "11110",
}
self.inverse = {v: k for k, v in self.mapping.items()}
def first_letters(self, chaine):
found = []
for k, v in self.mapping.items():
if chaine.startswith(v):
found.append(k)
return set(found)
def decode(self, chaine):
solutions = []
found = self.first_letters(chaine)
for f in found:
end = chaine[len(self.mapping[f]) :]
if end == "":
solutions.append(f)
continue
suites = self.decode(end)
if len(suites) == 0:
continue
for s in suites:
solutions.append(f + s)
return set(solutions)
c = Coding235()
assert c.decode("011100101") == {"BGBB", "DEF"}
{'BGBB', 'DEF'}
---
[ ]: