Всем привет, я Елена TeachYou, репетитор по информатике. На этом канале мы разбираем задания базового и повышенного уровня из ЕГЭ. Решение всех задач этих категорий позволяет набрать 22 первичных балла, что соответствует 83 баллам (!) по шкале 2022 года.
В этой статье разберем задания 4 типа на умение кодировать и декодировать информацию. План моего рассказа следующий:
- постановка задачи. Определение кодирования и декодирования информации;
- примеры однозначного и неоднозначного декодирования из статьи К.Ю. Полякова "Еще раз про неоднозначное декодирование" (очень уж они хороши, зачем придумывать свои примеры, если можно объяснить на эталонных?);
- прямое и обратное условия Фано: формулировка, примеры;
- рисуем дерево!
- разбор парочки задач из ЕГЭ.
Постановка задачи. Определение кодирования и декодирования информации
О чем вообще речь?
Когда я училась в средних классах, мы с девочками увлекались написанием зашифрованных записок. Кругу посвященных раздавались листочки с написанным шифром, в котором буквам, цифрам и знакам препинания соответствовали некоторые значки. И на скучных уроках мы шифровали и расшифровывали послания друг к другу.
Для передачи сообщений через цифровые каналы нам тоже нужен шифр - соответствие между символами, используемыми людьми, и тем, что использует компьютер. Компьютер знает два вида "символов" ("есть сигнал" / "нет сигнала"), обычно их обозначают 0 и 1. Получается, что все символы, используемые при передаче сообщения, нужно закодировать, используя только два - 0 и 1.
Из необходимости закодировать большое количество символов, используя только два значка, возникает понятие кодового слова - цепочки символов, соответствующей букве (цифре, знаку препинания...) из сообщения. Популярный (или уже не очень?) пример кодировки символов кодовыми словами (еще говорят просто "кодами") - азбука Морзе. В ней вместо 0 и 1 используют "тире" и "точку". Длиной кодового слова называют количество символов, из которых оно состоит. Например, в азбуке Морзе длина кодового слова для буквы Г равна 3, а для буквы Ъ - 5.
Как вы уже догадались, закодировать сообщение значит поставить в соответствие каждому символу некоторый код.
Давайте попробуем это сделать.
Примечание. Далее я буду использовать примеры из статьи К.Ю. Полякова "Еще раз об однозначном декодировании". Хоть она и вышла в 2012 г, материал является актуальным и прекрасно подан, а также для особо интересующихся в статье есть способ определять, будет ли код однозначно декодируемым, если не выполняются прямое и обратное условия Фано (этот способ не нужен для сдачи ЕГЭ).
Пример с неоднозначным декодированием
Возьмем фразу "Мама мыла ламу". Для ее кодирования нам сначала нужно определить, какие символы в ней встречаются. Их шесть - М, А, Ы, Л, У и символ пробела. Будем традиционно использовать двоичные коды (состоящие из 0 и 1).
Пусть кодировка наших символов выглядит так:
Для кодировки нашего сообщения нужно записать кодовые слова в одну строку: МАМА МЫЛА ЛАМУ → 0010011100010111010010.
Представим, что это закодированное сообщение прибыло в пункт назначения, и там пытаются его прочитать - раскодировать (декодировать). Таблицу с парами "символ - кодовое слово" в пункте знают, но гарантирует ли это успех? К примеру, можно предположить, что в сообщении участвуют только два символа, А и Л, с кодовыми словами 1 и 0. Тогда сообщение после декодирования будет выглядеть так: ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ. На исходное оно совсем не похоже.
Прежде чем пойти дальше, посчитаем количество символов в закодированном сообщении (это понадобится чуть дальше). Их 22. Так как наш код двоичный, то один символ равен одному биту, а закодированное сообщение "весит" 22 бита.
Пример с однозначным декодированием
Код называется однозначно декодируемым, если любое кодовое сообщение можно расшифровать единственным образом.
Чтобы гарантированно получить однозначно декодируемый код, договоримся использовать кодовые слова одинаковой длины для всех символов. В нашем примере используется шесть символов. Вспоминаем основную формулу информатики: N=2ⁿ, где N - количество двоичных чисел, записанных в n-разрядном представлении. Получается, что для кодирования шести символов нужно использовать как минимум трехзначные кодовые слова (трехбитный код). Например, такой:
Тогда все просто!
- Кодируем: МАМА МЫЛА ЛАМУ → 000001000001101000010011001101011001000100
- Декодируем: 000001000001101000010011001101011001000100 → 000 | 001 | 000 | 001 | 101 | 000 | 010 | 011 | 001 | 101 | 011 | 001 | 000 | 100 → МАМА МЫЛА ЛАМУ.
Огонь 🔥?
Но есть проблемка: длина закодированного сообщения равна 42 битам. А это почти в два раза больше, чем в предыдущем варианте!
Получается, что мы знаем два способа закодировать маму-ламу:
- первым способом получаем короткое сообщение, которое непонятно как правильно декодировать;
- вторым получаем длинное сообщение, которое декодируется очень легко.
Где же золотая середина?
Еще один пример с однозначным декодированием. Условие Фано
Давайте попробуем такой код:
МАМА МЫЛА ЛАМУ → 0100010011011011100001110000011010. В закодированном сообщении 34 бита - неплохо!
Попробуем декодировать, разбивая на отдельные символы. В нашем коде используются двух-, трех- и четырехзначные кодовые слова. Получается, первое кодовое слово из сообщения может быть 01, 010 или 0100. Таблица кодов содержит только один из этих вариантов - 01 - букву М. Отлично, мы отделили первую букву от закодированного сообщения!
0100010011011011100001110000011010 →
01 | 00010011011011100001110000011010 →
М 00010011011011100001110000011010
Пробуем еще? Следующее кодовое слово - 00, 000 или 0001. У нас есть только одно из них, 00 - буква А.
М 00010011011011100001110000011010 →
МА 010011011011100001110000011010.
Дальше вы можете поупражняться сами и убедиться, что данное сообщение можно расшифровать однозначно, отделяя одну букву за другой. Почему так получилось?
Для кода из этого примера выполняется прямое условие Фано - никакое кодовое слово не является началом другого кодового слова. Коды, для которых выполняется условие Фано, называются префиксными, и сообщения, закодированные с их помощью, декодируются однозначно.
Примечание. Существует также обратное условие Фано: "никакое кодовое слово не является окончанием другого кодового слова". Сообщения, зашифрованные при помощи таких кодов (постфиксных), нужно расшифровывать с конца.
Как проверять условие Фано?
На мой взгляд, удобно пользоваться деревом. Что оно из себя представляет? Смотрите на картинке.
Вернемся к кодировке в предыдущем примере. Для кодирования буквы М выбрано кодовое слово 01. Если нужно, чтобы для кода выполнялось условие Фано, то мы не сможем использовать кодовые слова, начинающиеся с 01 (т.е. находящиеся ниже 01, если смотреть на дерево - картинка с этим примером находится внизу). Также не можем использовать коды, являющиеся началом кода 01 (т.е. 0, который находится выше 01). Коды, которые мы использовать не можем, отметим крестиком:
Дальше добавляем код для буквы А - 00. Тоже отмечаю то, что теперь не можем использовать:
Остается закодировать еще четыре символа. Если мы для следующей буквы выберем код 1, то не сможем использовать все кодовые слова, находящиеся ниже единицы. Тогда закодированы окажутся только три символа из шести. Поэтому выберем для Л код 100:
При таком выборе кодовых слов остаются варианты для кодирования остальных символов: Ы, У и пробела. В примере выше кодировка была следующей: Ы - 1011, У - 1010, пробел - 11. Но можно закодировать отличным от предложенного образом:
Для интереса проверим длину закодированной последовательности:
МАМА МЫЛА ЛАМУ - 0100010011101101100001111000001110 - 34 бита.
Задачи из ЕГЭ
Задача 1
Если вам пока мало что понятно, не отчаивайтесь! Сейчас разберем на конкретной егэшной задачке.
Практически всегда решение этих задач начинаем с рисования дерева. Чертим его, отмечаем известные кодовые слова:
Вычеркиваем те, которые использовать не можем, чтобы не нарушить условие Фано:
Пытаемся найти кратчайшее кодовое слово:
- кодовые слова длины 1 вычеркнуты
- кодовые слова длины 2 вычеркнуты или заняты
- коды длины 3 вычеркнуты или заняты
- кодовые слова длины 4 - свободен только код 0100, он и будет ответом.
Можно ли было подобрать какое-то другое кодовое слово, чтобы код удовлетворял условию Фано? Да. Если код 0100 свободен, то из него "растут" кодовые слова 01000 и 01001 - их и можно взять в случае необходимости.
Задача 2
Начинаем всегда с рисования дерева. Медитативное, в общем-то, занятие 🧘♀️. Чертим, отмечаем известные кодовые слова. Смотрим решение в галерее, читаем комментарии под картинками.
Домашка
Ура, мы дошли до вашей любимой части - ДЗ!)
Традиционно вешаю ссылку на сайт К.Ю. Полякова (я прям амбассадор этого бренда 😆). Решаем номера 5366, 5365, 5122, 4819, 4817, 4443, 3504, 3502.
Жду от вас комментариев - все ли задачи получаются, нужно ли что-то объяснить подробнее или прорешать что-то конкретное. Подписывайтесь на мой канал, чтобы не пропустить разборы заданий.
Напоминашка
Если у вас не получается разбирать материал самостоятельно, вы чувствуете, что нуждаетесь в помощи, и при этом на календаре не апрель, у меня для вас приятная новость: скорее всего, у меня еще есть окошки для занятий по скайпу.
При онлайн-занятии я использую графический планшет для удобства объяснения, записи с занятия высылаю в виде pdf-файла.
Если я вам нужна, пишите в личку или в комментах.