5 (базовый уровень, время – 2 мин)

Тема:  Кодирование и декодирование информации.

Что нужно знать:

·    кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

·    обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

·    один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)

·    кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

·    закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;

·    закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;

·    условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Ещё пример задания

Р-13. По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

   а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

   б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:0, Б:10, В:110, Г:111

2) А:0, Б:10, В:01, Г:11

3) А:1, Б:01, В:011, Г:001

4) А:00, Б:01, В:10, Г:11

Решение:

1)      сначала выберем коды, в которых ни одно кодовое слово не совпадет с началом другого (такие коды называю префиксными)

2)      для кода 2 условие «а» не выполняется, так как кодовое слово буквы В (01) начинается с кодового слова буквы А (0)

3)      для кода 3 условие «а» не выполняется, так как кодовое слово буквы В (011) начинается с кодового слова буквы Б (01)

4)      для кодов 1 и 4 условие выполняется, их рассматриваем дальше

5)      считаем общее количество битов в сообщении для кода 1:

16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битов

6)      считаем общее количество битов в сообщении для кода 4:

16∙2 + 8·2 + 4∙2 + 4∙2 = 64 бита

7)      код 1 даёт наименьшую длину сообщения, поэтому выбираем его

8)      Ответ: 1.

Ещё пример задания

Р-12. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

1) 7            2) 8         3) 9         4) 10

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

1)      условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова

2)      поскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0

3)      поскольку есть код 110, запрещены кодовые слова 1, 11; кроме того, ни одно другое кодовое слово не может начинаться с 110

4)      таким образом, нужно выбрать еще два кодовых слова, для которых выполняются эти ограничения

5)      есть одно допустимое кодовое слово из двух символов: 10

6)      если выбрать кодовое слово 10 для буквы В, то остаётся одно допустимое трёхсимвольное кодовое слово – 111, которое можно выбрать для буквы Г

7)      таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов

8)      если же не выбрать В – 10, то есть три допустимых трёхсимвольных кодовых слова: 100, 101 и 110; при выборе любых двух их них для букв В и Г получаем суммарную длину кодовых слов 10, что больше 9; поэтому выбираем вариант 3 (9 символов)

9)      Ответ: 3.

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

1)      условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;

2)      построим дерево для заданных кодовых слов А – 0 и Б – 110:

3)      штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111)

4)      таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов

5)      Ответ: 3.

Ещё пример задания

Р-11. По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:

А — 0, И — 00, К — 10, О — 110, Т — 111.

Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАА                    2) ИКОТА               3) КОТ                    4) ни одно из со­об­ще­ний не под­хо­дит

Решение:

1)      прежде всего заметим, что для заданного кода не выполняется ни прямое, ни обратное условие Фано; «виновата» в этом пара А – И: код буквы А совпадает как с началом, так и с окончанием кода буквы И; больше ни для одной пары кодовых слов прямое условие Фано не нарушено

2)      это означает, что не все сообщения могут быть декодированы однозначно

3)      теперь нужно понять, какие последовательности могут быть декодированы неоднозначно; в данном случае очевидно, что сообщения АА и И кодируются одинаково: 00, поэтому все слова, где есть АА или И, не могут быть декодированы однозначно

4)      поэтому варианты 1 (КАА) и 2 (ИКОТА) отпадают

5)      на всякий случай проверим вариант 3: КОТ = 10110111; первой буквой может быть только К (по-другому сочетание 10 получить нельзя), аналогично вторая буква – только О, а третья – только Т

6)      Ответ: 3.

Ещё пример задания

Р-10. По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.

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

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

1)      код однозначно декодируется, если выполняется условие Фано или обратное условие Фано; в данном случае «прямое» условие Фано выполняется: с кода буквы О (0) не начинается ни один из двух других кодов;

2)      новый код не может начинаться с нуля (иначе нарушится условие Фано)

3)      начнём проверку с кодов длиной 1; единственный код, не начинающийся с нуля – 1 – не подходит, потому что с 1 начинаются два других кода: Т (111) и П (100

4)      кодов длиной 2, начинающихся с 1, всего 2: 10 и 11, но их использовать нельзя, потому что с 10 начинается код буквы П, а с 11 – код буквы Т

5)      рассматриваем коды длиной 3, начинающиеся с 1; коды 100 и 111 уже заняты, а ещё два – 101 и 110 – свободны и их можно использовать, причём условие Фано выполняется в обоих случаях;

6)      поскольку нужно выбрать код с минимальным значением, выбираем 101

7)      Ответ: 101.

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

1)      условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;

2)      построим дерево для заданных кодовых слов О – 0, Т – 111 и П – 100:

3)      штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С:  101 или 110; из них минимальное значение имеет код 101

4)      таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов

5)      Ответ: 101.

Ещё пример задания

Р-09. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны.

Каким из указанных способов это можно сделать?

1) для буквы В – 101                     2) это невозможно

3) для буквы В – 010                     4) для буквы Б – 10

Решение:

1)      код однозначно декодируется, если выполняется условие Фано или обратное условие Фано; в данном случае «прямое» условие Фано выполняется: с кода буквы А (0) не начинается ни один другой код, оставшиеся короткие коды (Б, Г и Д) не совпадают с началом длинного кода буквы В; таким образом, при сокращении нужно сохранить выполнение условия Фано

