Рекомендую посты об образовании

пятница, 30 ноября 2012 г.

Возможность однозначного декодирования информации

Задача А9 из демо-версии ЕГЭ-2013 по информатике:
Для лицеистов 9ИМ, 10ИМ и 11ИМ классов. Остальным любителям информатики это задание разбирать не обязательно, потому, что Вам это знать не положено, однако:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:
А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.
Выберите правильный вариант ответа.
1) для буквы Д – 11
2) это невозможно
3) для буквы Г – 10
4) для буквы Д – 10 

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



Подсказки к заданию на кодирование и декодирование информации: 
Прямое условие Фано : никакой код не должен быть началом другого кода; 
Обратное условие Фано : никакой код не должен быть концом другого кода.
И вопросы:
- Понимаете ли Вы, что мы можем закодировать сообщение, даже если условие Фано не выполняется, но возможно не сможем его однозначно декодировать? Или сможем?