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 \((7 * 3 + 3 * 5) * 0.1 = 3.6\). Donc le second est plus efficace. Si J a une probabilité d’apparition de 0.3, le calcule devient : \(7 * 3 * \frac{0.5}{9} + 2 * 5 * \frac{0.5}{9} + 5 * 0.3 \sim 4.22\).

[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'}
---
[ ]:


Notebook on github