2)      вариант 3 не подходит, потому что новый код буквы В начинается с 0 (кода А), поэтому условие Фано нарушено

3)      вариант 4 не подходит, потому что код буквы В начинается с 10 (нового кода б), поэтому условие Фано нарушено

4)      вариант 1 подходит, условие Фано сохраняется (все трёхбитные коды различны, ни один не начинается с 0)

5)      Ответ: 1.

Ещё пример задания

Р-08. По каналу связи передаются сообщения, содержащие только 4 буквы: А, И, С, Т.

В любом сообщении больше всего букв А, следующая по частоте буква – С, затем – И. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

1) А – 0, И – 1, С – 00, Т – 11                      2) С – 1, И – 0, А – 01, Т – 10

3) А – 1, И – 01, С – 001, Т – 000               4) С – 0, И – 11, А – 101, Т – 100

Решение:

1)      сначала выберем коды, допускающие однозначное декодирование: это коды 3 и 4 (для них выполняется условие Фано), коды 1 и 2 не подходят

2)      для того, чтобы длина сообщения была как можно короче, должно выполнять правило: «чем чаще встречается буква, тем короче её код»;

3)      к сожалению, правило, приведённое выше, не совсем «хорошо» выполняется для кодов 3 и 4: в коде 3 длина кодового слова для буквы С больше, чем длина кодового слова буквы И (а хочется наоборот); для кода 4 длина кодового слова для буквы А – не самая маленькая из всех

4)      сравним коды 3 и 4, предполагая, что в сообщении буква А встречается a раз, буква С – b раз, буква И – g раз и буква Т – d раз; причём по условию задачи a > b > g > d

5)      при кодировании кодом 3 получаем сообщение длиной

L3  = a + 3b + 2g +3 d

6)      при кодировании кодом 3 получаем сообщение длиной

L4  = 3a + b + 2g +3 d

7)      находим разность: L4 ­– L3 = (3a + b + 2g +3 d) – (a + 3b + 2g +3 d) = 2a – 2b

8)      поскольку a > b, получаем L4 ­– L3 > 0, то есть код 3 более экономичный

9)      Ответ: 3.

Ещё пример задания

Р-07. По каналу связи передаются сообщения, содержащие только 4 буквы: Е, Н, О, Т. Для кодирования букв Е, Н, О используются 5-битовые кодовые слова: Е - 00000, Н - 00111, О - 11011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Т, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 11111                  2) 11100               3) 00011               4) не подходит ни одно из указанных выше слов

Решение:

1)      код, рассмотренный в условии задачи, относится к помехоустойчивым кодам, которые позволяют обнаружить и исправить определенное количество ошибок, вызванных помехами при передаче данных;

2)      количество позиций, в которых отличаются два кодовых слова одинаковой длины, называется расстоянием Хэмминга

3)      код, в котором расстояние Хэмминга между каждой парой кодовых слов равно d, позволяет обнаружить до d-1 ошибок; для исправления r ошибок требуется выполнение условия

d   2r + 1

поэтому код с d = 3 позволяет обнаружить одну или две ошибки, и исправить одну ошибку.

4)      легко проверить, что для заданного кода (Е - 00000, Н - 00111, О - 11011) расстояние Хэмминга равно 3; в таблице выделены отличающиеся биты, их по три в парах Е-Н и Н-О и четыре в паре Е-О:

Е – 00000          Е00000       Н – 00111

Н – 00111          О11011       О – 11011

5)      теперь проверяем расстояние между известными кодами и вариантами ответа; для первого ответа 11111 получаем минимальное расстояние 1 (в паре О-Т), этот вариант не подходит:

Е – 00000          Н – 00111       О – 11011

Т - 11111          Т - 11111      Т - 11111

6)      для второго ответа 11100  получаем минимальное расстояние 3 (в парах Е-Т и О-Т):

Е – 00000          Н – 00111       О – 11011

Т - 11100          Т - 11100      Т - 11100

7)      для третьего ответа 00011 получаем минимальное расстояние 1 (в паре Н-Т) , этот вариант не подходит:

Е – 00000          Н – 00111       О11011

Т - 00011          Т - 00011      Т - 00011

8)      таким образом, расстояние Хэмминга, равное 3, сохраняется только для ответа 2

9)      Ответ: 2.

Ещё пример задания:

Р-06. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Б – 01                                    2) это невозможно

3) для буквы В – 01                                    4) для буквы Г – 01

Решение (1 способ, проверка условий Фано):

1)      для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;

2)      проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);

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

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

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

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.

Ещё пример задания:

Р-05. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–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.

 

Возможные ловушки:

·    условие Фано – это достаточное, но не необходимое условие однозначного декодирования, поэтому для уверенности полезно найти для всех «неправильных» вариантов контрпримеры: цепочки,  для которых однозначное декодирование невозможно

Еще пример задания:

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

1) 4B16                  2) 41116                3)BACD16             4) 102316  

Решение:

1)      из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный

2)      последовательность БАВГ кодируется так: 01 00 10 11 = 1001011

