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

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

1. Кодовые слова 000 и 001 занимают две ветви, начинающиеся с 00, а слова 10 и 11 — обе ветви, начинающиеся с 1.

2. Единственная свободная ветвь минимальной длины — 01. Однако если присвоить 01 букве Д, то любое кодовое слово для Е, начинающееся с 01, будет иметь 01 своим началом, что нарушит условие Фано.

3. Поэтому ветвь 01 нужно разделить на два кодовых слова одинаковой длины: 010 и 011. Букве Д выбирают слово с наибольшим числовым значением.
011>010