Главная / Безопасность /
Основы теории информации и криптографии / Тест 5
Основы теории информации и криптографии - тест 5
Упражнение 1:
Номер 1
Бинарное дерево называется упорядоченным, если:
Ответ:
 (1) его узлы НЕ могут быть перечислены в порядке убывания веса 
 (2) его узлы находятся на разных ярусах 
 (3) его узлы могут быть перечислены в порядке неубывания веса и в этом перечне узлы, имеющие общего родителя, должны находиться рядом, на одном ярусе 
Номер 2
При кодировании методом Хаффмена и на 0 и на 1 придется тратить:
Ответ:
 (1) максимум один бит 
 (2) не менее одного бита 
 (3) не менее одного байта 
Номер 3
Преимущество арифметического кодирования позволяет:
Ответ:
 (1) кодировать некоторые символы менее чем одним битом 
 (2) кодировать некоторые символы только несколькими битами 
 (3) кодировать символы одним байтом 
Упражнение 2:
Номер 1
Вычислить длины кодов Хаффмена и арифметического для сообщения AAB, полученного от дискретной случайной величины X
со следующим распределением вероятностей P(X=A)=1/3
, P(X=B)=2/3
:
Ответ:
 (1) LХаффмена = 3.5 бита, Lарифметический = 4.4 бита
 
 (2) LХаффмена = 4 бита, Lарифметический = 3 бита
 
 (3) LХаффмена = 3 бита, Lарифметический = 4 бита
 
Номер 2
Составить арифметический код для сообщения BAABC, полученного от дискретной случайной величины X
со следующим распределением вероятностей P(X=A)=1/4
, P(X=B)=1/2
, P(X=C)=1/4
:
Ответ:
 (1) 010001101 
 (2) 010001011 
 (3) 010001001 
Номер 3
Составить арифметический код для сообщения BAABC, полученного от дискретной случайной величины X
со следующим распределением вероятностей P(X=A)=1/3
, P(X=B)=7/15
, P(X=C)=1/5
:
Ответ:
 (1) 01011111 
 (2) 01100001 
 (3) 01100111 
Упражнение 3:
Номер 1
Дискретная случайная величина X
может принимать три различных значения. При построении блочного кода с длиной блока 4 для X
необходимо будет рассмотреть дискретную случайную величину X
- выборку четырех значений X
. X
может иметь:
Ответ:
 (1) 75 различных значений 
 (2) 27 различных значений 
 (3) 81 различное значение 
Номер 2
Дискретная случайная величина X
может принимать три различных значения. Если считать сложность построения кода пропорциональной количеству различных значений кодируемой дискретной случайной величины, то блочный код для X
по сравнению с неблочным сложнее строить в:
Ответ:
 (1) в 81 раз 
 (2) в 27 раз 
 (3) в 25 раз 
Номер 3
Вычислить длины в битах сообщения "AABCDAACCCCDBB" в коде ASCII+ и его полученного кода
Ответ:
 (1) L(AABCDAACCCCDBB) = 62 бит, длина исходного сообщения = 112 бит
 
 (2) L(AABCDAACCCCDBB) = 52 бит, длина исходного сообщения = 94 бит
 
 (3) L(AABCDAACCCCDBB) = 76 бит, длина исходного сообщения = 137 бит
 
Упражнение 4:
Номер 1
Считая, что код генерируется дискретной случайной величиной X
с распределением P(X=A)=2/3
, P(X=B)=1/3
вычислить длины кодов Хаффмена, блочного Хаффмена (для блоков длины 2 и 3) для сообщения ABAAAB:
Ответ:
 (1) LХаффмена-1(ABAAAB) = 5 бит, LХаффмена-2(ABAAAB) = 5 бит, LХаффмена-3(ABAAAB) = 6 бит
 
 (2) LХаффмена-1(ABAAAB) = 5 бит, LХаффмена-2(ABAAAB) = 6 бит, LХаффмена-3(ABAAAB) = 4 бита
 
 (3) LХаффмена-1(ABAAAB) = 6 бит, LХаффмена-2(ABAAAB) = 5 бит, LХаффмена-3(ABAAAB) = 5 бит
 
Номер 2
Считая, что код генерируется дискретной случайной величиной X
с распределением P(X=A)=2/3
, P(X=B)=1/3
вычислить длину арифметического кода для сообщения ABAAAB:
Ответ:
 (1) Lарифметический(ABAAAB) = 2 бита
 
 (2) Lарифметический(ABAAAB) = 1 бит
 
 (3) Lарифметический(ABAAAB) = 1.5 бит
 
