Главная / Задания ЕГЭ / Задание 4

Задание 4 ЕГЭ по информатике

Кодирование и условие Фано. Нужно найти наименьшую длину кодового слова или суммарную длину кодов при неравномерном двоичном коде, удовлетворяющем условию Фано.

Решать задание 4 в тренажёре Пробный урок с преподавателем

Как решать

Постройте двоичное дерево по известным кодам.
Никакой код не может быть началом другого кода.
Свободные короткие ветви отдайте самым частым буквам.

Частые ошибки

Занимают ветку, которая является началом уже известного кода.

Пример задания

По каналу связи передаются сообщения, содержащие все буквы русского алфавита. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: З — 011, Д — 111, П — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ПОЕЗД?

Показать ответ и разбор

Ответ: 14

Длины кодов букв слова: П: 3 (дан), О: 2, Е: 3, З: 3 (дан), Д: 3 (дан). Свободные короткие позиции дерева отдаём самым частым буквам. Итого 3 + 2 + 3 + 3 + 3 = 14.

В тренажёре каждый раз новое задание этого типа: ответ проверяется сразу, после ответа виден короткий разбор.

Все задания ЕГЭ

Нужна помощь с ЕГЭ?

На пробном уроке посмотрим ваш уровень по 2–3 темам ЕГЭ по информатике и составим план подготовки.

Записаться на пробный урок