СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 5 № 11106

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А — 0; Б — 110; В — 100.

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

 

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение.

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

 

Рассмотрим варианты для буквы Г, начиная с самого короткого.

 

1) Г=1: код буквы Г является началом кода буквы Б — 110, поэтому этот вариант не подходит.

 

2) Если код Г=01, то условие Фано нарушается, поскольку тогда код буквы А является началом кода буквы Г.

 

3) Если код Г=101, то условие Фано не нарушается. Данное кодовое слово является кратчайшим для буквы Г.

 

Ответ: 101.

Источник: ЕГЭ по ин­фор­ма­ти­ке 23.03.2016. До­сроч­ная волна