Задание 4 Вариант 1 Самостоятельная работа 2 ГДЗ Рабочая тетрадь Босова 10 класс (Информатика)

Какими кодовыми словами могут быть закодированы буквы Г и Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать разные варианты кодовых слов, укажите кратчайшие из них.
Решение задачи представьте с помощью бинарного дерева.
В данном случае надо добиться выполнения прямого правила Фано, ни один код не является началом другого. Обратное правило Фано уже не выполняется на приведенных кодах.
На 0 больше ни один код не может начинаться т.к. уже есть код 0!
Ответ: для Г код 1110, для Д 1111

Чтобы двоичный код можно было однозначно декодировать, он должен удовлетворять прямому правилу Фано: ни одно кодовое слово не должно быть началом другого.

Даны коды:

$$A = 0,\quad Б = 10,\quad В = 110.$$

Так как код $$0$$ уже занят, другие кодовые слова не могут начинаться с $$0$$. Значит, для букв $$Г$$ и $$Д$$ нужно выбрать коды, начинающиеся с $$111$$, чтобы они не были началом друг друга и не нарушали условие однозначного декодирования.

Кратчайшие подходящие кодовые слова:

$$Г = 1110,\quad Д = 1111.$$

Это можно представить в виде бинарного дерева: по ветви $$0$$ идёт буква $$A$$, по ветви $$10$$ — буква $$Б$$, по ветви $$110$$ — буква $$В$$, а оставшиеся два листа на ветвях $$1110$$ и $$1111$$ соответствуют буквам $$Г$$ и $$Д$$.

Ответ

$$Г = 1110,\quad Д = 1111.$$