О задании
В двух прошлых статьях мы познакомились с физическими принципами хранения информации в компьютере, научились разбираться в кодировании и декодировании, использовать условие Фано для однозначного декодирования информации, узнали о существовании различных структур данных и научились строить двоичные деревья для префиксных и постфиксных кодов.
В этой статье мы, наконец, перейдём к применению полученных теоретических знаний для решения 4 заданий ЕГЭ по информатике.
Обычно, в задании 4 вам даётся алфавит из нескольких букв и для большей части из них известны кодовые слова. Требуется же найти кодовое слово для определённой буквы или для сочетания букв, удовлетворяющее условию однозначного кодирования (условию Фано). Также зачастую сопутствующим условием является минимальная длина кодового слова для этой буквы.
Можем разделить 4 задания на два типа:
- В первом типе от нас требуется кодовое слово лишь для одной буквы
- Во втором типе необходимо найти количество двоичных знаков, требуемое для кодирования слова
Как обычно, каждому типу отведена своя статья. В этой же мы разберём алгоритм решения первого типа 4 задания, в котором будем строить двоичные деревья и искать самый короткий код для заданной буквы. Откровенно говоря, таким методом решаются все 4 задания, просто во втором требуется найти коды сразу для нескольких букв.
К сожалению, 4 задание входит в число тех, решать которые кодом не представляется возможным (или целесообразным). Так что для решения вам понадобятся листы бумаги, на которых будет располагаться двоичное дерево.
В статье же будем пользоваться уже построенными деревьями, в которых будем отмечать синим цветом незанятые узлы, зелёным – те, на которых можем расположить буквы из условия, а оранжевым – те, которые не удовлетворяют условию Фано, и разместить буквы, на которых не представляется возможным.
Сразу перейдём к разбору алгоритма решения.
Алгоритм решения
Начнём разбор алгоритма с такой формулировки:
«По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы B, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением»
Давайте проанализируем таблицу из условия. Мы видим, что больше всего кодов находится на «правой» стороне дерева и самый нижний уровень у нас будет четвертый.
Построим двоичное дерево до третьего уровня слева и до четвёртого уровня справа.
Сразу на нём отметим уже занятые другими буквами коды.
Далее можно было бы начать рассуждения, какие коды нам недоступны из-за условия Фано. Но на деле тут сразу видно, что остался всего один свободный лист дерева – с кодом «1000». На это место и поставим букву «B».
Следовательно, в ответ пишем код этой буквы: 1000.
Пример 1
Рассмотрим еще одну задачу с похожей формулировкой:
«По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова, представленные в таблице.
Укажите кратчайшее кодовое слово для буквы А, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением»
Проанализировав таблицу из условия, видим, что больше узлов здесь будет на левой «нулевой» части. Построим двоичное дерево до четвёртого уровня.
Далее отмечаем все коды букв, данные в условии.
И снова видим, что остался всего один свободный лист, на который можем поместить букву «А» – лист со значением 10.
На этом задание решено, в ответ запишем число 10.
Пример 2
Давайте решим что-нибудь посложнее. Теперь нас ждёт такая формулировка:
«По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 0; Б – 1100; B – 1000.
Укажите кратчайшее кодовое слово для буквы Г, при котором код допускает однозначное декодирование. Если таких слов несколько, укажите код с наибольшим числовым значением»
Итак, у нашего двоичного дерева вообще не будет никаких листьев слева, кроме 0, на котором и располагается буква А. Справа же строим симметричные ветви дерева до четвёртого уровня.
Теперь отметим листы с кодами всех букв, представленных в условии. Также отметим соседние листы – в них нельзя будет расположить никакие другие буквы из-за невыполнения условия Фано.
У нас остались свободными только два листа: 101 и 111.
Согласно условию, из них выбираем код с наибольшим значением – 111.
Итак, мы научились решать 4 задания самого простого типа. В следующей статье посвятим себя более сложным заданиям, в которых потребуется не только подобрать коды для каждой буквы, но и определить длину слова, составленного из этих букв.
