4-ое задание первой части ЕГЭ по информатике относится к одной из базовых тем предмета. По спецификации задание не требует использования специального ПО и решается за 2 минуты.
На чём построено задание
Любая информация в компьютере кодируется последовательностью единиц у нулей. Причём неважно, какого именно рода эта информация - закодировать можно что угодно, если знать правила. Также, зная правила кодирования, можно восстановить информацию из нулей и единиц в исходный вид.
Основные определения:
Код - система знаков, которыми что-то можно закодировать. Как правило, для компьютера код - это единицы и нули. Код, содержащий только единицы и нули, является двоичным.
Кодирование - это процесс перевода исходной информации в вид, соответствующий нужному коду. Например, кодирование слова "КОТ" в последовательность "01011".
Декодирование - это процесс восстановления закодированной информации в исходный вид. Причём важно, что декодирование не всегда позволяет достоверно восстановить закодированную информацию. Иногда декодировать одну и ту же последовательность единиц и нулей можно разными способами.
Кодовое слово - последовательность знаков кода, соответствующая исходному знаку. Например, мы можем договориться, что буква "К" будет кодироваться кодовым словом "01".
Разберём пример
Пусть у нас есть слово "КОТ". Предположим, что мы хотим его закодировать двоичным кодом. Мы договорились, что кодовые слова следующие:
"К" = 0
"О" = 10
"Т" = 11
Тогда "КОТ" = "01011".
Для декодирования мы будем просто читать последовательность нулей и единиц слева-направо и подбирать соответствующие буквы.
Разберём другой пример
Теперь попробуем закодировать слово "КОТ", используя другие кодовые слова. Пусть:
"К" = 0
"О" = 1
"Т" = 10
Тогда "КОТ" = "0110".
А теперь попробуйте декодировать. Наверняка вы столкнётесь с тем, что последовательность "0110" можно декодировать по-разному:
"0110" = "КОТ"
"0110" = "КООК"
Однозначное декодирование и условие Фано
Мы уже заметили, что в зависимости от подобранных кодовых слов декодирование может производиться либо одним способом, либо несколькими.
Однозначное декодирование - когда мы можем восстановить исходную информацию без проблем.
Неоднозначное декодирование - когда возникают разные результаты декодирования.
Для того, чтобы код декодировался однозначно, должно выполняться условие Фано.
Условие Фано звучит так: "Ни одно кодовое слово не должно быть началом другого".
Если мы хотим однозначно декодировать информацию, мы должны при декодирования подобрать подходящие кодовые слова.
Вернёмся к рассмотренному примеру:
"К" = 0
"О" = 1
"Т" = 10
Мы видим, что кодовое слово для буквы "О" является началом кодового слова для буквы "Т". Значит, условие Фано не выполняется и при декодировании могут возникнуть проблемы.
В то же время в нашем примере:
"К" = 0
"О" = 10
"Т" = 11
Условие Фано выполняется. Значит, исходную информацию можно будет декодировать однозначно.
Равномерный и неравномерный код
Всё просто:
Если все кодовые слова одинаковой длины, то код равномерный.
Пример: "А" = "01", "Б" = "11", "В" = "10"
Если кодовые слова разной длины, то код неравномерный.
Пример: "А" = "1", "Б" = "11", "В" = "10"
"А" кодируется одним символом, когда "Б" и "В" - двумя.
Прошу обратить внимание, что для равномерного кода условие Фано выполняется абсолютно всегда.
Наконец-то задача
Пример из демо ЕГЭ 2023:
Как мы видим, в задании теперь нам всё знакомо. Остаётся лишь решить задачу.
Для решения задачи нам нужно сделать 2 действия:
1. Подобрать кодовые слова для букв "А", "К", "Ч".
2. Посчитать, сколько единиц и нулей получится при кодировании слова "КАЗАЧКА".
Теперь внимание: по условию задачи нам нужно подобрать именно такие кодовые слова, которые соответствуют условию Фано и позволяют закодировать слово "КАЗАЧКА" минимальным количеством двоичных знаков.
Для начала запомним простое правило: чтобы закодировать информацию минимальным количеством занков, нужно стремиться для часто встречающихся букв подбирать короткие кодовые слова.
В слове "КАЗАЧКА" буква "А" встречается 3 раза. Предположим, что в первом случае мы кодируем букву "А" последовательностью "01". Тогда всего для кодирования трёх букв "А" нам понадобится 3*2=6 знаков. Если бы мы подобрали для буквы "А" кодовое слово "001", то нам бы уже понадобилось 3*3=9 знаков.
Решаем задачу с помощью бинарных деревьев
Бинарное (или по-другому двоичное) дерево - это структура данных, выглядящая следующим образом:
У любого дерева есть:
- Корень - то место, из которого дерево начинает "расти" вниз. На рисунке показан зелёным кружком.
- Листья - окончания дерева. На рисунке отмечены красными полупрозрачными кружками. Именно в листьях мы и будем располагать кодируемые знаки.
- Внутренние узлы - оранжевые кружки.
- Рёбра - линии, соединяющие все предыдущие элементы.
Договоримся, что в корне у нас ничего нет. Корень - это начало кодового слова. Если мы идём из корня по левому ребру, то получаем "0", а если идём по правому, то "1".
В итоге наша задача просто идти из корня к листу и записывать по порядку все единицы и нули, которые мы прошли. Я предлагаю для внутренних узлов просто отмечать цифры, которые добавляются в кодовое слово, а для листьев записывать всё кодовое слово целиком. Как на примере ниже:
Если логика работы с двоичными деревьями Вам понятна, то могу Вас поздравить: у Вас есть все знания для решения 4-го задания. Вам остаётся лишь грамотно разместить знаки в это дерево.
У бинарного дерева есть замечательная особенность: если мы располагаем символы только в листьях дерева, то мы можем быть уверены, что условие Фано 100% выполняется.
Возвращаемся к задаче
По условиям задачи некоторые кодовые слова нам уже известны ("Н" = "1111", "З" = "110"). Просто отмечаем их на дереве. Чтобы не рисовать кружки, вместо них в узлах просто ставлю цифры.
Часть дерева у нас уже есть. Остаётся только достроить дерево, разместив в его листья буквы "К", "А", "Ч".
Тут нужно обратить внимание, что для кодирования слова "КАЗАЧКА" нужно подобрать такие кодовые слова, чтобы закодированном виде было наименьшее количество единиц и нулей. Как уже было написано выше, для этого нужно просто размещать наиболее часто встречающиеся буквы ближе к корню.
Пробуем достроить дерево:
Теперь, зная все кодовые слова, считаем количество нулей и единиц в закодированном слове "КАЗАЧКА". Для этого нам даже необязательно кодировать это слово: достаточно просто для каждой используемой буквы перемножить её длину на количество её использований. Так:
"А" = 3 * 1 = 3
"К" = 2 * 2 = 4
"З" = 1 * 4 = 4
"Ч" = 4 * 1 = 4
В итоге после количества всех знаков получится ответ 15.
Однако дерево можно было построить иным способом. Проверим его:
Считаем количество знаком в закодированном слове:
"А" = 3 * 2 = 6
"К" = 2 * 2 = 4
"З" = 1 * 4 = 4
"Ч" = 2 * 1 = 2
В итоге получится ответ: 6 + 4 + 4 + 2 = 16.
Как мы видим, первый вариант (15) меньше, чем второй (16). По условию задания нам требуется добиться наименьшего количества знаков, значит, в ответе будет 15.
Ловушка
Задания могут формулироваться по-разному, но принцип везде одинаков: с помощью бинарного дерева можно подобрать требуемые кодовые слова. Однако если в задании упомянут символ, который не используется в кодируемом слове, его всё равно нужно располагать в каком-нибудь листе дерева.