2 Краткая информация о задании 4
Краткая информация о задании 4
Задание 4 — про кодирование букв двоичными словами. Каждой букве назначают код из нулей и единиц. Код неравномерный — это значит, что у разных букв коды могут быть разной длины (у одной буквы 0, у другой 110). Чтобы такой код можно было однозначно раскодировать, он должен удовлетворять условию Фано.
В задании дают несколько букв, для части из них коды уже известны, и просят одно из трёх: найти наименьшую суммарную длину всех кодов, подобрать код для конкретной буквы или посчитать, сколько бит уйдёт на кодирование слова. Звучит по-разному, но в основе всегда одно и то же — бинарное дерево.
Проверяемые требования
Умение кодировать и декодировать информацию, понимать условие однозначного декодирования (условие Фано).
Средний процент выполнения по РФ
Год | % по РФ |
|---|---|
2024 | 86 % |
2025 | 83 % |
2026 | 71,5 % |
Проценты — по методическим материалам ФИПИ. Задание базовое, его решают более 80 %. Балл теряют, когда забывают или неверно применяют условие Фано.
Уровень сложности: базовый.
Примерное время выполнения: 5 минут.
💡 Важный момент про способ решения Задание 4 не про программирование — его почти всегда решают вручную. Но не в уме, а рисуя дерево кода. Дерево показывает наглядно, какие ветки уже заняты, а какие свободны, — и ответ буквально виден на картинке. Python здесь нужен разве что для самопроверки на сложных задачах. Мы покажем и его, но главный герой этой методички — дерево. |