В двух прошлых статьях мы познакомились с физическими принципами хранения информации в компьютере, разобрались в кодировании и декодировании, изучили условие Фано и научились строить двоичные деревья для префиксных и постфиксных кодов.
В этой статье мы наконец перейдём к применению полученных теоретических знаний для решения задания 4 ЕГЭ по информатике.
Обычно в задании 4 вам даётся алфавит из нескольких букв, для большей части которых известны кодовые слова. Требуется найти кодовое слово для определённой буквы или сочетания букв, удовлетворяющее условию Фано. Зачастую дополнительным условием является минимальная длина кодового слова.
Задание 4 можно условно разделить на два типа:
Как обычно, каждому типу отведена своя статья. В этой мы разберём алгоритм решения первого типа задания 4: будем строить двоичные деревья и искать самый короткий код для заданной буквы. Во втором типе принцип тот же, но подобрать коды требуется сразу для нескольких букв.
Задание 4 обычно быстрее решать вручную. Для этого вам понадобится лист бумаги, на котором можно построить двоичное дерево.
В статье будем пользоваться уже построенными деревьями. Синим цветом отметим незанятые узлы, зелёным – узлы, в которых можно расположить буквы, а оранжевым – коды, запрещённые условием Фано.
Сразу перейдём к разбору алгоритма решения.
Начнём разбор алгоритма с такой формулировки:
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код.
Для кодирования букв используются кодовые слова: A — 00, C — 010, D — 011, E — 1011, F — 1001, S — 1100, X — 1010, Y — 1101, Z — 111
Укажите кратчайшее кодовое слово для буквы B, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Давайте проанализируем таблицу из условия. Мы видим, что больше всего кодов находится в правой части дерева, а самый нижний уровень будет четвёртым.
Построим двоичное дерево до третьего уровня слева и до четвёртого уровня справа.
Сразу на нём отметим уже занятые другими буквами коды.
Можно было бы подробно отметить все коды, недоступные из-за условия Фано. Но здесь сразу видно, что остался всего один свободный лист – с кодом «1000». На это место и поставим букву «B».
Следовательно, в ответ пишем код этой буквы: 1000.
Рассмотрим еще одну задачу с похожей формулировкой:
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код.
Для кодирования букв используются кодовые слова: Б — 0111, Е — 110, И — 111, К — 0100, Л — 0110, Р — 0011, С — 0101, Т — 0010, У — 000
Укажите кратчайшее кодовое слово для буквы А, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Проанализировав таблицу из условия, видим, что больше узлов здесь будет в левой, «нулевой», части. Построим двоичное дерево до четвёртого уровня.
Далее отмечаем все коды букв, данные в условии.
И снова видим, что остался всего один свободный лист, в который можно поместить букву «А», – лист с кодом 10.
На этом задание решено, в ответ запишем число 10.
Давайте решим что-нибудь посложнее. Теперь нас ждёт такая формулировка:
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано.
Кодовые слова для некоторых букв известны: А — 0; Б — 1100; B — 1000.
Укажите кратчайшее кодовое слово для буквы Г, при котором код допускает однозначное декодирование. Если таких слов несколько, укажите код с наибольшим числовым значением.
Итак, у нашего двоичного дерева вообще не будет никаких листьев слева, кроме 0, на котором и располагается буква А. Справа же строим симметричные ветви дерева до четвёртого уровня.
Теперь отметим узлы с кодами всех букв, представленных в условии. Также исключим их предков и потомков: размещать в них другие буквы нельзя из-за условия Фано.
У нас остались свободными только два листа: 101 и 111.
Согласно условию, из них выбираем код с наибольшим значением – 111.
Итак, мы научились решать задание 4 самого простого типа. В следующей статье перейдём к более сложным заданиям, в которых потребуется подобрать коды для нескольких букв и определить длину закодированного слова.
