Четвёртое задание из ЕГЭпо информатике ориентировано на кодирование и декодирование информации. Основной упор тут делается на условие Фано, которое гласит, что ни одно кодовое слово не может являться началом другого кодового слова. Говоря проще, если А кодируется как 011, то не будет никаких букв, у которых код начинается с 011. Зная, как правильно следовать условию Фано, на данное задание будет уходить всего 2-4 минуты. Нужно только быть внимательными.
Пример задания
По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: A — 1, B — 010, C — 000.
Укажите кратчайшее кодовое слово для буквы E, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Анализ
Всего будет 5 букв: A, B, С, D, E.
Код трёх букв уже известен.
Нужно найти кратчайшее кодовое слово для буквы Е, чтобы условие Фано соблюдалось. Это означает, что приоритет краткости надо будет отдавать именно этой букве.
Решение
Шаг 1 - Первичное бинарное дерево
Рисуем бинарное дерево по тем данным, что у нас есть. Бинарное дерево рисуется очень просто. Есть корень, от него вниз исходят две прямые линии. Та, что левее - это ноль, а та, что правее - это единица. Из каждого следующего узла тоже будут исходить по две линии, по такому же принципу.
Шаг 2 - Поиск лучшего кода
Известно, что нужно найти кратчайшее кодовое слово для буквы Е. По заданию, если подходящих кодовых последовательностей будет несколько, то нужно указать ту, значение которой будет меньше.
Исходя из рисунка, полученного на первом шаге, можно увидеть, что свободными остались только две последовательности: 001 и 011. От них тоже могут исходить ветви, но в данном случае это не требуется, так как нужно пристроить всего две буквы, а у нас как раз получилось два свободных узла. Если бы неизвестных букв было больше двух, то пришлось бы продлевать один из узлов.
Поскольку оба варианта нам подходят (001 или 011), то в соответствии с заданием, нужно выбрать наименьшее значение.
Ответ: 001
Дополнительный Пример №1
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Рисуем бинарное дерево по имеющейся информации:
Осталось две не пристроенные буквы, а узел только один. Значит, его нужно разветвить:
Теперь есть два свободных узла и две неизвестные буквы. Поскольку, по условию задания нам нужно найти наименьшую возможную суммарную длину всех четырёх кодовых слов, то не важно, куда поставить букву Л, а куда букву М, ведь у каждой из них будет по три символа в кодовом слове.
Итоговая суммарная длина = 1 (Н) + 2 (К) + 3 (Л) + 3 (М) = 9
Ответ: 9
Дополнительный пример №2
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Рисуем бинарное дерево по имеющейся информации:
Требуется разместить буквы Г, М, Р, Я. Все буквы обязательно должны быть размещены. При этом, нам нужно разместить буквы таким образом, чтобы слово ГРАММ состояло из наименьшего количества двоичных знаков (в соответствии с условием задания). Чтобы удовлетворить это условие, приоритет в короткости нужно отдать букве М, так как она повторяется дважды, а остальные буквы по одному разу.
Из рисунка видно, что из оставшихся вариантов можно занять либо комбинацию 00, либо 11. Оба варианта подойдут, нужно только убедиться, что для остальных букв хватит места. Допустим, получится следующая комбинация:
Тогда итоговая длина составит: 3(Г) + 4(Р) + 3(А) + 2(М) + 2(М) = 14
Можно предположить, что буква М стояла бы на позиции 00, но тогда у нас бы получился зеркальный вариант и результат бы не изменился.
Если предположить, что буква М имела бы, например, номер 110, то тогда все буквы состояли бы из 3-символьного кода и тогда, получился бы следующий результат: 3 + 3 + 3 + 3 + 3 = 15.
Поскольку в этом задании сказано указать наименьшее количество знаков, то правильный ответ 14.
Ответ: 14