3)      разобьем  такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем

1001011 = 0100  10112 = 4B16

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

 

Возможные ловушки:

·    расчет на то, что при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие числа (10–15) на буквы (10112 = 11, получаем неверный ответ 41116)

·    может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, B416

·    в ответах дана последовательность, напоминающая исходную (неверный ответ BACD16), чтобы сбить случайное угадывание

Еще пример задания:

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

A

B

C

D

E

000

01

100

10

011

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

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

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

1)      здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений

2)      попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно

3)      пусть первая буква – E с кодом 011, тогда остается цепочка 0100011000

·    для кода 0100011000 первой буквой может быть только B с кодом 01, тогда остается 00011000 ( начало исходной цепочки – EB?)

·    для кода 00011000 первой буквой может быть только A с кодом 000, тогда остается 11000, а эта цепочка не может быть разложена на заданные коды букв

·    поэтому наше предположение о том, что первая буква – E, неверно

4)      пусть первая буква – B с кодом 01, тогда остается цепочка 10100011000

·    для кода 10100011000 первой буквой может быть только D с кодом 10, тогда остается 100011000  (можно полагать, что начало исходной цепочки – BD?)

·    для кода 100011000 первой буквой может быть только С с кодом 100, тогда остается 011000 (начало исходной цепочки – BDC?)

Несмотря на то, что среди ответов есть единственная цепочка, которая начинается с BDC, здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись»

·    для кода 011000 на первом месте может быть B (код 01) или E (011); в первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором – остается код 000 (буква А), поэтому исходная цепочка может быть декодирована как BDCEA

5)      правильный ответ – 3

Возможные ловушки и проблемы:

·    при декодировании неравномерных кодов может быть очень много вариантов, их нужно рассмотреть все; это требует серьезных усилий и можно легко запутаться

·    нельзя останавливаться, не закончив декодирование до конца и не убедившись, что все «сходится», на это обычно и рассчитаны неверные ответы

Решение (вариант 2, декодирование с конца):

1)      для кода 0110100011000 последней буквой может быть только А (код 000),  тогда остается цепочка 0110100011

2)      для 0110100011 последней может быть только буква E (011),  тогда остается цепочка 0110100

3)      для 0110100 последней может быть только буква C (100),  тогда остается цепочка 0110

4)      для 0110 последней может быть только буква D (10),  тогда остается 01 – это код буквы B

5)      таким образом, получилась цепочка BDCEA

6)      правильный ответ – 3

Возможные ловушки и проблемы:

·    при декодировании неравномерных кодов может быть очень много вариантов (здесь случайно получилась единственно возможная цепочка), их нужно рассмотреть все; это требует серьезных усилий и можно легко запутаться

·    нельзя останавливаться, не закончив декодирование до конца и не убедившись, что все «сходится», на это обычно и рассчитаны неверные ответы

Решение (вариант 3, кодирование ответов):

1)      в данном случае самое простое и надежное – просто закодировать все ответы, используя приведенную таблицу кодов, а затем сравнить результаты с заданной цепочкой

2)      получим

1) EBCEA – 01101100011000                    2) BDDEA – 011010011000

3) BDCEA – 0110100011000                      4) EBAEA – 01101000011000

3)      сравнивая эти цепочки с заданной, находим, что правильный ответ – 3.

 

Возможные проблемы:

·    сложно сравнивать длинные двоичные последовательности, поскольку они однородны, содержат много одинаковых нулей и единиц

Еще пример задания:

Р-02. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 1                        2) 1110                 3) 111                    4) 11

Решение (вариант 1, метод подбора):

1)      рассмотрим все варианты в порядке увеличения длины кода буквы Г

2)      начнем с Г=1; при этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит

3)      следующий по длине вариант – Г=11; в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит

4)      третий вариант, Г=111, дает однозначное раскодирование во всех сочетаниях букв, поэтому…

5)      … правильный ответ – 3.

 

Возможные проблемы:

·    при переборе можно ошибиться и «просмотреть» какой-нибудь вариант

 

Решение (вариант 2, «умный» метод):

1)      для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода; это условие называют условием Фано

2)      как и в первом решении, рассматриваем варианты, начиная с самого короткого кода для буквы Г; в нашем случае код Г=1 является началом кодов букв Б и В, поэтому условие Фано не выполняется, такой код не подходит

3)      код Г=11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный вариант

4)      третий вариант кода, Г=111, не является началом никакого уже известного кода; кроме того, ни один уже имеющийся код не является началом кода 111; таким образом, условие Фано выполняется

5)      поэтому правильный ответ – 3.

 

Возможные проблемы:

·    нужно знать условие Фано

Еще пример задания[1]:

Р-01. Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Для компактности результат записали в шестнадцатеричной системе счисления. Выберите правильную запись кода.

1) BD9AA5                          2) BDA9B5          3) BDA9D5          4) DB9DAB

Решение:

1)      «вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка, потом – вторая, и т.д.:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 строка

2 строка

3 строка

4 строка

2)      в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:

1

0

1

1

1

1

0

1

1

0

1

0

1

0

0

1

1

1

0

1

0

