По каналу связи передаются сообщения, содержащие четыре буквы: С, Т, У, Л. Для передачи используется неравномерный двоичный код, допускающий однозначное кодирование. Для букв С, Т, У используются такие кодовые слова: С: 110, Т: 001, У: 111.
Укажите кратчайшее кодовое слово для буквы Л, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение:
Префиксный неравномерный двоичный код удовлетворяет условию Фано. Условие Фано гласит: "В неравномерном префиксном двоичном коде ни одно слово не может быть началом другого слова". Проще говоря, Если у нас код буквы С — 110, то кодом буквы Л не может быть 1, так как в этом случае код буквы Л будет началом кода буквы С.
Рассмотрим данные коды:
110 — С
001 — Т
111 — У
Кодом буквы Л не может быть 0 или 1, так как это начала данных кодов. По той же причине кодом не может быть 00 и 11.
Зато нам подходят коды 10 и 01, они не являются началом кодов букв С, Т, У. Нам нужен код с наименьшим числовым значением, это 01.
С: 110, Т: 001, У: 111, надо найти кратчайшее Л. Тут в данных уже числах соблюдается и прямое и обратное условие Фано, значит проверять числа нужно по 2 условиям, тогда по прямому условию - кратчайшее число = 01, а по обратному - 00, значит кратчайшее 00, а не 01. Если я ошибся, поправьте. Или в этих задачах стоит руководствоваться лишь прямым условием?
Тот же вопрос. Разве верным ответом не будет 000. Если нет, то почему? 000 Не является началом чего либо, ничего не является началом 000! Так в чем проблема?
Ответы на все вопросы умников: никаких обратных условий Фано в ЕГЭ не используется. 00 не подходит, т.к. является началом 001. 000 не подходит, т.к. оно длиннее 01 по кол-ву символов. Если символов одинаково - смотрим уже числовое значение.
