Отправлено: 20.02.22 08:51. Заголовок: задание 4

задание: (№ 1666) (А. Куканова) Для кодирования некоторой последовательности, состоящей из букв Ф, А, К, Т, О, Р решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды для некоторых букв: А — 10, К — 11, Т — 0100, О — 01, Р — 0000. Укажите кратчайшее возможное кодовое слово для буквы Ф, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Написано, что используется двоичный код, удовлетворяющий условию Фано, но буква О является началом буквы Т. Или я чего-то не понимаю, или в формулировке задания ошибка...

 Отправлено: 20.02.22 10:15. Заголовок: Спасибо, вы правы, т..

Спасибо, вы правы, тут неточность формулировки. Код удовлетворяет обратному условию Фано. Должно быть так "двоичный код, допускающий однозначное декодирование". Исправлено.

 Отправлено: 26.02.22 23:09. Заголовок: (№ 3504) (Е. Джобс) ..

(№ 3504) (Е. Джобс) По каналу связи передаются сообщения, содержащие только семь букв: О, К, Т, Я, Б, Р, Ь. Для передачи используется двоичный код, допускающий однозначное декодирование. Кодовые слова для некоторых букв известны: К – 1010, Т – 100, Б – 0101, Р – 110, Ь – 001. Укажите минимальную возможную сумму длин кодов всех букв.

Добрый вечер! Для решения строю двоичное дерево, нахожу коды известных букв. Свободными остаются ветви 000, 011 и 111. То есть для искомых букв О и Я остаются коды длиной 3. Тогда минимальная сумма длин кодов всех букв равна 3+4+3+3+4+3+3=23. Но в ответе 22.
Скажите, пожалуйста, в чем моя ошибка.

 Отправлено: 27.02.22 05:44. Заголовок: Обратное условие Фан..

Обратное условие Фано проверяли?

 Отправлено: 27.02.22 21:10. Заголовок: Нет. Не проверяла. Т..

Нет. Не проверяла. Тогда получается, что код 11 тоже подходит? так как не является окончанием ни одного другого кода.


Подскажите, пожалуйста, обратное условие всегда нужно проверять? или только при определенном условии задачи?

 Отправлено: 28.02.22 14:31. Заголовок: В задаче на экзамене..

В задаче на экзамене вообще должно быть примечание про то, что считать условием однозначного кодирования. Если же говорить про задачи на условие Фано без уточнения, то правильнее проверять всегда.