+Оглавление
Разбираем задачу №5 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
От нас требуется закодировать или декодировать информацию за две минуты.
В кодификаторе видим, что здесь, как и в третьем задании требуется уметь интерпретировать результаты моделирования и знать о кодировании.
Немного о кодах и шифрах
Эти слова часто путают. Кратко, разница в них такая: коды известны всем, а шифры секретны.
В наших задачах идёт речь именно о кодах и кодировании. Не вдаваясь в точное формальное определение, скажу, что код - "как заменить символы на другие". В детстве все играли в разведчиков (или ещё как), отправляя друг другу записочки "так, чтобы никто не прочитал". Кто-то заменял буквы на следующие по порядку в алфавите, кто-то просто номера по алфавиту писал. Герои рассказов о Шерлоке Холмсе использовали "пляшущих человечков". Полноценным шифрованием такой процесс трудно назвать, а вот кодированием - запросто. Запись одних символов через другие.
Важно: одна буква может кодироваться целым словом или набором цифр
Если Вашу таблицу кодов опубликовать, то трудностей ведь не будет, чтобы прочитать весь текст, не так ли?
В какой-то степени, от нас требуют того же на экзамене, но правила тут чуть менее привычные.
Нам даётся не вся таблица кодов, в которой каждой букве указан её код, а только её часть, и даётся условие, по которому её можно составлять и дальше.
Равномерный и неравномерный код
В своём примере я использовал коды отдельно для букв и писал их по клеточкам. Часто требуется использовать "сплошной" код, то есть такой, которые не надо распихивать по клеточкам, а приходится расшифровывать надо без разделителей между буквами. Вот так примерно:
Как тут определять, где закончилась одна буква, а где следующая началась? Надо знать о длине кода для каждой буквы. В моём случае - по 8 символов.
Кодовые слова:
Восстановить текст теперь может каждый желающий. Как, в прочем, и зашифровать обратно.
А есть коды, в которых одна буква кодируется двумя символами, а вторая - восемью, например, как азбука Морзе. Такие коды сложны, но нам дают довольно простой вариант с условием Фано. Оно написано в тексте задачи, но не все понимают его. Разжую:
Буква имеет такой код, что её нельзя спутать с началом другой буквы.
Закодировать таким кодом не трудно: просто заменяем букву её кодом. А декодирование идёт хитро:
- читаем текст сначала,
- как только прочитанный кусок текста совпал с каким-то кодом, заменяем его буквой и
- Продолжаем читать с того же места.
Если немного пораскинуть мозгами и головами, то условие довольно очевидным становится. В самом деле, если у нас у букв будут такие коды:
то как мы определим, началась ли уже буква "б", или всё ещё идёт буква "а", например, в таком коде: 11001110? Это может быть и (11001)(110) и (110)(01110). Букву "б" по коду можно спутать с началом кода буквы "а" Нужен "однозначный" код.
Придумывать такой код довольно просто, даже без подбора: нужно пользоваться любой модификацией алгоритма Хаффмана. Ещё раз: подбор никто не отменяет. Разберём самый простой, на мой взгляд, вариант алгоритма:
Построим граф-дерево. Как бы по-проще-то объяснить? Короче, вот такое:
Двигаясь сверху вниз мы встречаем либо развилку на две дороги (налево-направо), либо букву.
И теперь нам надо записать маршрут к каждой букве, обозначая "налево" как 1, а "направо" как 0 (или наоборот)
Путь до буквы "а" состоит из двух поворотов "налево". То есть, из двух 1. Это и будет кодом этой буквы:
Такой метод даёт 100% гарантии, что условие Фано выполняется.
Решение задачи
Построим теперь дерево для букв из задачи. Смотрите: нам уже даны "маршруты" до некоторых букв:
При аккуратном составлении мы должны будем нарисовать две "пустые" ветки (чтобы была развилка или буква). Я их серым нарисовал.
Теперь можно к вопросу задачи вернуться. Нам надо найти такой код для буквы "П", чтобы он
- был самым коротким (и наименьшим)
- не нарушал условие Фано
- чтобы можно было впихнуть ещё и букву Р, не нарушив это условие
У нас, собственно, два варианта: впихивать на уже имеющиеся ветки, и дорисовывать новые. Второе - очень трудно для ЕГЭ, поэтому явно тут первое. Тут две возможности: слева по маршруту "10" и справа по маршруту "011". Все остальные пути уже оканчиваются буквами. Ясно, который код подходит?
Если поставить букву "П" слева, то выполнятся все условия.
Ответ: 10.
Заключение
Рисунок всегда более нагляден, чем цифры. Если есть возможность решать задание с помощью графа, я рекомендовал бы именно его. Конечно, как я уже писал, тут можно было бы и подобрать. Перебирая все подряд
Правда, нам тут придётся топать и до кода "011", чтобы убедиться, что букву "Р" есть куда впихнуть.
Если бы "свободная" ветка оставалась бы только одна, то нам пришлось бы дорисовывать:
И уже потом выбирать между "101" и "100". Это как раз относится к фразе "Если таких кодов несколько, укажите код с наименьшим числовым значением"
PS
Понравился разбор - ставьте лайк, подписывайтесь на канал, нас ждут ещё остальные задачи
