Задание 4

Пример 1

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Теория

Для решения подобного вида задач удобно нарисовать бинарное (двоичное) дерево. Причем, часто, в задачах говорится о прямом условие Фано (сначала), если это не оговорено, то придется проверить и обратное условие (с конца).

Кодирование может быть равномерное и неравномерное, в большинстве задач речь идет о неравномерных кодах. Если будет задача про кратчайший код для какой-либо фразы - используйте алгоритм Хаффмана - использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины

Решение

Пример 1

Строим бинарное дерево и отмечаем на конце отрезков буквы. Свободное места зеленым, значит эти коды букв Ж и З. Ищем кратчайшее! Анализируя двоичное дерево, видно, что коды для букв Ж и З могут быть только справа. Так как мы ищем наименьшее количество двоичных знаков, то это вариант 100 для одной буквы (например Ж) и 11 для другой (З). В сумме суммарная длина кодовых слов равна 5.

Ответ

5 (Время не более 2 минут)