Отправлено: 27.03.21 15:43. Заголовок: Задание 4 № 158

ДЗ КЕГЭ_4 № 158 (А. Куканова) Для кодирования некоторой последовательности, состоящей из букв Ф, А, К, Т, О, Р решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды для некоторых букв: А — 10, К — 11, Т — 0100, О — 01, Р — 0000. Укажите кратчайшее возможное кодовое слово для буквы Ф, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением. Примечание. Прямое условие Фано означает, что никакое кодовое слово не является началом другого кодового слова; обратное — что никакое кодовое слово не является концом другого кодового слова. Выполнения любого из них достаточно для однозначной расшифровки закодированных сообщений.
Ответ: 0011
Решение
Вариант решения 1
Строим дерево кодов
Визуально по дереву графа видно, что кратчайшее возможное кодовое слово для буквы Ф – 001, такой код единственный
Вариант решения 2
Метод перебора:
Построим возможные коды, отметим использованные и проанализируем для остальных кодов, выполняется ли прямое или обратное условие Фано:
0 не выполняется прямое и обратное условие Фано: 01 и 10
1 не выполняется прямое и обратное условие Фано: 10 и 01
00 не выполняется прямое и обратное условие Фано: 0000 и 0000
01 код буквы О
10 код буквы А
11 код буквы К
000 не выполняется прямое и обратное условие Фано: 0000 и 0000
001 выполняется прямое условие Фано, обратное условие Фано можно не проверять!
010
011
…
0000 код буквы Р
…
0100 код буквы Т
Следовательно, кратчайшее возможное кодовое слово для буквы Ф – 001.
Ответ: 001
Ответ приведенный на сайте Полякова К.Ю. для задания 4 № 158: 0011
Такой ответ может получиться, только, если в условии задачи исправить код для буквы Т - 0010!

 Отправлено: 27.03.21 16:00. Заголовок: Обратите внимание, ч..

Обратите внимание, что для исходного набора кодовых слов прямое условие Фано не выполняется. Поэтому нужно играть на обратном. Ответ верный.

 Отправлено: 28.03.21 12:13. Заголовок: Обратное условие Фан..

Обратное условие Фано при ответе 001 тоже выполняется.
Какой ответе верен: 0011 и 001?
Если правильный ответ 0011, то не понятно, как его получить?

 Отправлено: 28.03.21 12:20. Заголовок: Там ответ 1100. Для ..

Там ответ 1100. Для 001 обратное условие Фано не выполнится в паре О-Ф.

 Отправлено: 28.03.21 12:56. Заголовок: Спасибо большое! Теп..

Спасибо большое! Теперь все понятно.

 Отправлено: 28.03.21 13:20. Заголовок: И еще вопрос, если м..

И еще вопрос, если можно.Как построив дерево кодов, можно наглядно понять, какой код подходит для выполнения обратного условия Фано? Если да, то что об этом однозначно свидетельствует?
При выполнении прямого условия Фано все коды символов должны размещаться на листках дерева? А как будет при выполнении обратного условия Фано?

 Отправлено: 28.03.21 13:23. Заголовок: Inna пишет: Как пост..

Inna пишет:

цитата:

Как построив дерево кодов, можно наглядно понять, какой код подходит для выполнения обратного условия Фано?

Постройте дерево для обратных кодов.

 Отправлено: 28.03.21 14:11. Заголовок: Спасибо, теперь все ..

Спасибо, теперь все получилось:-)))