Основы теории информации и криптографии

Упражнение 1:

Номер 1

Статистическими методами называют:

Ответ:

(1) словарные алгоритмы

(2) арифметическое кодирование

(3) метод Шеннона-Фэно

(4) алгоритм Ферма

(5) метод Хаффмена

Номер 2

Словарные алгоритмы преимущественно отличаются от статистических тем, что:

Ответ:

(1) позволяют кодировать последовательности символов одинаковой длины

(2) позволяют кодировать последовательности символов разной длины

(3) позволяют быстрее кодировать символы

Номер 3

Популярность алгоритмов LZ обусловлена:

Ответ:

(1) простотой при высокой эффективности сжатия

(2) сложностью в работе, но гибкими настройками

(3) неэффективным сжатием, но высокая скорость работы

Упражнение 2:

Номер 1

Основная идея LZ77 состоит в том, что:

Ответ:

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

(2) первое и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на примитив

(3) второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение

Номер 2

Алгоритм LZ77 использует "скользящее" по сообщению окно, разделенное на две  части, выполняющие определенные функции:

Ответ:

(1) первая включает уже просмотренную часть сообщения. Вторая является буфером, содержащим еще незакодированные символы входного потока. Первая и вторая части равны

(2) первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока

(3) первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим уже закодированные, но еще не просмотренные символы входного потока

Номер 3

Алгоритм LZ77 выдает коды, состоящие из элементов:

Ответ:

(1) смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера

(2) длина этой подстроки

(3) первый символ буфера, следующий за подстрокой

Упражнение 3:

Номер 1

Алгоритм LZ77 выдает коды, состоящие из:

Ответ:

(1) двух элементов

(2) пяти элементов

(3) трех элементов

Номер 2

К недостаткам алгоритма LZ77 следует отнести:

Ответ:

(1) невозможность применять алгоритм для больших объемов информации

(2) с ростом размеров словаря скорость работы алгоритма-кодера пропорционально замедляется

(3) неэффективность алгоритма в целом

(4) кодирование одиночных символов очень неэффективно

Номер 3

Алгоритм LZSS отличается от LZ77 следующим:

Ответ:

(1) производимыми кодами

(2) скоростью работы

(3) длина подстроки, которую можно закодировать, НЕ ограничена размером буфера

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

Упражнение 4:

Номер 1

Код, выдаваемый LZSS, начинается с:

Ответ:

(1) собственно кода, без префикса

(2) двубитного префикса

(3) однобитного префикса

Номер 2

Собственно код, выдаваемый LZSS, состоит из:

Ответ:

(1) символ

(2) длина

(3) смещение

(4) примитив

Номер 3

LZ77 и LZSS обладают следующими очевидными недостатками:

Ответ:

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

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

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

Упражнение 5:

Номер 1

При чрезмерном увеличении размера словаря и буфера для алгоритмов LZ77 и LZSS, то это приведет:

Ответ:

(1) к снижению стойкости кода

(2) к увеличению эффективности кодирования

(3) к снижению эффективности кодирования

Номер 2

"Скользящее" окно НЕ использует алгоритм:

Ответ:

(1) LZ77

(2) LZ78

(3) LZSS

Номер 3

Закодировать сообщения "СИНЯЯ СИНЕВА СИНИ", вычислить длины в битах полученных кодов, используя алгоритм LZW (словарь - ASCII+ и 16 фраз):

Ответ:

(1)

длина 14 * 9 = 126 бит

(2)

длина 13 * 9 = 117 бит

(3)

длина 12 * 9 = 108 бит

Упражнение 6:

Номер 1

Запатентованным является алгоритм:

Ответ:

(1) LZ78

(2) LZSS

(3) LZW

Номер 2

Закодировать сообщения "AABCDAACCCCDBB", вычислить длины в битах полученных кодов, используя алгоритм LZ77 (словарь - 12 байт, буфер - 4 байта):

Ответ:

(1)

длина 8 * 13 = 104 бита

(2)

длина 8 * 15 = 120 бит

(3)

длина 8 * 10 = 80 бит

Номер 3

Закодировать сообщения "AABCDAACCCCDBB", вычислить длины в битах полученных кодов, используя алгоритм LZ78 (словарь - 16 фраз):

Ответ:

(1)

\langle 0,'A'\rangle \langle 1,'B' \rangle \langle 0,'C' \rangle \langle 0,'D' \rangle \langle 1,'A' \rangle \langle 3,'C' \rangle
\langle 6,'D' \rangle \langle 0,'B' \rangle \langle 0,'B' \rangle,

длина 9 * 12 = 108 бит

(2)

\langle 4,'A'\rangle \langle 1,'B' \rangle \langle 1,'C' \rangle \langle 1,'D' \rangle \langle 0'A' \rangle \langle 2,'C' \rangle
\langle 5,'D' \rangle \langle 7,'B' \rangle,

длина 9 * 10 = 90 бит

(3)

\langle 0,'A'\rangle \langle 0,'C' \rangle \langle 0,'D' \rangle \langle 3,'C' \rangle
\langle 6,'D' \rangle \langle 0,'B' \rangle \langle 0,'B' \rangle,

длина 9 * 14 = 126 бит

Упражнение 7:

Номер 1

Закодировать сообщения "КИБЕРНЕТИКИ", вычислить длины в битах полученных кодов, используя алгоритм LZW (словарь - ASCII+ и 16 фраз):

Ответ:

(1)

длина 10 * 9 = 90 бит

(2)

0'К'0'И'0'Б'0'Е'0'Р'0'Н'
1 \langle 9,1 \rangle 0'Т'1 \langle 5,1 \rangle 1 \langle 5,2 \rangle,

длина 3 * 7 + 7 * 9 = 84 бит

(3)

длина 10 * 9 = 90 бит

Номер 2

Закодировать сообщения "КИБЕРНЕТИКИ", вычислить длины в битах полученных кодов, используя алгоритм LZSS (словарь - 12 байт, буфер - 4 байта):

Ответ:

(1)

длина 10 * 9 = 90 бит

(2)

0'К'0'И'0'Б'0'Е'0'Р'0'Н'
1 \langle 9,1 \rangle 0'Т'1 \langle 5,1 \rangle 1 \langle 5,2 \rangle,

длина 3 * 7 + 7 * 9 = 84 бит

(3)

0'К'0'И'0'Б'0'Е'Р'0'Н'
1 \langle 9,1 \rangle 0'Т'1 \langle 5,2 \rangle,

длина 3 * 7 + 7 * 9 = 84 бит

Номер 3

Закодировать сообщения "СИНЯЯ СИНЕВА СИНИ", вычислить длины в битах полученных кодов, используя алгоритм LZ77 (словарь - 12 байт, буфер - 4 байта):

Ответ:

(1)

\langle 0,0,'С' \rangle \langle 0,0,'И' \rangle \langle 0,0,'Н' \rangle
\langle 0,0,'Я' \rangle \langle 11,1' ' \rangle \langle 6,3,'Е' \rangle \langle 0,0,'В' \rangle \langle 0,0,'А' \rangle \langle 5,4,'И' \rangle,

длина 9 * 15 = 135 бит

(2)

длина 9 * 13 = 117 бит

(3)

длина 9 * 10 = 90 бит

Основы теории информации и криптографии - тест 6