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


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

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

 

Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

 

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

2) для буквы В – 000

3) для буквы Б – 0

4) для буквы Г – 11

Решение.

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

 

Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

 

Вариант 3 не подходит, потому что 0 является началом кода 0001.

 

Вариант 4 не подходит, потому что код 1 является началом кода 111.

 

Вариант 2 подходит, так как не нарушает условия Фано.

 

Правильный ответ указан под номером 2.

Источник: Яндекс: Тренировочная работа ЕГЭ по информатике. Вариант 1.
Спрятать решение · · Видеокурс ·
Екатерина Пронина (Москва) 15.12.2014 14:51

Здравствуйте! Решая задачу по вашему принципу, я столкнулась с проблемой. Приведу пример:

А - 1; Б - 000; В - 0101; Г - 001; Д - 011.

Ответы:

А) для буквы В - 010;

Б) это невозможно;

В) для буквы В - 101;

Г) для буквы Г - 01.

 

По условию Фано подходят варианты А) и Б).

 

Но, анализируя ответ В), получаем неоднозначность раскодирования: 1011 - (АД или ВА). По вашему условие Фано является достаточным для решения подобных задач. Как быть здесь?

Сергей Никифоров

В вашем примере верный ответ — А. Если для буквы В выбрать код 101, то 1 будет являться началом кода для буквы В, нарушится условие Фано.