1

0

1

1 строка

2 строка

3 строка

4 строка

3)      поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в данном случае все равно, откуда начинать разбивку, поскольку в полоске целое число тетрад – 6):

1

0

1

1

1

1

0

1

1

0

1

0

1

0

0

1

1

1

0

1

0

1

0

1

4)      переводя тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5

5)      поэтому правильный ответ – 3.

 

Возможные проблемы:

·    нужно уметь быстро переводить тетрады в шестнадцатеричные цифры (в крайнем случае, это можно сделать через десятичную систему)

Еще пример задания:

Р-00. Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01010100100111100011?

1) 59143                              2) 5971                 3) 102153                            4) 10273

Решение:

1)      сначала разберемся, как закодированы числа в примере; очевидно, что используется код равномерной длины; поскольку 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит, то есть

2 → 00101 и 3 → 00110

2)      как следует из условия, четыре первых бита в каждой последовательности – это двоичный код цифры, а пятый бит (бит четности) используется для проверки и рассчитывается как «сумма по модулю два», то есть остаток от деления суммы битов на 2; тогда

2 = 00102, бит четности (0 + 0 + 1 + 0) mod 2 = 1                 

3 = 00112, бит четности (0 + 0 + 1 + 1) mod 2 = 0             

3)      но бит четности нам совсем не нужен, важно другое: пятый бит в каждой пятерке можно отбросить!

4)      разобъем заданную последовательность на группы по 5 бит в каждой:

01010, 10010, 01111, 00011.

5)      отбросим пятый (последний) бит в каждой группе:

0101, 1001, 0111, 0001.
это и есть двоичные коды передаваемых чисел:

01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1.

6)      таким образом, были переданы числа 5, 9, 7, 1 или число 5971.

7)      Ответ: 2.


Задачи для тренировки[2]:

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

1) 13216          2) D216           3) 310216            4) 2D16

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

1) 13816          2) DBCA16     3) D816            4) 312016

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

a             b             c              d             e

000         110         01           001         10

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

1) baade       2) badde       3) bacde        4) bacdb

4)      Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:

1) 175423       2) 115612      3) 62577        4) 12376

5)      Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится:

1) А5216         2) 4С816         3) 15D16         4) DE516

6)      Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится:

1) 846138          2) 1052338       3) 123458       4) 7763258

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

 

  а                       b                      с                     d                   е

100                  110                  011                  01                 10

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

1) cbade        2) acdeb        3) acbed        4) bacde

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

 А                       В                    С                        D                 Е                    F

00                    100                  10                     011               11                 101

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

1) DEFBAC        2) ABDEFC        3) DECAFB        4) EFCABD

9)      Для кодирования букв А, В, С, D используются четырехразрядные последовательные двоичные числа, начинающиеся с 1 (от 1001 до 1100 соответственно). Если таким способом закодировать последовательность символов CADB и записать результат в шестнадцатеричном коде, то получится:

1) AF5216       2) 4CB816       3) F15D16       4) В9СА16

10)   Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

 А                       Б                    В                        Г

00                    11                   010                  011

Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится:

1) CDADBC16            2) A7C416                    3) 41271016                  4) 4С7А16

11)   Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

 А                       Б                    В                        Г

00                    11                   010                  011

Если таким способом закодировать последовательность символов ГАВБВГ и записать результат в шестнадцатеричном коде, то получится:

1) 62D316                   2) 3D2616                    3) 3132616                    4) 6213316

12)   Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

 А                       Б                    В                        Г

00                    11                   010                  011

Если таким способом закодировать последовательность символов ГБВАВГ и записать результат в шестнадцатеричном коде, то получится:

1) 7101316                  2) DBCACD16             3) 31A716                      4) 7A1316

13)   Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

 А                       Б                    В                        Г

00                    11                   010                  011

Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:

1) DACBDC16            2) AD2616                    3) 62131016                  4) 62DA16

14)   Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код:

 A                       B                    C                        D                 E

000                  11                   01                     001               10

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 110000010011110

2) 110000011011110                                  

3) 110001001001110

4) 110000001011110

15)   Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.

1) AD34                      2) 43DA                      3) 101334                      4) CADBCD

 

16)   Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 0001                       2) 000                          3) 11                               4) 101

 

17)   Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

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

 

18)   Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.

1) 57414                     2) 53414                     3) 53412                        4) 53012

19)   Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное кодирование: А-0, Б-11, В-100, Г-011. Через канал связи передается сообщение: ГБАВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в восьмеричный код.

1) DBACACD             2) 75043                     3) 7A23                          4) 3304043

 

20)   Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное кодирование: А-10, Б-11, В-110, Г-0. Через канал связи передается сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный код.

1) D3A6                      2) 62032206              3) 6A3D                         4) CADBAADC

 

21)   Для кодирования сообщения, состоящего только из букв О, К, Л, М и Б, используется неравномерный по длине двоичный код:

  О                      К                    Л                       М                Б

00                    01                   11                     010               0110

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 110001001001110

2) 10000011000111010                              

3) 110001001101001

4) 1000110001100010

22)   Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ГБВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричную систему счисления. Какой вид будет иметь это сообщение?

1) 71013

2) DBCACD

