Задание 5. Кодирование и расшифровка сообщений: демонстрационный вариант егэ информатика 2019; государственный выпускной экзамен 2019; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2019
*** КАНАЛ ЮТЬЮБ ***
ЕГЭ по информатике -> ЕГЭ 2019 -> ЕГЭ 2019
Разбор 5 задания. Демоверсия егэ по информатике 2019:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10.
Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
📹 Видеоразбор демоверсии егэ 2019
✍ Решение:
- Построим дерево, в котором расположим известные кодовые слова:
- По условию Фано получаем, что там, где уже есть лист дерева (кодовое слово), продолжать дерево нельзя. С учетом этого продолжим дерево для остальных кодовых слов:
- Для удобства подсчета разместили уровни. Теперь подсчитаем сумму длин кодовых слов для 4-х добавленных букв:
4(буквы) * 4(уровень) = 16
Результат: 16