Кодирование и декодирование информации в ЕГЭ
Умение выпускников кодировать и декодировать информацию проверяются в задании №5 единого государственного экзамена по информатике и ИКТ.
Задача относится к базовому уровню сложности. Для успешного ее решения выпускники должны знать и уметь:
- принципы неравномерного кодирования;
- прямое и обратное условие Фано;
- строить неравномерный код, обеспечивающий минимальную длину сообщения и однозначное декодирование.
Рассмотрим задачи, использованные в демонстрационных и досрочных вариантах КИМов ЕГЭ по информатике и ИКТ прошлых лет.
Разберем сначала задание 5 из демоверсии ЕГЭ 2016 года.
Задание №5. По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение.
Для решения задачи построим двоичное дерево возможных кодов:
По построению (рис. 1) видно, что имеется два кандидата с кодами 101 и 110. Поскольку необходимо указать код с наименьшим числовым значением, то выбираем код 101.
Ответ. 101