Статья "Решение задания А9 ЕГЭ по информатике быстро и легко"
статья по информатике и икт (11 класс) по теме

Решение задания А9 ЕГЭ по информатике быстро и легко.

Чтобы легко решать задачи на декодирование в случае использования неравномерного кода, надо знать следующее:

Код — система условных знаков 

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

Декодирование — процесс обратного преобразования кода к форме исходной символьной системы, т.е. получение исходного сообщения. Например: перевод из двоичного кода в письменный текст на русском языке.

Кодирование может быть равномерное и неравномерное,  при равномерном кодировании все символы кодируются кодами равной длины, при неравномерном кодировании разные символы могут кодироваться кодами с разным количеством символов. Это осложняет  декодирование.

При  использовании неравномерного кода надо знать, что «сообщение допускает однозначное разбиение, если выполняется условие Фано: никакой код символа не является началом кода другого символа (в этом случае сообщение нужно раскодировать с начала) или обратное условие Фано: никакой код символа не является окончанием кода другого символа (в этом случае сообщение нужно раскодировать с конца).»

Рассмотрим   задание, аналогичное заданию А9 ЕГЭ:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать  полученную  двоичную  последовательность.  Вот  этот  код: А – 00, Б – 010, В –101, Г – 011, Д – 110. Можно ли сократить для одной из букв  длину  кодового  слова  так,  чтобы  код  по-прежнему  можно  было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.  

1)  для буквы Д – 11

 2)  это невозможно

 3)  для буквы Г –01

 4) для буквы  Б –01

Разберем, как будет работать декодирующее устройство, и представим для большей наглядности  алгоритм его работы в виде графа.

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

Первый символ  может иметь значение 0 или 1, и от каждого значения  построим ветку.

Граф нашей задачи представлен на рисунке 1

Рис.1.  

 Код буквы А – 00, код Б – 010, код Г – 011, код В -10, код  Д – 110, а код – 111 – не используется.

Учтем условие  Фано и проанализируем граф. Из графа видно, что 01 – не может  быть  кодом  каких-либо букв, так как он является началом для букв Б и Г,  а код для буквы Д можно сократить до 11.

Ответ  нашей задачи 1.