3) 7A13

4) 31A7

23)   Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используются четырехразрядные последовательные двоичные числа от 1000 до 1011. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:

1) 175612                   2) 115612                    3) 62612                       4) 12612

24)   Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01100010100100100110?

1) 6543                       2) 62926                      3) 62612                       4) 3456

25)   Для кодирования букв А, Б, В, Г, Д, Е, Ж используются трех- и четырехразрядные последовательные двоичные коды от 101 до 1011. Если таким способом закодировать последовательность символов ГДЕЖЕБЕГ и записать результат в восьмеричном коде, то получится:

1) 1046535325         2) 4232565524          3) 10465353250         4) 42325655240

26)   Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Для компактности результат записали в шестнадцатеричной системе счисления. Выберите правильную запись кода.

1) BD9AA5                2) BDA9B5                 3) BDA9D5                    4) DB9DAB

27)   Для кодирования сообщения, состоящего только из букв X, W, Y и Z, используются двухразрядные последовательные двоичные числа от 00 до 11 соответственно. Если таким способом закодировать последовательность символов YXZXWX и записать результат в шестнадцатеричном коде, то получится:

1) 434                          2) 4B8                          3) 8B4                            4) 8С4

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

1) 70118         2) 210138       3) 11078              4) 2478

29)   Для кодирования букв Е, Н, Ч, Ь используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ПЕЧЕНЬЕ и записать результат в восьмеричном коде, то получится:

1) 1030240                2) 12017                      3) 2141351                   4) 23120

30)   Для кодирования букв Х, Е, Л, О, Д используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ЛЕДОХОД и записать результат в шестнадцатеричном коде, то получится:

1) 999C                       2) 3254145                 3) 123F                          4) 2143034

31)   Для кодирования букв И, Д, Т, О, Х используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ТИХОХОД и записать результат в шестнадцатеричном коде, то получится:

1) CD89                      2) 89CD                       3) 3154542                   4) 2043431

32)   Для кодирования букв О, Ч, Б, А, К используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов КАБАЧОК и записать результат в шестнадцатеричном коде, то получится:

1) 5434215                2) 9DA4                      3) ABCD                        4) 4323104

33)   Для кодирования букв Р, И, К, П, А используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ПАПРИКА и записать результат в шестнадцатеричном коде, то получится:

1) E634                       2) A1B2                      3) A45412A                 4) 3430124

34)   Для кодирования букв О, Л, А, З, К используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ЗАКОЛКА и записать результат в шестнадцатеричном коде, то получится:

1) 4531253                2) 9876                       3) E832                          4) 238E

35)   Для кодирования букв О, В, Д, П, А используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ВОДОПАД и записать результат в восьмеричном коде, то получится:

1) 22162                     2) 1020342                3) 2131453                   4) 34017

36)   Для кодирования букв Д, Х, Р, О, В используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ХОРОВОД и записать результат в восьмеричном коде, то получится:

1) 12334                     2) 2434541                3) 36714                       4) 16714

37)   Для кодирования букв Р, С, Н, О, Г используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов НОСОРОГ и записать результат в восьмеричном коде, то получится:

1) 34244                     2) 52634                     3) 55634                       4) 33334

38)   Для кодирования сообщения, состоящего только из букв A, M, N, E и O, используется неравномерный по длине двоичный код:

 A                       M                   N                       E                  O

000                  11                   01                     001               10

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 01100010001100                                      2) 01100100011001

3) 01100100011101                                      4) 01100100011100

39)   Кодирование сообщения происходило с использованием шифра переменной длины: А- 10, В- 11, С- 100, D- 101. После кодирования полученный двоичный шифр перевели в шестнадцатеричную систему счисления и получили: B7216. Определите зашифрованное сообщение.

1)ABDBCA                 2) DABCA                  3) DDBCA                      4) ABCDA

 

40)   Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=01, Б=1, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 0001                       2) 000                          3) 11                               4) 101

 

41)   Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 101                          2) 10                            3) 11                               4) 01

 

42)   Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=00, Б=11, В=100. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 010                          2) 0                              3) 01                               4) 011

 

43)   Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=000, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

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

 

44)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–11, В–000, Г–001, Д–011. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) это невозможно                                   2) для буквы Б – 1

3) для буквы Г – 00                                    4) для буквы Д – 01

 

45)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–11, Б–10, В–011, Г–000, Д–001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Г – 00                                    2) это невозможно

3) для буквы В – 01                                    4) для буквы Б – 1

 

46)   (http://ege.yandex.ru) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Г – 11                                    2) это невозможно

3) для буквы В – 000                                 4) для буквы Б – 00

47)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1110, Б–0, В–10, Г–110. Укажите, каким кодовым словом может быть закодирована буква Д.

Код должен удовлетворять свойству однозначного декодирования.

1) 0001                       2) 0011                       3) 0111                           4) 1111

48)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–111, Б–110, В–100, Г–0. Укажите, каким кодовым словом может быть закодирована буква Д.

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

1) 001                          2) 00                            3) 101                             4) 10

 

