Задание 4 ЕГЭ по информатике · CE447D

По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 0, 11, 1000, 1011 соответственно.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при котором код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

1. Кодовое слово 0 является началом любого слова, начинающегося с 0, поэтому дополнительные кодовые слова не могут начинаться с 0.

2. В ветви 1 уже используются слова 11, 1000 и 1011. Чтобы не нарушить условие Фано, новые слова должны быть свободными листьями двоичного дерева.

3. Наименьшие свободные кодовые слова имеют длину 4: например, 1001 и 1010. Они не являются началами или окончаниями других заданных слов.

4. Сумма длин двух новых кодовых слов равна:
4+4=8