Выступление на городском МО учителей информатики

«Подходы к изучению темы «Кодирование информации: префиксные коды» в профильном курсе информатики и ИКТ»

На основе анализа типичных затруднений выпускников при выполнении заданий ЕГЭ 2014 по исследованию Федерального института педагогических исследований задание А9, проверяющее умение кодировать информацию с использованием неравномерного кода, выполняется экзаменуемыми с результатом (59,6%), соответствующим нижней границе, установленной для заданий базового уровня. Содержание этого задания в 2014 г. было связано с определением минимального по длине двоичного кода, обеспечивающего однозначное декодирование. Опыт нескольких лет показывает, что экзаменуемые лучше справляются с заданиями на равномерное кодирование, чем с заданиями, связанными с использованием неравномерного по длине кода. При изучении основ информатики и ИКТ следует обратить внимание на раздел, связанный с кодированием, более подробно разбирать понятие префиксного кода, сопровождая это решением задач.

Как показывает практика, эта задача вызывает серьезные трудности не только у многих учеников, но даже у учителей информатики.
Нужно сказать, что этот материал практически не рассматривается в существующих школьных учебниках информатики, поэтому все (как ученики, так и учителя) вынуждены разбираться самостоятельно. В то же время вузовские учебники, где соответствующая теория изложена строго и научно, достаточно сложны для понимания.

В этом году задача на неравномерное кодирование находится в первой части под номером 1 Демоверсии.

Существует множество способов классификации способов кодирования.

• Критерий классификации: условие построения кодовых комбинаций

• Код фиксированной длины (англ. fixed-length code) — кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется равномерным или блоковым кодом. Примером такого кода может служить телеграфный код Бодо, который является равномерным пятибитным кодом (n=5).
• Код переменной длины (англ. variable-length code) — кодирование производится с помощью строк переменной длины. Также называется неравномерным кодом. Типичным представителем неравномерного кода является код Морзе, созданный в 1838 году Самюэлем Морзе.

Префиксный код — код, в котором, никакое кодовое слово не является началом другого. (В языковедении термин «префикс» означает «приставка»)

§   Аналогично, можно определить постфиксный код — это код, в котором никакое кодовое слово не является концом другого.

Все вышеперечисленные коды являются однозначно декодируемыми — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.

Преимущества префиксных кодов

§  Однозначно декодируемый и разделимый

§  Удается получить более короткие коды, чем с помощью кода фиксированной длины.

§  Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.

Недостатки префиксных кодов

§  При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.

Закодированное сообщение можно однозначно декодировать с начала, если выполняется  прямое условие Фано: никакое кодовое слово не является началом другого кодового слова;

Закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;

Условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

    Принцип решения задач на префиксное кодирование: сначала проверяем для всех указанных в задании вариантов прямое условие Фано, если какой-то из них подошел, это и есть ответ. Если ни для какого варианта не выполняется прямое условие Фано, проверяем обратное.  Проверка условия (и прямого, и обратного) предполагает, что сопоставляется не только предложенный вариант с кодом каждой данной буквы И код каждой данной буквы с предложенным вариантом, но И коды букв между собой...

Если проверили сначала прямое условие, потом обратное, и оба не выполняются, это не  значит, что однозначный ответ "декодировать нельзя". Не обязательно. Но пока все известные задачи ЕГЭ этого типа решаются с помощью условия Фано.

                Задачи:

1. Задача из демо-варианта

            Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000,  В–001,  Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1)  00              2)  01              3)  11             4)  010

            Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого).  Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным.

1)      00 – не подходит (является началом кодового слова 000 для буквы Б);

2)      01 – не подходит (является началом кодового слова 011 для буквы Г);

3)      11– не подходит (является продолжением(!) кодового слова 1 для буквы А);

4)      010 – подходит! (не является ничьим началом и никто не является его началом).

Ответ: 4.

2. Еще одна задача (тренировочная работа сайта Статград)

            Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова:  А–111, Б–110, В–100, Г–0.

Укажите, каким из приведенных ниже кодовых слов может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 00;   2) 001; 3) 10;   4) 101

            Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого).  Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным. Однако, в отличие от задачи из демо-варианта, здесь по условию более одного варианта может приводить к тому, что получится код, допускающий однозначное декодирование. Поэтому нужно перебирать варианты от более коротких к более длинных и, если вариант не приводит к префиксному коду, убеждаться, что этот вариант действительно дает код, не допускающий однозначного декодирования.

1) Код для Д: 00 – не допускает однозначного декодирования (00 допускает две расшифровки: ГГ и Д).

2) Код для Д: 10 – не допускает однозначного декодирования (100 допускает две расшифровки: В и ДГ).

3) Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДГГ).

4) Код для Д: 101 – вместе с кодами для А, Б, В, Г образует префиксный код.

Правильный ответ: 4

3. Рассмотрим задачу А9 из демо-варианта КИМ ЕГЭ-2013. Нужно оптимизировать код

А — 00, Б — 01, В — 100, Г — 101, Д — 110

выбрав один из вариантов

1) для буквы Д — 11    2) это невозможно

3) для буквы Г — 10    4) для буквы Д — 10

Решение. Сначала давайте посмотрим на исходный код, приведённый в условии. Можно заметить, что он префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно. 

Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Теперь проверим, что получится, если сократить код буквы Д до 11 (вариант 1). Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадёт с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение.

Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым. 

Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Таким образом, вариант 4 также не соответствует условию. Поэтому правильный ответ — 1.