49)   (http://ege.yandex.ru) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный троичный код, позволяющий однозначно декодировать троичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А–11, Б–12, В–21, Г–22. Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 0                              2) 01                            3) 02                               4) 10

50)   (http://ege.yandex.ru) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А–0, Б–11, В–20, Г–21, Д–22. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Б – 1                                      2) это невозможно

3) для буквы В – 2                                      4) для буквы Д – 2Конец формы

51)    (http://ege.yandex.ru) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–111, Б–110, В–100, Г–101. Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 0                              2) 01                            3) 00                               4) 000

 

52)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.

Выберите правильный вариант ответа.

1) это невозможно

2) для буквы Г – 10

3) для буквы Д – 11

4) для буквы Д – 10

53)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 100, Б - 101, В - 111, Г - 110.

Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.

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

1) 10                            2) 000                          3) 11                               4) 1111

54)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 001, Б - 010, В - 000, Г - 011.

Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.

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

1) 00                            2) 01                            3) 0000                           4) 101

55)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 111, Б - 110, В - 101, Г - 100.

Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.

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

1) 1                        2) 0                        3) 01                      4) 10

56)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 000, Б - 001, В - 010, Г - 011.

Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.

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

1) 1                        2) 0                        3) 01                      4) 10

57)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 11111, Б - 11000, В - 00100. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 00000               2) 00011               3) 11100               4) не подходит ни одно из указанных выше слов

58)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 00110, Б - 11000, В - 10011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01101               2) 01001               3) 00011               4) не подходит ни одно из указанных выше слов

59)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 11100, Б - 00110, В - 01011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 11001               2) 10010               3) 10001               4) не подходит ни одно из указанных выше слов

60)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 01101, Б - 00110, В - 10001. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 11111               2) 11010               3) 01000               4) не подходит ни одно из указанных выше слов

61)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 00101, Б - 01011, В - 10110. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 10000               2) 01110               3) 11000               4) не подходит ни одно из указанных выше слов

62)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 01010, Б - 11001, В - 10100. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 00000               2) 00111               3) 01101               4) не подходит ни одно из указанных выше слов

63)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 01101, Б - 11011, В - 00010. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 10100               2) 10001               3) 11000               4) не подходит ни одно из указанных выше слов

64)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 01000, Б - 10011, В - 11101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 10100               2) 01011               3) 00110               4) не подходит ни одно из указанных выше слов

65)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 01110, Б - 10010, В - 00101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01000               2) 11001               3) 10111               4) не подходит ни одно из указанных выше слов

66)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 10110, Б - 11000, В - 00101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01011               2) 01110               3) 10001               4) не подходит ни одно из указанных выше слов

67)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 00100, Б - 01010, В - 11111. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 00001               2) 01001               3) 10001               4) не подходит ни одно из указанных выше слов

68)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 01000, Б - 00011, В - 11101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 00101               2) 01110               3) 10100               4) не подходит ни одно из указанных выше слов

69)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А - 10000, Б - 00101, В - 01010. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01111               2) 11011               3) 10110               4) не подходит ни одно из указанных выше слов

70)   (http://ege.yandex.ru) Для передачи помехоустойчивых сообщений в алфавите, который содержит 16 различных символов, используется равномерный двоичный код. Этот код удовлетворяет следующему свойству: в любом кодовом слове содержится четное количество единиц (возможно, ни одной). Какую наименьшую длину может иметь кодовое слово?

1) 3                  2) 4        3) 5        4) 6

71)   По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:

А-0, И-00, К-10, О-110, Т-111.

Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАА                  2) ИКОТА            3) КОТ                  4) ни одно из сообщений не подходит

 

72)   По каналу связи передаются сообщения, содержащие только 4 буквы – П, О, Р, Т. Для кодирования букв используются 5-битовые кодовые слова: П – 00000, О – 00111, Р – 11011, Т – 11100. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех (в предположении, что передаваемые биты могут искажаться, но не пропадают). Закодированное сообщение считается принятым корректно, если его длина кратна 5 и каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции; при этом считается, что пятёрка кодирует соответствующую букву. Например, если принята пятерка 11111, то считается, что передавалась буква Р. Среди приведённых ниже сообщений найдите то, которое принято корректно, и укажите его расшифровку (пробелы несущественны).

11011 10111 11101 00111 10001

   10000 10111 11101 00111 00001

1) ПОТОП           2) РОТОР            3) ТОПОР            4) ни одно из сообщений не принято корректно

               

73)   По каналу связи передаются сообщения, содержащие только 4 буквы – П, О, Р, Т. Для кодирования букв используются 5-битовые кодовые слова: П – 11111, О – 11000, Р – 00100, Т – 00011. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех (в предположении, что передаваемые биты могут искажаться, но не пропадают). Закодированное сообщение считается принятым корректно, если его длина кратна 5 и каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции; при этом считается, что пятёрка кодирует соответствующую букву. Например, если принята пятерка 00000, то считается, что передавалась буква Р. Среди приведённых ниже сообщений найдите то, которое принято корректно и укажите его расшифровку (пробелы несущественны).

11011 11100 00011 11000 01110

00111 11100 11110 11000 00000

1) ПОТОП           2) РОТОР            3) ТОПОР            4) ни одно из сообщений не принято корректно

 

