Отправлено: 05.01.14 17:00. Заголовок: А9 и граф Маркова

Константин Юрьевич, опрос создала нечаянно.
А вопрос по задачи из книги
Крылов, Ушаков 2013 вариант 2 А9
Нужно оптимизировать код (однозначно декодируемый)
А — 00, Б — 01, В — 100, Г — 101, Д — 110, Е — 111
выбрав один из вариантов
1) невозможно 2) Е — 11 3) В — 10 4) Г — 10

Анализ исходного кода: префиксный-прямое условие Фано выполняется; обратное условие Фано не выполняется (А-В и Б-Г).
Анализ предложенных вариантов: все варианты дают нарушение прямого условия Фано.
Т. о. проверить однозначное декодирование предложенных вариантов можно
только построением графа по Маркову для каждого варианта ответа?

 Отправлено: 05.01.14 17:46. Заголовок: Luda пишет: Т. о. пр..

Luda пишет:

цитата:

Т. о. проверить однозначное декодирование предложенных вариантов можно только построением графа по Маркову для каждого варианта ответа?

Строго говоря, да. Но есть второй вариант - найти цепочку, которая неоднозначно декодируется:
1) для варианта 2 это 110101 => ЕББ = ДГ и 110100 => ЕБА = ДВ
2) для варианта 3 это 10101 => ВГ = ГБ и 10110 => ВД = ГВ
3) для варианта 4 это 100100 => ГБА = ВВ
Поэтому правильный вариант ответа - 1, оптимизировать код предложенными вариантами не удается.

 Отправлено: 05.01.14 18:33. Заголовок: Спасибо! у меня полу..

Спасибо!
у меня получилось найти цепочку только после того, как построила граф для варианта 2