Информатика

(**А. Минак**) Для кодирования информационных сообщений, состоящих из букв 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. При этом код удовлетворяет условию Фано. Найдите минимальную длину кодовой последовательности для слова ПАМПУШКА? Известно, что другие буквы в кодируемой последовательности встретиться не могут.

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

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

Заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что все кодовые слова содержат не меньше двух и не больше трёх двоичных знаков, а слову МАНКА соответствует код 1010111100001. Какой код соответствует слову МАК?

(**Е. Джобс**) По каналу связи передается сообщение «ПИРАНЬЯ». Для передачи используется двоичный код, допускающий однозначное декодирование. Укажите минимально возможную длину закодированной последовательности, если известно, что в сообщении могут встречаться и другие буквы, кроме тех, которых входят в передаваемое слово.

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

(**Е. Джобс**) По каналу связи передаются сообщения, содержащие только шесть букв: О, Т, П, У, С, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Укажите минимальную возможную длину закодированной последовательности КУСОККОПУСТ, если известно, что код для С -- 01.

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

(**Е. Джобс**) По каналу связи передаются сообщения, содержащие только шесть букв: Т, Е, Н, С, И, В. Для передачи используется двоичный код, допускающий однозначное декодирование. Кодовые слова для букв известны: Т -- 010, Е -- 0100, Н -- 1100, С -- 01000, И -- 0110, В -- 1110. Как можно сократить код для буквы Н, чтобы сохранялось свойство однозначности декодирования? Если таких кодов несколько, в качестве ответа указать код наименьшей длины.

(**Е. Джобс**) По каналу связи передаются сообщения, содержащие только восемь букв: Г, Д, Е, С, О, Т, К, А; для передачи используется двоичный код, удовлетворяющий условию Фано. Буквы С, Е, К, Т, А имеют коды 111, 110, 10, 0010, 0011 соответственно. Укажите наименьшую возможную длину закодированной последовательности для слова КОКОСЕГ.