74)   По каналу связи передаются сообщения, содержащие только 4 буквы:  E, Н, О, Т.  В любом сообщении больше всего букв О, следующая по частоте буква – Е, затем – Н. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

1) Е – 0, Н – 1, О – 00, Т – 11                       2) О – 1, Н – 0, Е – 01, Т – 10

3) Е – 1, Н – 01, О – 001, Т – 000                4) О – 0, Н – 10, Е – 111, Т – 110

75)   Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А - 10111, Б - 00000, В - 11010.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 00100, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается 'х').

Получено сообщение 10101 10000 11110 10010. Декодируйте это сообщение – выберите  правильный вариант.

1) АБВВ               2) хххх                 3) АБхх                                4) АБхВ

76)   Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А - 10001, Б - 01101, В - 10110.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01111, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается 'х').

Получено сообщение 00110 11101 11000 11001. Декодируйте это сообщение – выберите  правильный вариант.

1) ВБхх                2) ВБВА               3) хххх                 4) ВБхА

77)   Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А — 11010, Б — 00110, В — 10101.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается 'х').

Получено сообщение 00111 11110 11000 10111. Декодируйте это сообщение – выберите  правильный вариант.

1) БААх                               2) БААВ               3) хААх                               4) хххх

78)   Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А — 10010, Б — 11111, В — 00101.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01111, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается 'х').

Получено сообщение 10000 10101 11001 10111. Декодируйте это сообщение – выберите  правильный вариант.

1) АВББ               2) хххх                 3) АВхБ                               4) АххБ

79)   Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А — 11000, Б — 00010, В — 10101.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01010, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается 'х').

Получено сообщение 11110 10111 10010 10000. Декодируйте это сообщение – выберите  правильный вариант.

1) хххх                 2) АВБА               3) ххБА                                4) хВБА

 

80)   По каналу связи передаются сообщения, содержащие только 4 буквы: И, Г, Л, А. Для кодирования букв И, Г, Л используются 6-битовые кодовые слова:

И – 000000, Г – 001110, Л – 110110.

Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы А так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.

1) 111110      2) 111000            3) 000110            4) не подходит ни одно из указанных выше слов

81)   По каналу связи передаются сообщения, содержащие только 4 буквы: П, А, Р, К. Для кодирования букв П, А, Р используются 6-битовые кодовые слова:

П – 111111, А – 110001, Р – 001001.

Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы К так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.

1) 000001      2) 111001            3) 000111            4) не подходит ни одно из указанных слов

82)   (ege.yandex.ru) По каналу связи передаются сообщения, содержащие только 4 буквы А, И, С, Т. Для кодирования букв А, И, С используются 5-битовые кодовые слова: А - 10000, И - 11110, С - 01011. Для этих кодовых слов выполнено такое свойство: кодовые слова для разных букв отличаются не менее, чем в трех позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для буквы Т нужно выбрать кодовое слово так, чтобы оно тоже отличалось от кодовых слов для букв А, И, С не менее, чем в трех позициях. Какое из перечисленных ниже кодовых слов можно использовать для буквы Т?

1) 01111               2) 01001               3) 00101               4) не подходит ни одно из указанных слов

83)   (ege.yandex.ru) По каналу связи передаются сообщения, содержащие только 4 буквы Э, Ю, Я, Ы. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование. В любом сообщении больше всего букв Я, следующая по частоте буква — Ю, затем — Э. Буква Ы встречается реже, чем любая другая. Какой из перечисленных ниже кодов нужно использовать, чтобы передаваемые закодированные сообщения были как можно более короткими?

1) Э — 0, Ю — 1, Я — 00, Ы – 11

2) Я — 1, Ю – 0, Э — 01, Ы — 10

3) Э — 1, Ю — 01, Я — 001, Ы — 000

4) Я — 0, Ю — 11, Э — 101, Ы - 100

84)   По каналу связи передаются сообщения, содержащие только 4 буквы: А, Т, О, М; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 100, О: 00, М: 11.

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

1)  1       2) 0        3) 01      4) 101

85)   Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К – 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

Примечание. Префиксный код – это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

1) кодовое слово для буквы Е можно сократить до 01

2) кодовое слово для буквы К можно сократить до 1

3) кодовое слово для буквы Н можно сократить до 10

4) это невозможно

86)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, используется неравномерный двоичный префиксный код. Даны кодовые слова для четырёх букв: А – 011, Б – 010, В – 001, Г – 000. Какие кодовые слова из приведённых ниже вариантов подходят для букв Д и Е? Если подходит более одного варианта, укажите тот, для которого сумма длин кодовых слов меньше.

Примечание. Префиксный код – это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

1) Д – 100, Е – 110              3)  Д – 10, Е – 11

2) Д – 100, Е – 11                4) Д – 10, Е – 1

87)   По каналу связи передаются сообщения, содержащие только 4 буквы М, А, Р, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв М, А, Р используются такие кодовые слова: М: 010, А: 1, Р: 011.

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

88)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 1; Б – 0100; В – 000; Г – 011; Д – 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

1) для буквы Г – 11        2) для буквы В – 00       3) для буквы Г – 01        4) это невозможно

89)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 10; Б – 11; В – 000; Г – 001; Д – 010. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

