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

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

1. Проверим двоичные слова длины 1. Слово 1 является началом всех заданных кодовых слов, а слово 0 можно использовать только в одном кодовом слове: после выбора 0 другие слова, начинающиеся с 0, использовать нельзя.

2. Два кодовых слова длины 2 можно выбрать как 00 и 01. Ни одно из них не является началом кодовых слов 101, 110 и 1000, и они не являются началами друг друга.
l(Г)=2,l(Д)=2

3. Минимальная сумма длин кодовых слов для букв Г и Д равна:
l(Г)+l(Д)=2+2=4