Системы счисления при подготовке к ЕГЭ по информатике

«обратное» условие  Фано не выполняется (код буквы Б  совпадает с окончанием кода буквы  Г); поэтому этот вариант не подходит;

4. проверяем вариант 3: А–00, Б–010, В–01, Г–101, Д–111.

«прямое» условие  Фано не выполняется (код буквы В  совпадает с началом кода буквы  Б);

«обратное» условие  Фано не выполняется (код буквы В  совпадает с окончанием кода буквы  Г); поэтому этот вариант не подходит;

5. проверяем вариант 4: А–00, Б–010, В–011, Г–01, Д–111.

«прямое» условие  Фано не выполняется (код буквы Г  совпадает с началом кодов  букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит;  

6. правильный ответ – 4.

Решение (2 способ, дерево):

1. построим двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы (красным цветом выделен код буквы В – 011):

2. здесь однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);
3. теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом
4. видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано
5. хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца):

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

6. в заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится
7. правильный ответ – 4.

6. Для кодирования  некоторой последовательности, состоящей  из букв А, Б, В, Г и Д,  решили использовать неравномерный  двоичный код, позволяющий однозначно  декодировать двоичную последовательность, появляющуюся на приёмной стороне  канала связи. Использовали код:  
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1) 00  2) 01    3)11    4) 010 

Решение:

1. заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова  
2. если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит
3. если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит
4. если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит
5. для четвертого варианта, Д = 010, условие Фано не нарушено;
6. правильный ответ – 4.

7. Для кодирования  букв А, Б, В, Г решили использовать  двухразрядные последовательные  двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать  последовательность символов БАВГ  и записать результат шестнадцатеричным кодом, то получится

1) 4B₁₆   2) 411₁₆   3)BACD₁₆   4) 1023₁₆ 

Решение:

1. из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный  
2. последовательность БАВГ кодируется так: 01 00 10 11 = 1001011
3. разобьем  такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем

1001011 = 0100  1011₂ = 4B₁₆

4. правильный ответ – 1.  

8. Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти  коды представлены в таблице:

Определить, какой  набор букв закодирован двоичной строкой 0110100011000

1) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA

 Решение  (вариант 1, декодирование с начала):

1. здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений
2. попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно   
3. пусть первая буква – E с кодом 011, тогда остается цепочка 0100011000

• для кода 0100011000 первой буквой может быть только B с кодом 01, тогда остается 00011000 ( на<span class="List_0020Paragraph__Char" style=" font-family: 'Times New Roman', 'Arial';