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

Кодирование, условие Фано

1 балл ≈ 2 мин уровень Б Кодирование и декодирование, условие Фано

Задание 4 – двоичное неравномерное кодирование с условием Фано. Нужно найти наименьшую длину кодового слова, наименьшую суммарную длину кодов или длину сообщения. 1 балл.

Условие Фано: никакое кодовое слово не является началом другого кодового слова. Такой код однозначно декодируется.

Метод – двоичное дерево

Нарисуй дерево: от корня влево – 0, вправо – 1. Каждое кодовое слово – лист (конец пути).
Отметь известные коды. Узлы на пути к ним заняты, ниже них ничего ставить нельзя.
Найди свободные ветки – узлы, которые не являются ни кодом, ни префиксом кода. Каждый свободный узел длины k даёт возможный код длины k.
Если нужно разместить несколько букв, а свободных узлов мало – раздели свободный узел: вместо кода длины k получаешь два кода длины k + 1.
Для наименьшей суммарной длины – занимай самые короткие свободные узлы.

Разобранный пример. Буквы А, Б, В, Г, Д. Известно: А – 00, Б – 01, В – 101. Найди наименьшую суммарную длину кодов Г и Д.

Ветка 0 полностью занята (00 и 01). Ветка 1: занят узел 10 (префикс 101), значит, свободны узлы 11 (длина 2) и 100 (длина 3). Г – 11, Д – 100. Сумма: 2 + 3 = 5.

Если нужна длина сообщения: умножь длину кода каждой буквы на число её вхождений и сложи. Чаще встречающимся буквам давай более короткие коды.

Ловушки: поставить новый код, началом которого является уже существующий (например, 1010 при наличии 101); забыть, что один свободный узел можно разделить на два более длинных; путать «наименьшую длину кода одной буквы» и «суммарную длину».

На экзамене

Всегда рисуй дерево – на это уходит минута, а ошибок почти не остаётся.
Код, состоящий из одних нулей или одних единиц длины 1, «съедает» половину дерева – с ним осторожно.
Проверь итог: ни один код не должен начинаться с другого.

Разобранные задания 4 из открытого банка ФИПИ

Пример 1 · код ФИПИ A1A6CB

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква	Кодовое слово	Буква	Кодовое слово
А	00	Л	1101
Б	1100	Р	1000
Е	010	С	1110
И	011	Т	1001
К	1111	У

Укажите кратчайшее кодовое слово для буквы У, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код
с наименьшим числовым значением.

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Показать ответ и решение

Ответ: 101

Коды длины 1–2 невозможны: «0», «1», «01», «10», «11» являются началами имеющихся кодов. Свободен код длины 3 – 101 (ни один код не начинается с 101, и ни один не является его началом).

Пример 2 · код ФИПИ 76E4A0

По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код. Для букв А, Б и В используются кодовые слова 001, 010, 0111 соответственно.

Укажите минимальную сумму длин кодовых слов для букв Г и Д, при которых код будет удовлетворять условию Фано.

Показать ответ и решение

Ответ: 4

Свободны ветви 1, 000 и 0110. Г=1, Д=000 – сумма 1+3=4 (или 10 и 11 – тоже 4).

Пример 3 · код ФИПИ B3e888

По каналу связи передаются сообщения, содержащие только буквы из набора: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б $-$ 00, Н $-$ 010, Л $-$ 111. Для двух оставшихся букв К и О кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова КОЛОБОК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Показать ответ и решение

Ответ: 17

Свободны 011, 10, 110. О=10, К=011 (или 110).

КОЛОБОК: $2 \cdot 3 + 3 \cdot 2 + 3 + 2 = 17$ .

Частые вопросы о задании 4

Сколько баллов даёт задание 4 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 2 мин. Уровень сложности – Б.

Что проверяет задание 4?

Как подготовиться к заданию 4?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.