Тема: Кодирование и декодирование информации
1) (ЕГЭ-2023) По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и 3. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 000, Б – 001, В – 01, Г – 11. Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, 3.
2) (ЕГЭ-2023) По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и 3. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 000, Б – 001, В – 0101, Г – 0100, Д – 011. Какое наименьшее количество двоичных знаков потребуется для кодирования трёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Е, Ж, 3.
3) По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, О, П, Р, С, Т. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для девяти букв кодовые слова известны:
Укажите кратчайшее кодовое слово для буквы Р, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением.
4) По каналу связи передаются шифрованные сообщения, содержащие только двенадцать букв: А, В, С, Е, Н, К, М, О, Р, Т, X, Y. Для передачи используется неравномерный двоичный код. Для десяти букв кодовые слова известны:
Укажите кратчайшее кодовое слово для буквы X, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
5) В сообщении встречается 7 разных букв. При его передаче использован неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: 1, 01, 001. Коды остальных четырёх букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов?
6) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово МИЛАНА кодируется как 001101000011101. Какой код соответствует слову НИМ?
7) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово КРЕЧЕТ кодируется как 110111100110001. Какой код соответствует слову ЧЕК?
8) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово ГРАНАТ кодируется как 0101110100101100. Длина всех кодовых слов не превышает 3. Какой код соответствует слову ТРН?
9) (А. Богданов) По каналу связи передаются сообщения, содержащие только буквы Д, А, Н, О, В. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Д – 00, А – 111, Н – 100, О – 101. Найдите код минимальной длины для буквы В. Если таких кодов несколько, укажите код с максимальным числовым значением.
10) (Досрочный ЕГЭ-2023) По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 0, Б – 1111, В – 1010. Найдите код минимальной длины для буквы Г. Если таких кодов несколько, укажите код с минимальным числовым значением.
11) (Досрочный ЕГЭ-2023) По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: А – 0010, Б – 0011, В – 000, Е – 0101, Ж – 111, З – 0110, И – 101, К – 100. Найдите код минимальной длины для буквы Г. Если таких кодов несколько, укажите код с минимальным числовым значением.
12) (О. Миндзаев) По каналу связи передаются сообщения, содержащие только буквы Ф, А, С, О, Л, Ь. Для передачи используется двоичный код, удовлетворяющий обратному условию Фано (ни одно кодовое слово не совпадает с окончанием другого кодового слова). Известны коды некоторых букв: Ф – 00 , С – 10, О – 11. Найдите код минимальной длины для буквы Л. Если таких кодов несколько, укажите код с минимальным числовым значением.
13) (Ф. Лущекин) По каналу связи передаются сообщения, содержащие только шесть букв: А, В, И, К, П, Р, для передачи используется двоичный код, удовлетворяющий условию Фано. Буквы П и И имеют коды 0 и 11 соответственно. Укажите наименьшую возможную длину закодированной последовательности для слова КРАПИВКА.
14) (Ф. Лущекин) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не совпадает с началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова первых букв алфавита: А — 11, Б — 0110, В — 001. Какую наименьшую длину может иметь код слова СТРАТОСТАТ?
15) (Ф. Лущекин) Сообщения, содержат только буквы слова НУНОЯБРЬ. Для кодирования используется двоичный код, в котором никакое кодовое слово не совпадает с началом другого кодового слова. Кодовые слова для некоторых букв известны: Н – 1010, У – 100, Б – 0101, Р – 110, Ь – 001. Укажите минимальную возможную сумму длин кодов всех букв.
16) (Ф. Лущекин) Сообщения, содержат только буквы А, В, Д, Е, К, О, Т, Ь. Для кодирования используется двоичный код, в котором никакое кодовое слово не совпадает с началом другого кодового слова. Кодовые слова для некоторых букв известны: В – 1010, А – 100, Т – 0101, О – 110, Е – 001. Укажите минимальную возможную длину кода для слова ВОТВЕДЬКАК.
17) (Ф. Лущекин) Сообщения, содержат только буквы слова ТЫКВАЧОК. Для кодирования используется двоичный код, в котором никакое кодовое слово не совпадает с началом другого кодового слова. Кодовые слова для некоторых букв известны: Ч – 10, О – 011. Укажите минимальную возможную длину кода для слова КАКТАК.
18) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: А – 10, Б – 110, В – 01, Г – 001, Д – 111. Укажите возможный код минимальной длины для буквы Я. Если таких кодов несколько, укажите тот из них, который имеет минимальное числовое значение.
19) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: А – 00, Б – 01, В – 110, Г – 101, Д – 100. Укажите возможный код минимальной длины для буквы Я. Если таких кодов несколько, укажите тот из них, который имеет максимальное числовое значение.
20) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: А – 000, Б – 01, В – 100, Г – 11, Д – 001. Укажите возможный код минимальной длины для буквы Я. Если таких кодов несколько, укажите тот из них, который имеет минимальное числовое значение.
21) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: А – 11, Б – 000, В – 100, Г – 01, Д – 101. Укажите возможный код минимальной длины для буквы Я. Если таких кодов несколько, укажите тот из них, который имеет максимальное числовое значение.
22) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: А – 100, Б – 01, В – 111, Г – 00, Д – 101. Укажите возможный код минимальной длины для буквы Я. Если таких кодов несколько, укажите тот из них, который имеет минимальное числовое значение.
23) (А. Богданов) Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово ПОТОК кодируется как 10001100011. Какой код соответствует слову КОТ?
24) (А. Богданов) По каналу связи передаются сообщения, содержащие только буквы Ф, И, З, М, А, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано (ни одно кодовое слово не является началом другого кодового слова). Кодовые слова для букв известны: Ф: 11; И: 000; З: 011; М: 010; Найдите код минимальной длины для буквы Т. Если таких кодов
несколько, укажите код с максимальным числовым значением.
25) (Е. Джобс) По каналу связи передаются сообщения из букв слова ИНФАСОТКА. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для некоторых букв кодовые слова известны: И – 00, Н – 1010, Ф – 1011, А – 100. Какое количество двоичных знаков потребуется для кодирования слова АНТИКАТОНИСТ, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
26) (Е. Джобс) По каналу связи передаются сообщения из букв слова ГОРЕСТЬ. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для некоторых букв кодовые слова известны: C – 1, Е – 0110, Т – 01110, Ь – 011111, соответственно. Какое количество двоичных знаков потребуется для кодирования слова ГОРСТЬ, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
27) (Е. Джобс) По каналу связи передаются сообщения, содержащие только буквы из набора: К, А, П, И, Б, Р, Д. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для некоторых букв кодовые слова известны: Б – 00, Р – 100, К – 111. Какое количество двоичных знаков потребуется для кодирования слова КАПИБАРА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
28) (А. Рогов) По каналу связи передаются сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В и Г используются кодовые слова 001, 010, 101, 11 соответственно. Укажите кратчайшее кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование.
Если таких кодов несколько, укажите код с наибольшим числовым значением.
29) (М. Шагитов) По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для некоторых букв кодовые слова известны: В – 00, Г – 1000, Д – 111, Е – 1001, Ж – 01, 3 – 110. Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв А и Б.
Ответы
1. 16
2. 8
3. 100
4. 01
5. 26
6. 11101001
7. 0110110
8. 1001100
9. 01
10. 100
11. 110
12. 001
13. 27
14. 26
15. 23
16. 33
17. 14
18. 0000
19. 1111
20. 1010
21. 0011
22. 1100
23. 0110011
24. 10
25. 35
26. 21
27. 21
28. 100
29. 8
Источник информации: © К. Поляков http://kpolyakov.spb.ru