1) это невозможно              2) для буквы А – 0         3) для буквы В – 00       4) для буквы Д – 01

90)   По каналу связи передаются сообщения, содержащие только 5 букв А, Д, Р, Т, К. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:
А — 1, Д — 00, Р — 10, Т — 110, К — 111.
Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) АКР                    2) РАД                    3) ТАРА                  4) ни одно из со­об­ще­ний не под­хо­дит

 

91)   По каналу связи передаются сообщения, содержащие только 5 букв А, К, Л, Р, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:
А — 01, К — 010, Л — 011, Р — 11, Т — 101.
Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) РАК                  2) ЛАК                  3) ТАРА                               4) ни одно из со­об­ще­ний не под­хо­дит

92)   По каналу связи передаются сообщения, содержащие только 5 букв А, К, Л, Р, У. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:
А — 01, Б — 10, К— 00, Л — 11, Р — 101.
Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КРАБ                               2) ЛАК                  3) АРКА               4) ни одно из со­об­ще­ний не под­хо­дит

93)   По каналу связи передаются сообщения, содержащие только 5 букв А, Б, В, К, Р. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:
А — 0, Б — 10, В — 00, К — 11, Р — 101.
Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАРА               2) РАК                  3) БАРК                               4) ни одно из со­об­ще­ний не под­хо­дит

94)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

1) 7        2) 8        3) 9        4) 10

95)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00; Б – 101; В – 011; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

1) это невозможно          2) для буквы Б – 01      

3) для буквы В – 11          4) для буквы Г – 11

96)   Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 11; Б – 110; В – 101; Г – 000; Д – 010. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

1) это невозможно          2) для буквы Б – 10      

3) для буквы В – 01          4) для буквы Д – 10

97)   (М.В. Кузнецова, г. Новокузнецк) По каналу связи передаются сообщения, содержащие только 4 буквы: Л, Е, О; для передачи используется двоичный код, допускающий однозначноедекодирование. Для букв Т, О, Л используются такие кодовые слова: Т – 101, О – 01, Л – 11. Укажите такое кодовое слово для буквы Е, при котором код будет допускать однозначное декодирование, при этом его длина должна быть наименьшей.  00

98)   (М.В. Кузнецова, г. Новокузнецк) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 001. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов? 9

99)   (М.В. Кузнецова, г. Новокузнецк) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д  решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 01, для буквы Б – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов? 12

100)    (М.В. Кузнецова, г. Новокузнецк) Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д  решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 101. Какова наименьшая возможная суммарная длина всех пяти кодовых слов? 13

101)    (М.В. Кузнецова, г. Новокузнецк) В сообщении встречается 7 разных  букв. При его передаче использован неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: 1, 01, 001. Коды остальных четырёх букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов? 26

102)    (М.В. Кузнецова, г. Новокузнецк) В сообщении встречается 10 разных  букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды трех букв: 11, 100, 101. Коды остальных семи букв имеют одинаковую длину. Какова минимальная суммарная длина всех 10-ти кодовых слов? 36

103)    (М.В. Кузнецова, г. Новокузнецк) В сообщении встречается 7 разных  букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды двух букв: 10, 111. Коды остальных пяти букв имеют одинаковую длину. Какова минимальная суммарная длина всех 7-ми кодовых слов? 20

104)    (М.В. Кузнецова, г. Новокузнецк) В сообщении встречается 50 букв А, 30 букв Б, 20 букв В и 5 букв Г. При его передаче использован неравномерный двоичный префиксный код, который позволил получить минимальную длину закодированного сообщения. Какова она в битах? 185

105)    По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

   а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

   б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:1, Б:01, В:001, Г:111

2) А:1, Б:01, В:10, Г:111

3) А:00, Б:01, В:10, Г:11

4) А:100, Б:101, В:11, Г:0

106)    По каналу связи передаются сообщения, каждое из которых содержит 10 букв А, 5 букв Б, 20 букв В и 5 букв Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

   а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

   б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:1, Б:01, В:001, Г:111

2) А:00, Б:01, В:10, Г:11

3) А:0, Б:10, В:11, Г:111

4) А:10, Б:111, В:0, Г:110

107)    Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

1)  13     2) 14      3) 15      4) 16

 



[1] Самылкина Н.Н., Островская Е.М. Информатика: тренировочные задания. – М.: Эксмо, 2009.

[2] Источники заданий:

1.   Демонстрационные варианты ЕГЭ 2004-2016 гг.

2.   Тренировочные и диагностические работы МИОО, СтатГрад.

3.   Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009.

4.   Самылкина Н.Н., Островская Е.М. Информатика: тренировочные задания. – М.: Эксмо, 2009, 2010.

5.   Якушкин П.А., Ушаков Д.М.  Самое полное издание типовых вариантов реальных заданий ЕГЭ 2010. Информатика.  — М.: Астрель, 2009.

6.   Абрамян М.Э., Михалкович С.С., Русанова Я.М., Чердынцева М.И.  Информатика. ЕГЭ шаг за шагом. — М.: НИИ школьных технологий, 2010.

7.   Чуркина Т.Е. ЕГЭ 2011. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2010.