Рассмотрим четвёртое задание демоверсии ЕГЭ по информатике 2021 года. Задание связано с понятием условия Фано.
Условие Фано
Условие Фано гласит: ни одно кодовое слово не является началом другого кодового слова. Это обеспечивает однозначную расшифровку закодированных сообщений.
Например, буквы A, B, C кодируются как 01, 100, 101 соответственно. Если для C взять кодовое слово 0, это нарушит условие Фано, так как «0» является началом кодового слова «01» для буквы A. Аналогично, кодовое слово «10» также не подходит, так как оно является началом «100».
Для построения кодов, удовлетворяющих условию Фано, удобно использовать бинарные деревья. В узлах дерева находятся биты (0 или 1), а листья соответствуют кодовым словам.
Решение задания
Для кодирования последовательности букв L, M, N, P, R используется неравномерный двоичный код, удовлетворяющий условию Фано. Кодовые слова для L, M, N известны: 00, 01, 11 соответственно. Необходимо найти кратчайшее кодовое слово для P, при котором условие Фано выполняется. Если таких кодов несколько, выбрать код с наименьшим числовым значением.
Буквы и их известные кодовые слова:
- L: 00
- M: 01
- N: 11
Построим бинарное дерево:
- Кодовые слова L и M начинаются с 0.
- Кодовое слово N начинается с 1.
Так как L и M используют префикс «0», для P и R мы можем использовать только префикс «1». Поскольку N использует «11», для P можно использовать «100» или «101», и аналогично для R.
Для буквы P выбираем кратчайшее кодовое слово – «100». Для буквы R – «101».
Полученный код:
- L: 00
- M: 01
- N: 11
- P: 100
- R: 101
Таким образом, кратчайшее кодовое слово для буквы P, удовлетворяющее условию Фано и имеющее наименьшее числовое значение, равно 100.
Правильный ответ на задание – 100. Использование бинарных деревьев помогает эффективно находить кодовые слова, удовлетворяющие условию Фано.