Алгоритмические основы растровой графики

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

Номер 1

Что называют алгоритмом сжатия изображения без потерь (англ. lossless compression)?

Ответ:

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

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

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

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

Номер 2

Что называют алгоритмом сжатия изображения c потерями (англ. lossy compression)?

Ответ:

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

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

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

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

Номер 3

Что называют алгоритмом сжатия изображений?

Ответ:

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

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

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

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

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

Номер 1

В каких графических форматах представления изображений используется сжатие без потерь?

Ответ:

(1) GIF

(2) JPEG

(3) JPEG2000

(4) PNG

(5) PCX

(6) TGA

(7) TIFF

(8) LZW

Номер 2

В каких графических форматах представления изображений используется сжатие с потерями?

Ответ:

(1) GIF

(2) JPEG

(3) JPEG2000

(4) PNG

(5) PCX

(6) TGA

(7) TIFF

(8) LZW

Номер 3

В каких графических форматах представления изображений используется сжатие данных?

Ответ:

(1) GIF

(2) JPEG

(3) JPEG2000

(4) PNG

(5) PCX

(6) TGA

(7) TIFF

(8) LZW

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

Номер 1

Какой код получается алгоритмом кодирования длины повторения RLE на битовом уровне для последовательности, состоящей из 21 единицы, 21 нуля, 3 единиц и 7 нулей при кодировании числа повторений тремя битами?

Ответ:

(1) 111 111 111 000 000 000 011 000

(2) 111 000 111 000 111 111 000 111 000 111 011 111

(3) 110 111 000 111 000 111 111 000 111 011

(4) 110 000 000 000 111 111 000

(5) 001 111 000 111 101 010

Номер 2

Какой код получается алгоритмом кодирования длины повторения RLE на битовом уровне для последовательности, состоящей из 6 единиц, 21 нуля, 14 единиц и 3 нулей при кодировании числа повторений тремя битами?

Ответ:

(1) 111 111 111 000 000 000 011 000

(2) 111 000 111 000 111 111 000 111 000 111 011 111

(3) 110 111 000 111 000 111 111 000 111 011

(4) 110 000 000 000 111 111 000

(5) 001 111 000 111 101 010

Номер 3

Какой код получается алгоритмом кодирования длины повторения RLE на битовом уровне для последовательности, состоящей из 1 единицы, 14 нулей, 5 единиц и 2 нулей при кодировании числа повторений тремя битами?

Ответ:

(1) 111 111 111 000 000 000 011 000

(2) 111 000 111 000 111 111 000 111 000 111 011 111

(3) 110 111 000 111 000 111 111 000 111 011

(4) 110 000 000 000 111 111 000

(5) 001 111 000 111 101 010

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

Номер 1

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на битовом уровне кодом: 111 000 111 101 001 110 010 111 000 111 101 при кодировании числа повторений тремя битами?

Ответ:

(1) 14 единиц, 6 нулей, 7 единиц, 6 нулей, 14 единиц, 14 нулей 5 единиц

(2) 14 единиц, 5 нулей, 1 единица, 6 нулей, 2 единицы, 14 нулей 5 единиц

(3) 3 единицы, 10 нулей, 27 единиц, 5 нулей

(4) 3 единицы, 11 нулей, 28 единиц, 3 нуля

Номер 2

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на битовом уровне кодом: 011 111 000 011 111 000 111 000 111 000 110 101 при кодировании числа повторений тремя битами?

Ответ:

(1) 14 единиц, 6 нулей, 7 единиц, 6 нулей, 14 единиц, 14 нулей 5 единиц

(2) 14 единиц, 5 нулей, 1 единица, 6 нулей, 2 единицы, 14 нулей 5 единиц

(3) 3 единицы, 10 нулей, 27 единиц, 5 нулей

(4) 3 единицы, 11 нулей, 28 единиц, 3 нуля

Номер 3

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на битовом уровне кодом: 001 100 111 000 111 000 101 011 111 при кодировании числа повторений тремя битами?

Ответ:

(1) 14 единиц, 6 нулей, 7 единиц, 6 нулей, 14 единиц, 14 нулей 5 единиц

(2) 14 единиц, 5 нулей, 1 единица, 6 нулей, 2 единицы, 14 нулей 5 единиц

(3) 3 единицы, 10 нулей, 27 единиц, 5 нулей

(4) 3 единицы, 11 нулей, 28 единиц, 3 нуля

(5) 1 единица, 4 нуля, 19 единиц, 3 нуля, 7 единиц

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

Номер 1

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на байтовом уровне кодом: 15;164;78;255;126; при фиксированной границе М=127?

Ответ:

(1) 15, 37 раз 78, 128 раз 126

(2) 15, 53 раза 78, 111 раз 126

(3) 100, 79, 58, 128 раз 126

(4) 1раз 127,100, 79, 58, 128 раз 126

Номер 2

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на байтовом уровне кодом: 128;100;79;58;255;126; при фиксированной границе М=127?

Ответ:

(1) 15, 37 раз 78, 128 раз 126

(2) 15, 53 раза 78, 111 раз 126

