4.04 Редактирование кодовых слов
Ошибка.
Попробуйте повторить позже
Крабоед решил списать решение задачи у одноклассника, но он ошибся. Необходимо найти ошибку в решении Краба и записать её в ответ. Известно, что задача была составлена на проверку знания прямого условия Фано.
Сообщение кодируется с помощью символов 
. Для каждой буквы выделено кодовое слово: 
— 
, 
—
, 
— 
, 
— 
.
В ответ запишите ошибочное кодовое слово с наименьшим количеством символов.
Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Так как буква 
начинается так же, как и буква 
одно кодовое слово неверно. Так как просят код с наименьшим
количеством символов — в ответ идёт 
.
Ошибка.
Попробуйте повторить позже
Для кодирования некоторой последовательности, состоящей из букв А, В, С, D, E используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 011; B — 000; C — 001; D — 100; E — 101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. В ответе запишите букву и новый код (без пробелов). Если таких букв несколько, то записать ту, что идет позже по алфавиту.
Есть возможность сократить кодовое слово для буквы A до 01, конфликтов никаких не будет, кодовых слов с таким началом нет. Смотрим дальше.
В B и C сократить до 00 не получится, так как эти слова начинаются одинаково. Если попробовать сократить B до 01, то будет конфликт с буквой A.
Кодовое слово для D сократить не получится, так как начало 00 у других слов уже есть, а 10 является началом для E.
В кодовом слове для E нельзя сократить до 01 или 10, но можно сократить до 11, так как нигде такого начала нет, это и есть наш ответ.
Ошибка.
Попробуйте повторить позже
По каналу связи передаются сообщения, содержащие только пять букв: Б, У, Л, К, А. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А - 110, Б - 101, К - 1001, Л - 011, У - 010. Как можно сократить код для буквы Л, чтобы сохранялось свойство однозначности декодирования? Если таких кодов несколько, в качестве ответа указать код наименьшей длины.
Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
После составления дерева Фано можно заметить, что остались свободными ветви 1000, 111 и 00. Из них наименьшую длину имеет код 00 и он не будет нарушать условие Фано, так как до него ни один код не начинается с 00.
