2 Краткая информация о задании 4

Краткая информация о задании 4

Задание 4 — про кодирование букв двоичными словами. Каждой букве назначают код из нулей и единиц. Код неравномерный — это значит, что у разных букв коды могут быть разной длины (у одной буквы 0, у другой 110). Чтобы такой код можно было однозначно раскодировать, он должен удовлетворять условию Фано.

В задании дают несколько букв, для части из них коды уже известны, и просят одно из трёх: найти наименьшую суммарную длину всех кодов, подобрать код для конкретной буквы или посчитать, сколько бит уйдёт на кодирование слова. Звучит по-разному, но в основе всегда одно и то же — бинарное дерево.

Проверяемые требования

Умение кодировать и декодировать информацию, понимать условие однозначного декодирования (условие Фано).

Средний процент выполнения по РФ

Год

% по РФ

2024

86 %

2025

83 %

2026

71,5 %

Проценты — по методическим материалам ФИПИ. Задание базовое, его решают более 80 %. Балл теряют, когда забывают или неверно применяют условие Фано.

Уровень сложности: базовый.

Примерное время выполнения: 5 минут.

💡 Важный момент про способ решения

Задание 4 не про программирование — его почти всегда решают вручную. Но не в уме, а рисуя дерево кода. Дерево показывает наглядно, какие ветки уже заняты, а какие свободны, — и ответ буквально виден на картинке.

Python здесь нужен разве что для самопроверки на сложных задачах. Мы покажем и его, но главный герой этой методички — дерево.