Задание 4 Вариант 1 Самостоятельная работа 2 ГДЗ Рабочая тетрадь Босова 10 класс (Информатика)
Босова, Босова, Лобанов
10 класс
Класс
10
Предмет
Информатика
Автор
Босова, Босова, Лобанов
Задание 4 Вариант 1 Самостоятельная работа 2 ГДЗ Рабочая тетрадь Босова 10 класс (Информатика)
Задача
- Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б и В использовали такие кодовые слова: А — $$0$$, Б — $$10$$, В — $$110$$. Какими кодовыми словами могут быть закодированы буквы Г и Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать разные варианты кодовых слов, укажите кратчайшие из них. Решение задачи представьте с помощью бинарного дерева.
Подробный ответ
Чтобы код был однозначно декодируемым, нужно выполнить прямое правило Фано: ни одно кодовое слово не должно быть началом другого.
Даны коды:
А — $$0$$, Б — $$10$$, В — $$110$$.
Тогда для букв Г и Д нужно выбрать самые короткие коды, которые не начинаются с уже занятых кодов и сами не являются началом других кодов. После $$0$$ нельзя брать коды, начинающиеся с $$0$$, а после $$10$$ и $$110$$ остаются подходящие продолжения ветви $$111$$.
Подойдут коды:
- Г — $$1110$$
- Д — $$1111$$
Такое кодирование можно изобразить бинарным деревом: коды $$0$$, $$10$$, $$110$$, $$1110$$ и $$1111$$ занимают разные листья дерева, поэтому двоичная последовательность декодируется однозначно.
Ответ: Г — $$1110$$, Д — $$1111$$.
Другие учебники
Другие предметы