ЕГЭ-2015 задание 1.

Кодирование и декодирование данных

В последние годы в заданиях материалов ЕГЭ по информатике, как в демоверсиях, так и в реальных вариантах, неизменно присутствует задача на кодирование данных следующего типа [1 (2015 год), задание А9 (2014 год)]:

Задача

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

  1. для буквы Д — 11;
  2. это невозможно;
  3. для буквы Г — 10;
  4. для буквы Д — 10.

Теория

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

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

Ответ

  1. для буквы Д — 11;
Яндекс.Метрика