Урок посвящен тому, как решать 4 задание ЕГЭ по информатике
Содержание:
- Кодирование информации
- Кодирование и расшифровка сообщений
- Решение 4 заданий ЕГЭ
Кодирование информации
4-е задание: «Кодирование и декодирование информации»
Уровень сложности
— базовый,
Требуется использование специализированного программного обеспечения
— нет,
Максимальный балл
— 1,
Примерное время выполнения
— 2 минуты.
Проверяемые элементы содержания: Умение кодировать и декодировать информацию
До ЕГЭ 2021 года — это было задание № 5 ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:
“Из-за невнимательного чтения условия задания экзаменуемые иногда не замечают, что требуется найти кодовое слово минимальной длины с максимальным (минимальным) числовым значением.
Кроме того, если в задании указано, что несколько букв остались без кодовых слов (как, например, в задании демоварианта), то кодовое слово для указанной буквы должно быть подобрано таким образом, чтобы осталась возможность найти кодовые слова, удовлетворяющие условию Фано, и для других букв. Так, например, если мы букву А закодируем нулём, а букву Б единицей, то букву В мы уже никак не сможем закодировать с соблюдением условия Фано, поэтому длину кодового слова для А или Б следует увеличить”
ФГБНУ “Федеральный институт педагогических измерений”
- Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
- Кодирование бывает равномерным и неравномерным:
- при равномерном кодировании всем символам соответствуют коды одинаковой длины;
- при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.
Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).
Кодирование и расшифровка сообщений
Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.
Для решения задач с декодированием, необходимо знать условие Фано:
Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)
Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.
- если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:
- условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова
Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с концом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.
Однозначное декодирование обеспечивается:
Однозначное декодирование
Декодирование
Егифка ©:
Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube: 
ЕГЭ 4.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
✍ Решение:
- Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
О -> 0 -> 00 В -> 1 -> 01 Д -> 2 -> 10 П -> 3 -> 11 А -> 4 -> 100
ВОДОПАД:010010001110010
010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2
Результат: 22162
Теоретическое решение ЕГЭ данного задания по информатике, видео:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Рассмотрим еще разбор 4 задания ЕГЭ:
ЕГЭ 4.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
| a | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
Какой набор букв закодирован двоичной строкой 1100000100110?
✍ Решение:
- Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
- Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
✎ 1 вариант решения:
110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e
Результат: b a c d e.
✎ 2 вариант решения:
-
Этот вариант решения 4 задания ЕГЭ более сложен, но тоже верен.
- Сделаем дерево, согласно кодам в таблице:
- Сопоставим закодированное сообщение с кодами в дереве:
110 000 01 001 10
Результат: b a c d e.
Кроме того, вы можете посмотреть видеорешение этого задания ЕГЭ по информатике (теоретическое решение):
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Решим следующее 4 задание:
ЕГЭ 4.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).
Определите, какое число передавалось по каналу в виде 01100010100100100110.
✍ Решение:
- Рассмотрим пример из условия задачи:
Было2310 Стало00101001102
0010100110 (0010 - 2, 0011 - 3)
01100 01010 01001 00110
0110 0101 0100 0011
0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3
Ответ: 6 5 4 3
Вы можете посмотреть видеорешение этого задания ЕГЭ по информатике, теоретическое решение:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
ЕГЭ 4.4:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Подобные задания для тренировки
✍ Решение:
✎
1 вариант решения
основан на логических умозаключениях:
- Найдём самые короткие возможные кодовые слова для всех букв.
- Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
- Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
- Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
- Суммарная длина всех четырёх кодовых слов равна:
(Н)1 + (К)2 + (Л)3 + (М)3 = 9
✎ 2 вариант решения:
- Будем использовать дерево. Влево откладываем 0, вправо — 1:
- Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
(Н) -> 0 -> 1 символ (К) -> 10 -> 2 символа (Л) -> 110 -> 3 символа (М) -> 111 -> 3 символа
(Н)1 + (К)2 + (Л)3 + (М)3 = 9
Ответ: 9
4.5:
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:
А: 101010, Б: 011011, В: 01000
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Подобные задания для тренировки
✍ Решение:
- Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
- Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.
Результат: 00
4.6:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:
А - 01 Б - 00 В - 11 Г - 100
Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
- Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:
- Перепишем сверху вниз получившееся кодовое слово для Д: 101
Результат: 101
Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
4.7: Демоверсия ЕГЭ 2018 информатика (ФИПИ):
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Подобные задания для тренировки
✍ Решение:
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
- При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:
Результат: 1100
Подробное теоретическое решение данного 4 (раньше №5) задания из демоверсии ЕГЭ 2018 года смотрите на видео:
📹 Видеорешение на RuTube здесь
4.8:
По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:
А: 00011 Б: 111 В: 1010
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
- Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
- Получившееся числовое значение кодового слова для буквы Г — 01.
- Получившееся числовое значение кодового слова для буквы Г — 00.
- После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.
Дерево по условию Фано (однозначно декодируется с начала):
Дерево по обратному условию Фано (однозначно декодируется с конца):
Результат: 00
4.9:
По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:
Е – 000 Д – 10 К – 111
Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.
Подобные задания для тренировки
✍ Решение:
- С помощью дерева отобразим известные коды для букв:
- В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:
- Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
Д Е Д М А К А Р 10 000 10 001 01 111 01 110
Результат: 20
Смотрите виде решения задания:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Всем привет, я Елена 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-файла.
Если я вам нужна, пишите в личку или в комментах.
Кодирование чисел с помощью нулей и единиц впервые применил в своей (механической)
вычислительной машине немецкий мыслитель Готфрид Вильгельм Лейбниц в конце XVII века. Затем, уже в середине XX века, двоичное кодирование информации стало повсеместно
применяться для электронных компьютеров.
Чаще всего используется равномерный код, когда все символы исходного сообщения
кодируются с помощью одинакового количества двоичных знаков. Например,
используется таблица
Здесь использовано 4 символа (А…Г), поэтому понадобилось 2 бита (2 разряда в двоичном числе) для кодирования.
Если бы использовали 8 символов, то нужно было бы 3 бита.
Сколько бит понадобится для кодирования 32 символов?
Как ты думаешь, чем отличается равномерный код от неравномерного?
Например, для кодирования первых 5 букв русского алфавита используется таблица
|
А |
Б |
В |
Г |
Д |
|
000 |
10 |
01 |
110 |
001 |
Это неравномерный код, поскольку в нем есть двух‐ и трехсимвольные коды.
Как декодировать сообщение 1100000100110, зная ключ?
Рассуждаем.
Букв с кодами 1 и 11 в таблице нет, поэтому сообщение начинается с буквы Г – она имеет код 110:
Г
110 0000100110
Следующий (единственно возможный) код – 000, это буква А:
Г А
110 000 0100110
Аналогично декодируем все сообщение:
Г А В Д Б
110 000 01 001 10
В общем случае декодировать сообщение удается только перебором вариантов. Например,
декодируем сообщение 010100111101, закодированное с помощью кодовой таблицы
|
А |
Б |
В |
Г |
Д |
|
01 |
010 |
011 |
11 |
101 |
Декодировать сразу, скорее всего, не удастся. На первом месте может быть, буква А или буква Б. Сначала предположим, что это буква А:
А0100111101
Тогда второй буквой также может быть буква А:
АА00111101.
Дальше декодировать не получается, потому что в таблице нет кодов 0, 00 и 001. Поэтому
проверяем второй вариант: вторая буква – Б:
АБ0111101.
Третьей буквой может быть А:
АБА11101,
Тогда четвертая и пятая буквы определяются однозначно – это буквы Г и Д. Таким образом, один
из подходящих вариантов – АБАГД.
Попробуй расшифровать
1.Для кодирования сообщения используется таблица
|
А |
Б |
В |
Г |
Д |
|
01 |
11 |
100 |
010 |
110 |
Найдите все способы декодирования сообщения 1111001001100.
2. Для кодирования сообщения используется таблица
|
А |
Б |
В |
Г |
Д |
|
0 |
11 |
101 |
110 |
111 |
Найдите все способы декодирования сообщения 1111001010.
3.Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется
неравномерный двоичный код:
|
А |
B |
C |
D |
E |
|
000 |
11 |
01 |
001 |
10 |
Какие из этих сообщений были переданы без ошибок:
1) 110000010011110
2) 110000011011110
3) 110001001001110
4) 110000001011110
4. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили
использовать неравномерный код: A = 0, Б = 10, В = 110. Как нужно закодировать букву Г,
чтобы длина кода была минимальной и допускалось однозначное разбиение
кодированного сообщения на буквы?
В этом уроке мы поговорим о задании 4 из ЕГЭ по информатике 2022.
Задание 4 включает в себя понятие кодирование и декодирование информации.
Приступим к тренировочным заданиям из ЕГЭ по информатике 2022.
Задача (Стандартная)
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Решение:
Используем приём Дерево Фано. Расставим на этом дереве те буквы, для которых уже известны кодовые слова.
Дерево рисуется обычно сверху вниз. В начале от дерева рисуются две ветки: ветка 0 и ветка 1. От каждой ветки можно нарисовать ещё две ветки, так же 0 и 1, и т. д.
Для удобства ветки с 1 будем направлять вправо, а ветки с 0 будем направлять влево.
В конце каждой ветки можно размещать буквы, но если мы разместили букву, то эта ветка блокируется, и от этой ветки больше нельзя делать новые ответвления.
Нам осталось закодировать (расположить на дереве) две буквы: Д и Е.
Мы можем нарастить ещё две ветки от точки 1-1. Тогда получится код 111. И от точки 1-0. Тогда получится код 101.
Для буквы Д нужно выбрать код с наименьшим числовым значением. Значит, для буквы Д выбираем код 101, а для буквы Е выбираем код 111.
Ответ: 101
Закрепим приём дерево Фано на ещё одной примерной задаче из ЕГЭ по информатике 2022.
Задача(Стандартная, закрепление)
Для кодирования некоторой последовательности, состоящей из букв Н, О, П, Р, С, Т, У, Ф решили использовать неравномерный двоичный код, удовлетворяющий условию, что ни одно кодовое слово не является началом другого кодового слова. Для букв Н, О, П, Р, С, Т использовали соответственно кодовые слова 10, 110, 010, 0110, 111, 0111. Укажите кратчайшее возможное кодовое слово для буквы У, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение:
Здесь код так же должен удовлетворять Условию Фано, т.к. сказано, что ни одно кодовое слово не является началом другого кодового слова.
Значит, можем воспользоваться Деревом Фано. Расположим на Дереве Фано буквы, для которых уже известны кодовые слова.
Нам нужно закодировать ещё две буквы: У, Ф. У нас единственная возможность осталась прорастить ветку от точки 0. От этой точки проращиваем ветку 0 и от этой ветки проращиваем ещё две ветки 0 и 1.
Букву У размещаем на позиции 000, потому что для этой буквы нужно выбрать код с наименьшим числовым значением.
Ответ: 000
Ещё одна примерная задача из ЕГЭ по информатике 2022 является частым гостем в различных тренировочных вариантах.
Задача (Стандартная, закрепление)
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Д, Л, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 110, Б – 01, И – 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ДЕЛЕНИЕ?
Решение:
Расставим на дереве Фано буквы, для которых известны коды.
Нам осталось расположить 4 буквы: Д, Л, E, Н.
Буква Е встречается три раза в слове ДЕЛЕНИЕ, значит, ей нужно постараться присвоить самый короткий код. По дереву видно, что можно букве Е присвоить код 10.
Буквы Д, Л, Н встречаются в слове ДЕЛЕНИЕ 1 раз. Одну букву можно разместить на позицию 111. Так же можно продлить ветку из точки 00, а затем от позиции 001 сделать два отростка. У нас получатся ещё два свободных места: 0011 и 0010.
Можно оставшиеся буквы разместить следующим образом:
Подсчитаем какое количество двоичных знаков потребуется для кодирования слова ДЕЛЕНИЕ.
3+2+4+2+4+3+2=20
Ответ: 20
Далее решим непростую задачу из тренировочных вариантов ЕГЭ по информатике 2022. Похожая задача была в сборнике С. С. Крылова в 2021 году.
Задача (Непростая)
По каналу связи передаются сообщения, содержащие только четыре буквы: М, Н, Р, Т; для передачи используется двоичный код, допускающий однозначное декодирование.
Для букв М, Н, Р используются такие кодовые слова: М: 00011, Н: 1001, Р: 01100.
Укажите кратчайшее кодовое слово для буквы Т, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение:
Нужно, чтобы код декодировался однозначно. Чтобы код декодировался однозначно, можно использовать условие Фано. Мы видим, что в уже известных кода не нарушается условие Фано. Узнаем код для буквы Т по дереву Фано. Отметим известные буквы.
Куда разместить букву Т? Чтобы кодовое слово было кратчайшее, разместим букву Т на позицию 11.
Сложность этой задачи заключается в том, что явно не указано, что нужно использовать условие Фано. Так же однозначное декодирование будет, если используется обратное условие Фано.
Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.
Т. е. сообщения нужно такие раскодировать справа налево. Здесь про то, как будут раскодировать сообщения, ничего не сказано, поэтому мы должны проверить, какой код получится для буквы Т, если здесь используется обратное условие Фано.
Кодовое слово 0 мы использовать не можем, потому что 0 – это окончание кодового слова буквы Р. Кодовое слово 1 – это окончание кодовых слов букв М и Н. Кодовое слово 00 – это окончание кодового слова буквы Р. А вот 10 подходит для буквы Т.
Получилась следующая ситуация. Если кодовые слова будут удовлетворяют условию Фано, то для буквы Т можно написать кратчайшее кодовое слово 11 с минимальным числовым значением. Если кодовые слова будут удовлетворяют обратному условию Фано, то для буквы Т можно написать кратчайшее кодовое слово 10 с минимальным числовым значением.
И в том и в другом случае будет однозначное декодирование. Но мы выбираем тот случай, когда кодовое слово будет наименьшим числовым значением. Таким образом, в ответе напишем 10.
Ответ: 10
Разберём ещё один нюанс в подобных задах из ЕГЭ по информатике.
Задача (Ещё раз про однозначное декодирование)
По каналу связи передаются сообщения, содержащие только четыре буквы: М, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 111, О: 0, М: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение:
Здесь условие похоже на то, которое было в предыдущей задаче. Но обратное условие Фано здесь не применимо, т.к. код для буквы О является окончанием для кода буквы М.
Значит, у нас остаётся единственный инструмент, чтобы сообщения декодировались однозначно – это условие Фано. Теперь задачу решаем как обычно по дереву Фано.
Выбираем из двух вариантов: 110 и 101. Но останавливаемся на 101, т.к. это кодовое слово с наименьшим числовым значением.
Ответ: 101
Решим задачу, которая часто встречается в бумажных сборниках по подготовке к ЕГЭ по информатике.
Задача (код не удовлетворяет условию Фано)
По каналу связи передаются шифрованные сообщения, содержащие только пять латинских букв: A, B, С, D, E. Для передачи используется неравномерный двоичный код. Для некоторых букв известны кодовые слова: A: 01, B: 10, C: 11, D: 000.
Укажите самое короткое кодовое слово для буквы E, при котором код не будет удовлетворять условию Фано, при этом в записи самого этого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из используемых слов для букв с известными кодами.
Если таких слов несколько, то укажите слово с наименьшим числовым значением.
Решение:
Здесь код не должен однозначно декодироваться.
Подходит код 00, т.к. длина этого кодового слова больше чем 1 символ. Этот код не совпадает ни с одним кодом для известных букв. Этот код нарушает принцип условия Фано, видно, что он является началом кодового слова буквы D. И этот код имеет самое маленькое числовое значение.
Ответ: 00
В 4 задании из ЕГЭ по информатике 2022 не обязательно может попасться задача, связанная с условием Фано. Может просто быть задача на кодирование и декодирование информации.
Задача (Заключительная)
Для кодирования букв X, К, Л, О, Д решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ХОЛОДОК таким способом и результат запишите шестнадцатеричным кодом.
Решение:
Распишем, как кодируются все буквы в двоичной системе. Ноль и один кодируются одним разрядом, поэтому к ним слева приписывается ноль, как написано в условии.
| Буква | Десятичное Представление | Двоичное Представление |
| Х | 0 | 00 |
| К | 1 | 01 |
| Л | 2 | 10 |
| О | 3 | 11 |
| Д | 4 | 100 |
Выписываем слово ХОЛОДОК и под ним кодовые слова букв.
Чтобы перевести из двоичной системы число в шестнадцатиричную систему, мы должны двоичные цифры разбить по четвёркам, начиная с правого края. Каждая четвёрка превращается в цифру в шестандцатиричной системе. Таблицу перевода четвёрок двоичных цифр в шестнадцатиричную систему можно посмотреть в этой статье.
Т.к. ЕГЭ по информатике сдаётся в компьютерной форме, то можно воспользоваться стандартным калькулятором в режиме программист.
Ответ: 1DCD
На этом всё! Пусть Вам повезёт на ЕГЭ по информатике 2022.
В последней задаче буква К шифруется как 01, тогда почему в самом слове ХОЛОДОК она кодируется как 00?
