Алгоритм решения задания 4 ЕГЭ по информатике
Навигация по странице
О задании
В задании 4 ЕГЭ по информатике проверяются базовые навыки работы с кодированием информации, а также построения и анализа двоичного дерева.
Обычно от экзаменуемых требуется найти кодовое слово для определённой буквы. При этом для предшествующих и/или последующих букв кодовые слова уже известны. Следовательно, необходимо построить двоичное дерево на основе известной информации и найти недостающее кодовое слово.
Но, прежде чем перейти к построению двоичных деревьев, давайте сначала разберемся, что такое кодирование информации и для чего оно используется в компьютерных системах.
Кодирование информации
Кодирование информации — это процесс преобразования данных из одной формы в другую с целью обеспечения их более эффективного хранения, передачи и обработки. Это основа работы всех информационных технологий, поскольку позволяет представить информацию в удобном для использования в компьютерах и других устройствах виде.
Давайте вспомним, в каком виде удобно, точнее сказать вообще возможно, хранить информацию внутри памяти компьютера.
Память компьютера, не зависимо от того, жесткий диск это или электронные микросхемы памяти на подобии SSD или оперативной памяти, может хранить в себе данные только в цифровом, двоичном, виде. То есть любая информация представляется в виде последовательностей сигналов высокого или низкого уровней.
Например, рассмотрим устройство жёсткого диска. Он состоит из нескольких основных компонентов, включая корпус, магнитные диски (пластины), головки чтения/записи и двигатель, который вращает диски.
Для нас тут интересны сами магнитные диски, ведь именно на них записаны данные. Данные хранятся на поверхности магнитных дисков в виде последовательности битов. Каждый бит представлен изменением направления намагниченности на поверхности диска.
Условно, можно это рассмотреть так:
- Вектор намагниченности направлен вверх — это высокий уровень или же логическая единица
- Вектор намагниченности направлен вниз — это низкий уровень или логический ноль.
Следовательно, иных вариантов записи, кроме нулей и единиц у нас нет.
Также и в электронных компонентах: напряжение на ячейке памяти выше порогового — это высокий уровень (логическая единица), напряжение ниже порогового — низкий уровень (логический ноль).
Поэтому для хранения, передачи или обработки внутри компьютерных систем любая информация должна быть закодирована в двоичной системе — с использованием только двух символов — нуля и единицы.
Если компьютеру удобно хранить данные в виде нулей и единиц, то как же человеку тогда понимать эту же информацию? Для этого применяется обратная операция — декодирование.
Декодирование — это процесс, обратный кодированию. Он заключается в преобразовании закодированной информации обратно в исходный вид. Декодирование позволяет получить доступ к исходным данным, которые были преобразованы в другую форму для удобства хранения, передачи или обработки.
Например, у нас есть слово «Привет». Когда мы вводим его в компьютер и хотим сохранить в памяти, оно преобразуется в набор нулей и единиц. В распространённой кодировке UTF-8 это слово будет записано так:
11010000 10011111 11010001 10000000 11010000 10111000 11010000 10110010 11010000 10110101 11010001 10000010
Когда же мы обращаемся к файлу с этим словом, то перед тем, как вывести на экран, компьютер декодирует это сообщение в понятное нам «Привет».
Но как компьютер понимает, что набору символов «11010000 10011111» соответствует именно буква «П», а не любое другое значение?
Это работает за счет того, что у нас выполняется принцип однозначного декодирования.
Однозначное декодирование — это свойство кода, которое позволяет однозначно восстановить исходные данные из закодированной последовательности. Это означает, что каждому коду соответствует только один исходный символ или сообщение.
Также, вы должны были заметить, что тут 12 групп по 8 символов нулей и единиц. Букв в слове «Привет» у нас 6. Следовательно, для каждой буквы отводится одинаковое количество битов (16 бит или 2 байта). Это означает принцип равномерного кодирования.
Равномерное кодирование — это метод представления данных, при котором все символы или сообщения кодируются с использованием одинакового количества битов. Это означает, что каждый символ или сообщение имеет фиксированную длину кода.
Преимущества равномерного кодирования:
- простота реализации;
- удобство использования;
- эффективность при передаче данных по каналам связи с фиксированной пропускной способностью.
Недостатки равномерного кодирования:
- неэффективное использование пространства для кодирования редко встречающихся символов;
- сложность адаптации к изменяющимся условиям передачи данных.
Но также может встречаться и неравномерное кодирование символов.
Неравномерное кодирование — это метод кодирования, при котором символы или сообщения могут иметь различную длину кода в зависимости от их частоты появления. Более частые символы имеют более короткие коды, а менее частые — более длинные. Это обеспечивает более эффективное использование пространства для хранения данных и возможность адаптации к изменяющимся условиям передачи данных.
Представим, что у нас есть алфавит из 4 букв: A, B, C и D. Если мы используем неравномерное кодирование, то можем присвоить каждой букве разное количество бит в зависимости от её частоты появления:
- A — 1 бит (наиболее частый символ);
- B — 2 бита;
- C — 3 бита;
- D — 4 бита (наименее частый символ).
В рассмотренном примере, слово «Привет» у нас хранится в памяти и занимает строго определённый её объём. Поэтому компьютер всегда может определить в каких двух байтах какая буква записана. Но как быть, когда данные передаются потоком и используется неравномерное кодирование?
Например, идет передача такого сообщения: «11001011». Если бы у нас в системе букве «А» соответствовал код «110», а букве «Б» — «1100», то как понять, какая именно буква указана в начале этого сообщения?
В таком случае необходимо применять принцип условия Фано.
Условие Фано — это принцип, который используется при построении кодов для представления информации. Он гласит, что никакое кодовое слово не может быть началом другого кодового слова.
Это означает, что если мы имеем два кодовых слова «A» и «Б», то ни одно из них не должно начинаться с другого.
Обратное условие Фано также является важным принципом в теории кодирования. Оно утверждает, что никакое кодовое слово не должно заканчиваться на другую часть кода. То есть, если у нас есть два кодовых слова, их последние символы не должны совпадать.
Эти условия помогают обеспечить однозначное декодирование сообщений, поскольку они гарантируют, что ни один символ не будет иметь более одного возможного продолжения. Это особенно важно в ситуациях, когда необходимо передавать информацию по каналам связи, где возможны ошибки.
Из условий Фано следуют еще два термина: префиксный код и постфиксный код.
Префиксный код — это тип кода, в котором ни одно кодовое слово не начинается на другой код. Постфиксный код, с другой стороны, гарантирует, что никакое кодовое слово не заканчивается на другой код.
Построение двоичного дерева
Для успешного решения задания 4 ЕГЭ по информатике нам необходимо уметь правильно строить двоичные деревья. Давайте вспомним основные термины, которыми будем пользоваться в рамках этой темы.
Деревья в программировании — это структуры данных, которые представляют собой иерархическую структуру, состоящую из узлов. Каждый узел может иметь ноль или более дочерних узлов, что позволяет создавать сложные и многоуровневые структуры.
Деревья используются для представления различных типов данных и решения задач, таких как поиск, сортировка, обработка графов и т. д. Они могут быть реализованы с использованием различных языков программирования и технологий.
Выглядят деревья следующим образом:
Основные понятия деревьев:
- Узел дерева — это основная структурная единица, представляющая собой точку соединения ветвей. Узлы могут содержать данные и ссылки на другие узлы. На изображении узлы обозначены латинскими буквами.
- Корень — А — начальный узел дерева. Это основа для построения всей структуры. Корень является родителем всех остальных узлов в дереве и не имеет предков.
- Лист — узел, который не имеет потомков. Листовые узлы представляют конечные точки или результаты обработки данных. Они являются терминальными элементами дерева. На изображении листами являются узлы E, F, G и H.
- Ветви — связи между узлами. Они представляют собой линии или стрелки, которые соединяют один узел с другим. Ветви позволяют перемещаться по дереву от одного узла к другому. На изображении ветви обозначены синим цветом.
- Уровень (глубина) узла отсчитывается от корневого узла и определяет его положение в структуре дерева. Корневой узел находится на уровне 0, его потомки — на уровне 1 и так далее. Уровень узла помогает понять его позицию в иерархии дерев. Например, у узла B уровень 1, у узла H уровень 3.
- Высота дерева — максимальное расстояние от корня до самого дальнего листа. Высота определяет высоту дерева в уровнях. Если высота дерева равна 3 (как на изображении выше), то самое дальнее расстояние от корня до листа составляет 3 уровня.
Деревья разделяются на несколько видов в зависимости от количества дочерних узлов или от их сбалансированности. Мы же будем пользоваться только двоичными деревьями, у которых каждый узел может иметь не более двух дочерних узлов.
Давайте построим двоичное дерево. Корень у нас не будет иметь значения, а будет лишь означать начало кодового слова. Далее мы строим две ветви: слева будет «нулевая» ветвь, справа — «единичная».
Далее к уже имеющимся значениям будем дописывать ноль, если узел слева и единицу, если узел справа.
То есть на втором уровне у нас сначала идет слева направо узел «00», затем «01» для нулевой ветви и узел «10» и «11» для единичной ветви. Аналогично действуем и с остальными дочерними узлами.
В итоге получаем такое дерево:
Здесь мы дописывали новые значения в конец. Такое дерево подходит для работы с префиксным кодом (условием Фано).
При решении задания 4 ЕГЭ по информатике мы же можем использовать лишь одну из рассмотренных ветвей, а зависимости от кодовых слов, которые даны нам в задании.
Теперь давайте предположим, что мы строим двоичное дерево, у которого в корне находится единица и уже использован код «110». Проверим, какие коды будут удовлетворять условию Фано.
Начнем с тех, которые нам не подходят. А это будут все коды, которые начинаются с «110», то есть потомки этого узла: «1100», «1101» и все остальные. Но нам также не подходят и узлы-предки: «11» и «1», которые тоже содержат в себе значения, на которые начинается наш код. Все неподходящие коды выделены на изображении оранжевым цветом, подходящие — зелёным.
Теперь давайте построим дерево, у которого значения нового узла будут дописываться в начало. То есть такое дерево нам подойдет для работы с постфиксными кодами (обратным условием Фано).
И таким же образом давайте найдем коды, неудовлетворяющие обратному условию Фано в случае, если использован код «010». Это будут все коды, оканчивающиеся на «010». То есть все потомки узла со значением «010» («0010» и «1010»), и также два его предка: «10» и «0».
Алгоритм решения задания 4
Обычно, в задании 4 вам даётся алфавит из нескольких букв и для большей части из них известны кодовые слова. Требуется же найти кодовое слово для определённой буквы или для сочетания букв, удовлетворяющее условию однозначного кодирования (условию Фано). Также зачастую сопутствующим условием является минимальная длина кодового слова для этой буквы.
Решаются все задания практически одинаково. Для начала мы строим двоичное дерево и отмечаем на нём уже известные коды букв.
Далее перебираем кодовые слова по возрастанию и ищем то, которое будет удовлетворять условию Фано. Таким образом находим самое короткое кодовое слово для одной буквы.
Если требуется найти кодовые слова для нескольких букв, то продолжаем поиск. Но при этом, если в условии указано, что необходимо найти наименьшее количество двоичных знаков для кодирования слова из заданных букв, то букву, которая повторяется в слова чаще всего мы кодируем наименьшим возможным кодом. То есть у такой буквы уровень узла кодового слова в двоичном дереве должен быть наименьшим.
Гораздо наглядней этот алгоритм можно будет продемонстрирован на примерах ниже.
Пример 1
Имеем следующую формулировку задания 4:
«По каналу связи передаются сообщения, содержащие только буквы: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – 1001, К – 11.
Для трёх оставшихся букв Л, Н и О кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова КОЛОКОЛ?»
Начнем с того, что определим количество разных букв в слове «колокол»:
- Букв «К» — 2 штуки
- Букв «О» — 3 штуки
- Букв «Л» — 2 штуки
Будем стараться найти для буквы «О» кодовое слово минимальной длины.
Давайте построим двоичное дерево и разместим на нём известные буквы.
Теперь отметим кодовые слова, которые не будут удовлетворять условию Фано. Это узлы с кодами «110» и «111», являющиеся потомками узла с кодом «11». И предки узлов «1001» и «11»: «100», «10», «1».
У нас на дереве остаётся только 3 узла с кодовыми словами «0», «101» и «1000», в которые мы и поместим наши буквы. С самым длинным кодовым словом «1000» будет неиспользованная в слове «колокол» буква «Н». С самым коротким «0» — самая часто встречающаяся буква «О». Букву «Л» поместим на оставшийся узел — «101».
Теперь подсчитаем, сколько двоичных знаков требуется для кодирования слова «колокол».
Для буквы «К» у нас 2 знака, для «О» — 1 знак, для «Л» — 3. Итого получаем: 2*2+1*3+2*3 = 13 двоичных символов.
Любое другое размещение кодовых слов дало бы больший результат, что противоречит условию. Следовательно ответ в этом задании — 13.
Пример 2
«По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.
| Буква | Кодовое слово | Буква | Кодовое слово |
|---|---|---|---|
| A | 00 | F | 1001 |
| B | ? | S | 1100 |
| C | 010 | X | 1010 |
| D | 011 | Y | 1101 |
| E | 1011 | Z | 111 |
Укажите кратчайшее кодовое слово для буквы B, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.»
Как обычно, строим двоичное дерево и сразу отмечаем буквы, кодовые слова которых нам известны.
На самом деле, тут даже не нужно проверять, какие коды удовлетворяют условию Фано. Сразу видно, что осталось только один свободный лист дерева — с кодом «1000». На это место и поставим букву «B».
