Условие.
По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, З, О, Ы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 1110, О – 01, З – 110.
Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВЫЗОВ?
Решение.
Сразу отметим, условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Нам нужно найти самые короткие представления для всех букв.
Чтобы было наглядней, построим (да просто нарисуем) граф:
Из букв А, Б, В, З, О, Ы в слове ВЫЗОВ не используются две А и Б, им (буквам А и Б) необходимо оставить возможность получения кода, но он может быть и безумно длинным, это не имеет значения. Но "А" нам дано по условию, значит надо оставить веточку для "Б".
В данной задаче нам не принципиально то, какой именно код мы подберём оставшимся буквам, значение имеет его длина (длина этого кода).
Первое, что необходимо проверить, есть ли в слове повторяющиеся буквы. У нас это буква «В», она используется в слове ВЫЗОВ 2 раза. Значит ей необходим самый короткий код. Минимальная длина кода, который мы можем дать исходя из условий (Фано), это два символа.
Пусть у В будет код 00 (длина 2), тогда для Ы можно взять код 10 (длина 2), а для буквы Б останется и код, и ветвь 1111 (длина 4), буквы Б в слове нет, и нас эта длина устраивает..
Тогда В2 Ы2 З3 О2 В2 и длина кода нашего слова получается 11.
Пишите в комментариях, какие здания ещё разобрать. #егэпоинформатике2022