ЕГЭ · Информатика · задание 41 балл · ≈6 мин

Задание 4 ЕГЭ: Условие Фано: однозначное декодирование кодов

Несколько букв закодированы двоичными словами, и код должен удовлетворять условию Фано: ни одно кодовое слово не является началом (префиксом) другого — только тогда декодирование однозначно. Вопросы бывают трёх видов: найти код новой буквы наименьшей длины, декодировать готовую последовательность битов или проверить набор на нарушение условия. Типовые потери: пробуют слово, начинающееся с уже занятого кода, забывают, что короткое слово запрещено, если оно начало чужого кода, и сравнивают коды как числа, теряя ведущие нули.

Все задания Информатика

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

Кодирование и условие Фано. Это задание с коротким ответом, который проверяется автоматически. Одна арифметическая ошибка — ноль баллов, поэтому скорость и аккуратность здесь важнее гениальности.

Формулы к заданию

y = x \cdot z \Rightarrow fail

Слово y начинается со слова x — условие Фано нарушено

2^{k}

Столько существует различных двоичных слов длины k

0, 10, 110, 111

Пример префиксного кода: короткое слово не начало длинных

L = ⌈ lo g_{2} M ⌉

Длина равномерного кода для M букв — минимальная подходящая степень двойки

Разбор типовых задач

Пример 1

Для букв А, Б, В, Г используются двоичные коды: А — 00, Б — 01, В — 10, Г — 111. Код должен удовлетворять условию Фано. Какую наименьшую длину может иметь код буквы Д? Укажите такой код.

Решение по шагам

Заняты коды 00, 01, 10 и 111. Новое слово не должно совпадать с занятым, быть чужим началом и не должно иметь занятый код своим началом.
Длина 1: слово 0 — начало кодов 00 и 01, слово 1 — начало 10 и 111. Оба запрещены.
Длина 2: 00, 01 и 10 заняты, а 11 — начало кода 111. Все четыре слова длины 2 отпадают.
Длина 3: слова 000–011 начинаются с 0..., слова 100 и 101 — с кода 10, слово 111 занято. Свободно и безопасно только 110.
$110$
Проверка парой (110, 111): слова различаются в третьем бите, ни одно не начало другого. Минимальная длина — 3.
$L = 3$

Ответ: 3 (код 110)

Пример 2

По каналу связи передают сообщения только из букв А, Б, В, Г с префиксным кодом: А — 0, Б — 100, В — 101, Г — 110. Какая последовательность букв закодирована строкой 100110101?

Решение по шагам

Читаем строку слева направо и находим первое кодовое слово, с которого начинается строка: префиксность гарантирует единственность совпадения.
Режем строку на кодовые слова: 100, 110, 101.
$100110101 = 100∣110∣101$
Кода 1 и 10 нет, поэтому первое слово — ровно 100, это буква Б.
Далее 110 — буква Г, затем 101 — буква В; строка закончилась ровно на границе кодового слова.
Ответ: БГВ. Если бы в конце остался хвост, не совпадающий ни с одним кодом, запись была бы ошибочной.

Ответ: БГВ

Тренажёр задания (числа меняются)

Клавиши 1–9 выбирают вариант, Enter — «Проверить»

Буквы закодированы префиксным кодом: А — 0, Б — 10, В — 11. В сообщении 8 букв А, 6 букв Б и 2 букв В. Сколько всего бит в закодированном сообщении?

Алфавит закодирован кодовыми словами одинаковой длины 3 бит, всего 5 букв. Сколько ещё букв можно добавить кодами той же длины, не нарушая условие Фано?

Сообщение закодировано префиксным кодом А — 0, Б — 10, В — 11 и занимает 23 бит. Известно, что в сообщении 2 букв Б и 3 букв В. Сколько в нём букв А?

Равномерный код занимает 4 бит на букву, а префиксный код Фано — 3 бит на букву. Сколько бит сэкономит код Фано на сообщении из 21 букв?

Буквы закодированы префиксным кодом: А — 0, Б — 10, В — 11. В сообщении 7 букв А, 3 букв Б и 1 букв В. Сколько всего бит в закодированном сообщении?

Сообщение закодировано префиксным кодом А — 0, Б — 10, В — 11 и занимает 25 бит. Известно, что в сообщении 2 букв Б и 3 букв В. Сколько в нём букв А?

Равномерный код занимает 5 бит на букву, а префиксный код Фано — 3 бит на букву. Сколько бит сэкономит код Фано на сообщении из 25 букв?

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

Проверяют условие Фано только в одну сторону: запрещено и «короткое слово — начало длинного», и «новое слово начинается с занятого кода»; для каждой пары смотрят оба направления.
Берут свободное слово, начинающееся с занятого кода (например, 100 при занятом 10): оно запрещено, даже если само по себе нигде не встречается.
Сравнивают коды как числа и теряют ведущие нули: 0 и 00 — разные слова, при этом 0 — начало 00; сравнивай строки битов посимвольно.

Стратегия на экзамене. Нарисуй двоичное дерево от корня: занятый код закрывает свою вершину и всё поддерево под ней. Для новой буквы ищи свободный лист наименьшей глубины — это и есть минимальная длина кода. При декодировании режь строку на кодовые слова слева направо: первое совпадение обязано быть кодом, и это безопасно именно из-за префиксности. Финальный контроль — последняя часть строки должна совпасть с кодом целиком, без хвоста.

Повторить теорию по информатике

Разбор задания опирается на формулы и приёмы — если тема вспоминается с трудом, сначала пробегите уроки:

Формат задания 4 на экзамене

Балл за задание: 1. Ориентир по времени: ≈6 минут вместе с оформлением решения. Проверяемая тема: кодирование и условие фано. На тренировке лимитов нет — сначала точность, скорость придёт после 10–15 решённых задач. Планируйте экзамен так, чтобы не застревать: если решение не идёт — зафиксируйте промежуточный результат, переходите дальше и возвращайтесь в конце, потому что остальные задания дадут больше суммарных баллов.

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

Как проверить, что набор кодов удовлетворяет условию Фано?

Для каждой пары кодовых слов проверь, не совпадает ли одно с началом другого: сравни длины и первые символы. Если ни в одной паре одно слово не префикс другого, декодирование однозначно.

Как найти кодовое слово минимальной длины для новой буквы?

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

Чем условие Фано отличается от обратного условия Фано?

Прямое условие запрещает, чтобы одно слово было началом другого, а обратное — чтобы одним из концов. Оба гарантируют однозначное декодирование, но наборы кодов для них строятся по-разному.