ЕГЭ-04. Кодирование и декодирование информации

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово ПРОТОН кодируется как 1100001010010111. Какой код соответствует слову ТОП?

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово КРОКЕТ кодируется как 001111000011110. Какой код соответствует слову ТОК?

(**А. Игнатюк**) Для передачи слов по каналу связи используется специальный шифр, который составляется согласно условию Фано. Известно, что используются буквы, взятые из набора К, Р, Б, А, И, П, причем кодовое слово любой гласной буквы короче, чем кодовое слово любой согласной. Буквы Р, Б, П, И имеют код 111, 110, 101 и 00 соответственно. Запишите слово, код которого имеет вид 10001101001100111101.

(**PRO100 ЕГЭ**) По каналу связи передаются сообщения, содержащие только буквы из набора: П, Р, O, С, Т, Е, Г, Э. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: П -- 1111, Р -- 110, С -- 11101, Т -- 00, Е -- 11100. Для трёх оставшихся букв О, Г и Э кодовые слова неизвестны.

Какое количество двоичных знаков потребуется для кодирования слова ПРОСТОЕГЭ, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

(**Д. Статный**) По каналу связи передаются сообщения, содержащие только буквы из набора: А, Б, В, Д, Е, М, Т, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Б -- 01, В -- 11. Для оставшихся букв А, Д, Е, М, Т, И, К кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова МАТЕМАТИКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

(**И. Женецкий**) По каналу связи передаются сообщения, содержащие только буквы из набора: А, Г, Е, Н, Т. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Г - 01, Е - 100, Т - 101. Для двух оставшихся букв А и Н кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова ТАГАНЕГ, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

(**С. Якунин**) По каналу связи передаются сообщения, содержащие следующие символы: А, В, Е, Л, И, Н, О, С, У, Ф и пробел. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

О -- 0000, У -- 10, А -- 0001, И -- 1101, В -- 0010, Н -- 11001, Е -- 0011, Ф -- 110001.

Укажите код для буквы С такой, при котором словосочетание УСЛОВИЕ ФАНО кодируется наименьшим количеством бит. Если таких кодов несколько, укажите код с наибольшим числовым значением.

(**С. Якунин**) Для кодирования некоторой последовательности, состоящей из букв А, Т, З, Н, И, Е решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А и Т использовали кодовые слова 01 и 00, соответственно. Найдите кодовое слово наибольшей длины, если известно, что слово АНТИТЕЗА закодировано, с помощью 21 бита. Если возможно несколько вариантов ответа, выберите код с наименьшим числовым значением.

(**А. Минак**) Для кодирования информационных сообщений, состоящих из букв А, Б, В, Г, Д и Е, используется неравномерный двоичный код, удовлетворяющий обратному условию Фано. Для букв А, Б и В использовали соответственно кодовые слова: 1, 110, 00. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание: Обратное условие Фано означает, что никакое кодовое слово не является концом другого кодового слова. Соблюдение этого условия достаточно для однозначного декодирования информации.

(**А. Минак**) Для кодирования информационных сообщений, состоящих из букв A, B, C, D, E и F, используется неравномерный двоичный код, удовлетворяющий обратному условию Фано. Для букв А, B и C использовали соответствующие кодовые слова: 1, 100, 010. Укажите кратчайшее кодовое слово для буквы D, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Примечание: Обратное условие Фано означает, что никакое кодовое слово не является концом другого кодового слова. Соблюдение этого условия достаточно для однозначного декодирования информации.

(**А. Минак**) Для передачи сообщений, состоящих только из букв A, B, C, D, используют неравномерный двоичный код: A --- 10, B --- 1, C --- 100. Каким должно быть кодовое слово для буквы D, чтобы длина этого кодового слова была минимальной и допускалось однозначное декодирование сообщений?

(А. Богданов) По каналу связи передаются шифрованные сообщения, содержащие только 10 букв. Для передачи используется неравномерный двоичный код. Для девяти букв слова известны:
{ 11; 0011; 101; 100; 0010; 0101; 0001; 0000; 011 }
Укажите кратчайшее кодовое слово для десятой буквы, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением.
 

(**ЕГЭ-2022**) По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Н -- 1111, З -- 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

(**ЕГЭ-2022**) По каналу связи передаются сообщения, содержащие только шесть букв: А, И, К, Л, Н, Т, для передачи используется двоичный код, удовлетворяющий условию Фано. Буквы Л и Н имеют коды 0 и 11 соответственно. Укажите наименьшую возможную длину закодированной последовательности для слова КАЛИТКА.

Для кодирования некоторой последовательности, состоящей из букв А, К, Л, О, C, Т решили использовать неравномерный двоичный код, для которого выполняется условие Фано. Для букв А и К использовали соответственно кодовые слова 10, 111. Найдите кодовую последовательность наименьшей длины для кодирования слова КОЛОКОЛ и запишите полученный результат в восьмеричном коде. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Для кодирования некоторой последовательности, состоящей из букв Е, Л, П, К, Р, C, решили использовать неравномерный двоичный код, для которого выполняется условие Фано. Для букв К и Р использовали соответственно кодовые слова 011, 11. Найдите кодовую последовательность наименьшей длины для кодирования слова ПЕРЕПЕЛ и запишите полученный результат в восьмеричном коде. Если таких кодов несколько, укажите код с наименьшим числовым значением.

(**И. Кушнир**) Для кодирования некоторой последовательности, состоящей из букв О, Н, Г, К, Р, решили использовать неравномерный двоичный код, для которого выполняется условие Фано. Для букв К и Р использовали соответственно кодовые слова 00, 011. Найдите кодовую последовательность наименьшей длины для кодирования слова КОНОГОН и запишите полученный результат в восьмеричном коде. Если таких кодов несколько, укажите код с наименьшим числовым значением.

(**А. Богданов**) По каналу связи передаются шифрованные сообщения, содержащие только 10 букв. Для передачи используется неравномерный двоичный код. Для девяти букв слова известны:

{ 11; 0110; 0101; 001; 1010; 100; 000; 1011; 0111 }

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

(**Е. Джобс**) Для кодирования некоторой последовательности, состоящей из букв П, О, Е, Х, А, Л, И, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв О, Е, А, И использовали соответственно кодовые слова 01, 110, 1010, 001. Найдите наименьшую возможную суммарную длину всех кодовых слов.

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