Задание 4: Кодирование: условие Фано

Теория к заданию № 4 ЕГЭ-2027 по информатике: коротко правило, приём решения по шагам, два разобранных примера из банка «Ранга» и ошибки, на которых теряют балл.

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

Что проверяет
Умение кодировать и декодировать информацию: двоичные коды переменной длины, однозначное декодирование, условие Фано.
Баллы
до 1 балл из 29 первичных
Уровень
базовый
Время
около 2 минуты (примерное время по спецификации ФИПИ; на весь экзамен — 235 минут)
Формат
краткий ответ; решается и без программы

Правило и теория

  • Условие Фано: ни одно кодовое слово не является началом (префиксом) другого — тогда сообщение декодируется однозначно.
  • Код удобно изображать двоичным деревом: кодовые слова — листья; занятый лист «закрывает» всё поддерево под ним.
  • Неравенство Крафта: для префиксного двоичного кода Σ 2−li ≤ 1, где li — длины кодовых слов.
  • Чтобы суммарная длина сообщения была минимальной, частым буквам дают короткие коды (идея кода Хаффмана).
  • Наименьшая длина свободного кодового слова — ищи самый «верхний» свободный узел дерева.

Приём решения по шагам

  1. Нарисуй дерево уже известных кодовых слов.
  2. Найди свободные ветви, которые не являются ни началом, ни продолжением занятых слов.
  3. Распредели свободные коды по буквам: короче — тем, что встречаются чаще (если задана частота).
  4. Посчитай требуемую величину: длину слова, сумму длин или длину закодированного сообщения.

Два разобранных примера из банка «Ранга»

Сначала реши сам — потом раскрой ответ и разбор. Ответы взяты из банка, по которому работает тренажёр, и проверены.

Пример 1

По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, Л, М, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 00, К – 011, М – 110. Для букв Л, О и Р кодовые слова неизвестны. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МОЛОКО, если известно, что оно закодировано минимально возможным количеством двоичных знаков? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

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

Ответ: 15

Известные коды занимают ветви дерева 00, 011, 110. Свободные вершины дерева дают для неизвестных букв, например, коды: Л – 010, О – 10, Р – 111 — более короткие коды нарушили бы условие Фано (стали бы началом известного кода или наоборот), а частые буквы слова получают самые короткие свободные коды. В слове МОЛОКО буквы встречаются так: М — 1 раз, О — 3 раза, Л — 1 раз, К — 1 раз. Длина кода слова: 1·3 + 3·2 + 1·3 + 1·3 = 15. Ответ: 15.

Карточка банка «Ранга» informatics-4-8 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Пример 2

Все буквы сообщения записаны двоичным кодом, в котором ни одно кодовое слово не является началом другого (условие Фано). Сообщение состоит из 246 букв: А — 55 раз, Б — 52 раза, В — 45 раз, Г — 33 раза, Д — 31 раз, Е — 30 раз. Каков наименьший возможный размер закодированного сообщения в битах? Ответ — целое число.

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

Ответ: 631

Шаг 1. Условие Фано означает, что коды букв — это листья двоичного дерева: длина кода буквы равна числу шагов от корня до её листа. Размер сообщения — сумма произведений «сколько раз встретилась буква × длина её кода». Шаг 2. Чтобы сумма была наименьшей, частые буквы должны стоять ближе к корню, а редкие — глубже. Это делает алгоритм Хаффмана: две самые редкие буквы объединяются в одну «слитую» и опускаются на шаг ниже, и так пока не останется одна. Шаг 3. Ход слияний по частотам: 30 + 31 = 61; 33 + 45 = 78; 52 + 55 = 107; 61 + 78 = 139; 107 + 139 = 246. Каждое слияние удлиняет коды всех букв, попавших в него, ровно на один бит. Шаг 4. Получившиеся длины кодов: А — 2 бита, Б — 2 бита, В — 3 бита, Г — 3 бита, Д — 3 бита, Е — 3 бита. Размер сообщения равен 55·2 + 52·2 + 45·3 + 33·3 + 31·3 + 30·3 = 631 бит. Равномерный код дал бы 3 бита на букву, то есть 738 бит, — неравномерный код короче. Шаг 5. Проверка тремя независимыми способами счёта (жадное слияние двух наименьших весов, перебор векторов длин кодов под равенством Крафта, полный перебор форм дерева разбиением букв на две части): все три дают 631. Ответ: 631.

Карточка банка «Ранга» informatics-4-16 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Типичные ошибки

  • Выбирают код, являющийся продолжением существующего (например, 101 при наличии 10).
  • Забывают, что сам свободный узел нельзя использовать, если его продолжение уже занято.
  • Считают сумму длин кодовых слов вместо длины сообщения (или наоборот).
  • Не учитывают частоты букв при минимизации длины сообщения.

Тренироваться: 30 заданий этого номера

Тренажёр «Ранга»: условие, проверка ответа сразу и разбор по шагам. Первое задание — без регистрации, дальше — в кабинете ученика.

Решать задание 4

Кабинет ученика · Разбор задания 4: 10 примеров

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

Сколько баллов дают за задание 4 ЕГЭ по информатике?
До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — базовый.
Сколько времени тратить на задание 4?
Примерное время выполнения по спецификации ФИПИ — 2 минуты; на весь экзамен отводится 235 минут.
Что проверяет задание 4?
Умение кодировать и декодировать информацию: двоичные коды переменной длины, однозначное декодирование, условие Фано.
Где потренироваться на задании 4?
В тренажёре «Ранга» по этому номеру сейчас 30 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Источник: ФИПИ — демоверсии, спецификации, кодификаторы ЕГЭ, архив материалов 2027 года (проект спецификации и демоверсии КИМ ЕГЭ-2027 ФИПИ по информатике (опубликован как проект; 27 заданий, 29 первичных баллов, экзамен на компьютере)).

Тексты теории — авторские материалы «Ранга». Примеры — авторские тренировочные задания в формате ЕГЭ, не официальные задания ФИПИ. Мы не обещаем конкретных баллов: результат зависит от твоей работы.