Задание 1
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы В – 101
2) это невозможно
3) для буквы В – 010
4) для буквы Б – 10
Решение
Для решения задачи построим граф. Сначала возьмем 0, так как это буква А. Чтобы было однозначное кодирование, с нуля не должна начинаться никакая другая буква. Т.е. ноль после нуля идти не может, и один после нуля идти не может.
Основная ветвь у нас - единица. Имеются комбинации Б (100), В (1010), Г (111) и Д (110). Мы смотрим, где можно что-нибудь сократить. Сокращаем в ветви В последний участок. Таким образом В можно представить как 101.
Ответ: 1