1A.algo - Décoder du Morse sans espaces

Links: notebook, html ., PDF, python, slides ., GitHub

Le code Morse était utilisé au siècle dernier pour les transmissions. Chaque lettre est représentée par une séquence de points et tirets. Comment décoder ce code ? Notion abordée : graphe, programmation dynamique, trie.

from jyquickhelper import add_notebook_menu
add_notebook_menu()
Plan
run previous cell, wait for 2 seconds
from IPython.display import Image
Image("330px-International_Morse_Code-fr.svg.png")
../_images/exercice_morse_2_0.png

On se propose de répondre à deux questions :

Enoncés

Exercice 1 : Traduire un texte Morse qui ne contient pas d’espace

Ce sujet est un exercice classique de programmation. Il est déjà résolu et expliqué sur Codingame.

Exercice 2 : calculer l’alphabet qui minimise une transcription

Cette optimisation est possible puisque l’alphabet Morse transcrit les lettres avec des codes de longueurs différentes. Il faudra aussi vérifier qu’une fois l’alphabet choisi, il n’autorise qu’un seul décodage de la transcription. On suppose qu’on conserve les contraintes du Morse : chaque lettre de l’alphabet est constituée de traits courts et long et qu’il n’y a pas de séparation entre lettres. Vous pouvez vous inspirez de cet article sur la Compression de données ou celui sur le code de Huffman.

Solutions

Solution au problème 1

Solution au problème 2