Задача 2.5.1. Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее трёх и не более пяти сигналов (точек и тире)?
Задача 2.5.2. Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех): К – 000, М – 10, А – 111, Р – 01, И – 101 . Из четырех сообщений в этом коде только одно прошло без ошибки и может быть корректно декодировано. Найдите его.
- 11001011011
- 0001011111
- 100011101
- 0111110000111
Задача 2.5.3. Некоторые буквы русского алфавита закодировали неравномерным кодом (по две и три двоичные цифры): А – 010, Б – 111, В – 10, Г – 01, Д – 00. Напишите без пробелов букву, в которой для корректного декодирования нужно добавить третью цифру, и букву, в которой третья цифра избыточна для корректного декодирования.
Теория. Чтобы было возможно однозначное декодирование, нужно, чтобы ни одна буква не была началом другой буквы. Это называется условием Фано.
Пример, когда условие Фано не выполняется:
A – 01
В – 010
С – 1
Сообщение 0101 Может быть декодировано двумя способами:
АА
Или
BC
На практике вы сталкивались с условием Фано при наборе телефонного номера. Есть короткие зарезервированные номера 01, 02, 03. И ни один другой номер не начинается с 01, 02, 03.
Задача 2.5.4. По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова:
A – 1, B – 010, C – 000.
Укажите кратчайшее кодовое слово для буквы E, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание 1. Если бы в задаче не было бы буквы С, то есть алфавит состоял бы только из A, B, D, E, нам не обязательно было бы ветвить 0 на втором уровне, и код для буквы С был бы 00.
Примечание 2. Для решения задачи мы воспользовались графической схемой – деревом, которое используется для множества других задач в ЕГЭ. То есть мы перешли к следующему разделу – задачам, которые решаются с помощью деревьев и графов.
Задача 2.5.5. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г – 110, И – 01, Т – 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