(3) 100, 79, 58, 128 раз 126

(4) 1раз 127,100, 79, 58, 128 раз 126

Номер 3

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на байтовом уровне кодом: 46;210;78;128;100;56 при фиксированной границе М=127?

Ответ:

(1) 15, 37 раз 78, 128 раз 126

(2) 15, 53 раза 78, 111 раз 126

(3) 100, 79, 58, 128 раз 126

(4) 1раз 127,100, 79, 58, 128 раз 126

(5) 46, 83 раза 78, 1 раз 100, 56

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

Номер 1

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на байтовом уровне кодом: 46;210;78;128;100;56 при фиксированной границе М=200?

Ответ:

(1) 15, 37 раз 78, 128 раз 126

(2) 15, 53 раза 78, 111 раз 126

(3) 100, 79, 58, 128 раз 126

(4) 1раз 127,100, 79, 58, 128 раз 126

(5) 46, 10 раз 78, 128, 100, 56

Номер 2

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на байтовом уровне кодом: 128;100;79;58;255;126 при фиксированной границе М=200?

Ответ:

(1) 15, 37 раз 78, 128 раз 126

(2) 15, 53 раза 78, 111 раз 126

(3) 100, 79, 58, 128 раз 126

(4) 128,100, 79, 58, 55 раз 126

(5) 46, 83 раза 78, 1 раз 100, 56

Номер 3

Какая последовательность закодирована алгоритмом кодирования длины повторения RLE на байтовом уровне кодом: 15;164;78;255;126; при фиксированной границе М=200?

Ответ:

(1) 15, 37 раз 78, 128 раз 126

(2) 15, 164, 78, 55 раз 126

(3) 100, 79, 58, 128 раз 126

(4) 1раз 127,100, 79, 58, 128 раз 126

(5) 46, 83 раза 78, 1 раз 100, 56

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

Номер 1

Какой алгоритм сжимает без потерь любой набор данных?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 2

Идея какого алгоритма используется при передаче факсов?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 3

Какой алгоритм используется в формате PCX?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

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

Номер 1

Какой алгоритм был первым алгоритмом, использующим словарь?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 2

Сочетание каких алгоритмов называют методом DEFLATE использующимся в графическом формате PNG?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 3

Какой алгоритм является модификацией метода LZ78?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

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

Номер 1

В каком алгоритме словарь представляет собой таблицу, которая заполняется цепочками элементов по мере работы алгоритма?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 2

Модификации какого алгоритма используются во множестве архиваторов общего назначения, а также в таких форматах как GIF и TIFF?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 3

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

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

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

Номер 1

Какие недостатки алгоритма Хаффмена были призваны решить его адаптивные модификации?

Ответ:

(1) слишком низкую степень сжатия

(2) двухпроходную суть алгоритма Хаффмена

(3) очень медленную скорость декодирования

(4) необходимость хранить таблицу весов для декодирования

Номер 2

Какие действия входят в алгоритм построения кодового дерева Хаффмена?

Ответ:

(1) увеличивается значение веса в соответствующем терминальном узле при поступлении очередного элемента

(2) создать n терминальных узлов по числу элементов в алфавите

(3) в каждый узел записать соответствующие веса

(4) создать родительский узел и соединить с ним два свободных узла с минимальными весами

Номер 3

Как осуществляется декодирование кода полученного алгоритмом Хаффмена?

Ответ:

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

(2) прямой заменой кода на соответствующий элемент пока не достигнута отметка конца кода

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

(4) по схеме: инициализация дерева, получение кода, расшифровка

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

Номер 1

Какой из алгоритмов использует префиксный код для представления элементов?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 2

Какой алгоритм дает коды, почти равные длинам оптимальных кодов из теоремы Шеннона?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

Номер 3

Какой алгоритм требует наибольших вычислительных затрат?

Ответ:

(1) RLE - битовый уровень

(2) RLE - байтовый уровень

(3) алгоритм LZ77

(4) алгоритм LZW

(5) алгоритм Хаффмена

(6) алгоритм арифметического кодирования

(7) нет такого алгоритма

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

Номер 1

В чем заключается декодирование кода, полученного алгоритмом арифметического кодирования?

Ответ:

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

(2) в коррекции дроби после обработки очередного элемента

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

(4) в расшифровке дроби по известному распределению вероятностей появления элементов в последовательности

Номер 2

Как строится кодирующая дробь в алгоритме арифметического кодирования?

Ответ:

(1) при обработке очередного элемента производится корректировка исходного полуинтервала

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

(3) делением весов цепочки элементов на распределение вероятностей этих элементов

(4) делением весов каждого элемента на распределение вероятностей этого элемента

Номер 3

Для чего были предложены адаптивные модификации алгоритма арифметического кодирования?

Ответ:

(1) чтобы увеличить степень сжатия

(2) чтобы избавиться от необходимости совершать два прохода по последовательности

(3) чтобы уменьшить вычислительные затраты на алгоритм

(4) чтобы не хранить информацию о распределении вероятностей появления элементов

Алгоритмические основы растровой графики - тест 13