Ручное решение

Условие Фано:

«Никакое кодовое слово не может быть началом другого кодового слова» Условие Фано позволяет декодировать сообщение единственным образом.

Алгоритм построения дерева по кодовым словам

1. Количество уровней дерева = длина максимального кодового слова. Нарисовать линии.
2. Корень дерева — над 1 уровнем.
3. Нарисовать ветки 0 и 1 для свободной вершины.
4. Если последовательность 0 и 1 от корня в ветке составляет существующее кодовое слово, то ветка обрезается крестиком.
5. Повторить шаги 3–4 до тех пор, пока не будут отмечены все существующие кодовые слова. 

Прототипы с ЕГЭ

Задача №1 Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв – П и Р – кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 100

Задача №2 Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова. Белый — 0, Зелёный — 11111, Фиолетовый — 11110, Красный — 1110, Чёрный — 10. Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код допускает однозначное декодирование.

Ответ: 110

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

Укажите кратчайшее кодовое слово для буквы Л. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Ответ: 1101

Задача №4 Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв П и Р кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 100

Задача №5 Для кодирования некоторой последовательности, состоящей из букв N, P, R, Q, X, W, Z, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв Q и R использовали кодовые слова 11 и 100 соответственно. Определите наименьшую возможную сумму длин всех семи кодовых слов, учитывая, что кодовые слова оставшихся букв имеют одинаковую длину. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ: 20

Задача №6 По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, Л, Н, О. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: О - 100, К - 111. Для трёх оставшихся букв А, Л и Н кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЛАНКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Ответ: 15

Задача №7 По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Ответ: 14

Задания уровня ЕГЭ

Задача №1 Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: И – 0001, Н – 1110, Ф – 1111, О – 1000, Р – 001, М – 110, А – 0000, Т – 101, К – 01 Укажите возможный код минимальной длины для буквы Ю. Если таких кодов несколько, укажите минимальное числовое значение.

Ответ: 10010

Задача №2 Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 00, О – 010, Д – 011, Ф – 100, А – 11. Укажите возможный код минимальной длины для буквы Н. Если таких кодов несколько, укажите тот из них, который имеет минимальное числовое значение.

Ответ: 1010

Задача №3 Известно, что слово КАШКА закодировали с помощью последовательности 1110110011101. При этом код удовлетворяет условию Фано. Найдите минимальную длину кодовой последовательности для слова ПАМПУШКА? Известно, что другие буквы в кодируемой последовательности встретиться не могут.

Ответ: 20

Задача №4 Для кодирования букв Ч, И, Т, А, Й, В, С, Ё, использован неравномерный двоичный код. Для букв А, В, И, Й, Ё, использовали кодовые слова 10, 101, 100, 111, 1101. Какова минимальная общая длина кодовых слов для букв Ч, Т, С, при которых код не будет удовлетворять условию Фано? Известно, что ни одно кодовое слово не совпадает с уже используемыми и длина любого кодового слова более одного символа. Примечание. Условие Фано означает, что соблюдается одно из двух условий. Либо никакое кодовое слово не является началом другого кодового слова, либо никакое кодовое слово не является окончанием другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ: 6

Задача №5 По каналу связи передаются сообщения, содержащие только заглавные буквы русского алфавита. Для передачи используется двоичный код, удовлетворяющий условию Фано. Укажите минимальную возможную длину закодированной последовательности АТТЕСТАТ. Примечание: условие Фано выполняется, когда либо ни одно кодовое слово не является началом другого кодового слова, либо ни одно кодовое слово не является окончанием другого кодового слова.

Ответ: 15