Номер 3
Закодировать сообщение "СИНЯЯ СИНЕВА СИНИ", используя адаптивный алгоритм Хаффмена с упорядоченным деревом:
Ответ:
 (1) код(СИНЯЯ СИНЕВА СИНИ) = 'С'0'И'
00'Н'100'Я'001100' '101001011100'Е'11000'В'10100'А'1010101101101111
 
 (2) код(СИНЯЯ СИНЕВА СИНИ) = 'С'0'И'
00'Я'101'Я'001101' '101001011100'С'11110'И'10100'И'1010111101101011
 
 (3) код(СИНЯЯ СИНЕВА СИНИ) = 'С'0'И'
01'Я'100'Я'111100' '101001011100'Е'11010'В'11100'А'1010111100101010
 
Упражнение 5:
Номер 1
Закодировать сообщение BBCBBC, используя адаптивный алгоритм Хаффмена с упорядоченным деревом:
Ответ:
 (1) 'C'01'B'0100
 
 (2) 'B'11'C'1001
 
 (3) 'B'10'C'1101
 
Номер 2
Закодировать сообщение "AABCDAACCCCDBB", используя адаптивный алгоритм Хаффмена с упорядоченным деревом:
Ответ:
 (1) код(AABCDAACCCCDBB) = 'A'10'B'00'C'011'D'00011001111100110011110
 
 (2) код(AABCDAACCCCDBB) = 'A'10'B'00'C'000'D'00011001111100110011001
 
 (3) код(AABCDAACCCCDBB) = 'A'11'B'11'C'010'D'00011001111100110000101
 
Номер 3
Закодировать сообщение "КИБЕРНЕТИКИ", используя адаптивный алгоритм Хаффмена с упорядоченным деревом:
Ответ:
 (1) код(КИБЕРНЕТИКИ) = 'К'0'И'00'Б'100'Е'000'Р'1
100'Н'1111000'Т'100110111
 
 (2) код(КИБЕРНЕТИКИ) = 'К'0'И'00'Б'101'Е'010'Р'1
100'Н'1100001'Т'100110001
 
 (3) код(КИБЕРНЕТИКИ) = 'К'0'И'00'Б'100'Е'000'Р'1
100'Н'1111000'Т'101010001
 
Упражнение 6:
Номер 1
Вычислить длины в битах сообщения "КИБЕРНЕТИКИ" в коде ASCII+ и его полученного кода
Ответ:
 (1) L(КИБЕРНЕТИКИ) = 98 бит, длина исходного сообщения = 102 бита
 
 (2) L(КИБЕРНЕТИКИ) = 72 бита, длина исходного сообщения = 75 бит
 
 (3) L(КИБЕРНЕТИКИ) = 85 бит, длина исходного сообщения = 88 бит
 
Номер 2
Вычислить длины в битах сообщения "СИНЯЯ СИНЕВА СИНИ" в коде ASCII+ и его полученного кода
Ответ:
 (1) L(СИНЯЯ СИНЕВА СИНИ) = 104 бит, длина исходного сообщения = 124 бит
 
 (2) L(СИНЯЯ СИНЕВА СИНИ) = 114 бит, длина исходного сообщения = 136 бит
 
 (3) L(СИНЯЯ СИНЕВА СИНИ) = 124 бит, длина исходного сообщения = 148 бит
 
Номер 3
Составить адаптивный арифметический код с маркером конца для сообщения BAABC:
Ответ:
 (1) 01000010111001 
 (2) 01000011000011 
 (3) 01000010110100 
Упражнение 7:
Номер 1
Распаковать сообщение 'A'0'F'00'X'0111110101011011110100101
, полученное по адаптивному алгоритму Хаффмена с упорядоченным деревом
Ответ:
 (1) FFXAAAXFXAXFFAA 
 (2) AFXFFAXFXAXAAAF 
 (3) AFXAFFXFXAXAFFA 
Номер 2
Cообщение, полученное путем сжатия адаптивным алгоритмом Хаффмена с упорядоченным деревом имеет вид: 'A'0'F'00'X'0111110101011011110100101
. Определить длину несжатого сообщения в битах:
Ответ:
 (1) 125 бит 
 (2) 120 бит 
 (3) 117 бит 
Номер 3
Cообщение, полученное путем сжатия адаптивным алгоритмом Хаффмена с упорядоченным деревом имеет вид: 'A'0'F'00'X'0111110101011011110100101
. Определить длину сжатого кода в битах:
Ответ:
 (1) 52 бит 
 (2) 62 бит 
 (3) 58 бит