Теория:
Характеристика задания
1. Тип ответа: числовой.
2. Структура содержания задания: дана текстовая задача с вариантами кодов либо в задаче записано, какой алфавит нужно закодировать.
3. Уровень сложности: базовый.
4. Примерное время выполнения: \(2\) минуты.
5. Количество баллов: \(1\).
6. Требуется специальное программное обеспечение: нет.
7. Задание проверяет умение кодировать и декодировать информацию.
Пример задания
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н — \(1111\), З — \(110\). Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Для решения задания построим двоичное дерево.
Алгоритм решения
- Рассмотрим предложенное слово: если буквы повторяются, то для их кода выбирается код минимальной длины.
- Внимательно прочитаем условие задания: в предложенном задании написано: «По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч», следовательно, кроме А, З, К, Н, Ч букв в алфавите больше нет. В некоторых заданиях можно увидеть такую запись: «В сообщении могут встречаться и другие буквы, кроме тех, которые входят в передаваемое слово», следовательно, при построении дерева нужно учитывать, что букв может быть больше, и оставлять для этого хотя бы одну свободную «ветку» двоичного дерева.
- Построим двоичное дерево, соблюдая условие, что код должен быть минимальной длины.
Пример:
нужно закодировать слово КАМАРЧАГА, здесь буква А встречается \(4\) раза, поэтому при кодировании символа выберем для него наиболее короткий код.
Учитывая предложенный алгоритм, решим задание из ЕГЭ-\(2023\).
- Дано слово КАЗАЧКА, буква А встречается три раза, буква К — два раза, поэтому при кодировании букве А должен соответствовать самый минимальный код, вторым по длине будет код для буквы К.
- В задании сказано, что кроме А, З, К, Н, Ч букв в алфавите больше нет, следовательно, можно построить дерево, не оставляя свободную «ветку».
- Учитывая всё вышеизложенное, строим дерево.
Рис. \(1\). Построение двоичного дерева
Сделаем анализ двоичного дерева и увидим, что:
буква А получила код \(0\), длина кода — \(1\),
К получила код \(10\), длина кода — \(2\),
З получила код \(110\), длина кода — \(3\),
Ч получила код \(1110\), длина кода — \(4\).
Отвечаем на вопрос: «Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА?»
КАЗАЧКА \(=\) \(2+1+3+1+4+2+1=14\).
Правильный ответ: \(14\).
Рассмотрим задание демоверсии ЕГЭ-\(2022\)
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова \(00\), \(01\), \(11\). Для двух оставшихся букв П и Р кодовые слова неизвестны. Укажи кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажи код с наименьшим числовым значением.
Алгоритм решения
- Для кодирования используют ТОЛЬКО буквы Л, М, Н, П, Р. Минимальный код для буквы П (укажи кратчайшее возможное кодовое слово для буквы П) в данном случае не минимальной длины, а минимальный по коду; если сравнить код \(101\) и \(110\), то минимальным окажется \(101\).
- Слово не дано, пропускаем шаг.
- Строим двоичное дерево.
\(1\) шаг: строим дерево по известным кодам.
Рис. \(2\). Двоичное дерево для известных кодов
\(2\) шаг: составляем коды для букв П, Р.
Рис. \(3\). Кодирование остальных букв
Остаются коды \(100\) и \(101\); так как нужен минимальный код для буквы П, кодируем её кодом \(100\).
Правильный ответ: \(100\).
Источники:
Рис. 1. Построение двоичного дерева. © ЯКласс.
Рис. 2. Двоичное дерево для известных кодов. © ЯКласс.
Рис. 3. Кодирование остальных букв. © ЯКласс.