Введение в параллельные алгоритмы

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

Номер 1

Алгоритму пузырьковой сортировки в наихудшем случае наиболее точно соответствует оценка числа операций:

Ответ:

(1) O(n*log(n))

(2) O(n^2)

(3) O(n)

Номер 2

Алгоритму сортировки слиянием в наихудшем случае наиболее точно соответствует оценка числа операций:

Ответ:

(1) O(n*log(n))

(2) O(n)

(3) O(log(n))

Номер 3

Алгоритму быстрой сортировки в наихудшем случае наиболее точно соответствует оценка числа операций:

Ответ:

(1) O(n*log(n))

(2) O(n^2)

(3) O(n)

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

Номер 1

Как соотносятся времена сортировки одного и того же массива с помощью алгоритмов простой вставки и слияния:

Ответ:

(1) алгоритм слияния всегда выполняется не быстрее, чем алгоритм простой вставки

(2) алгоритм слияния всегда выполняется не медленнее, чем алгоритм простой вставки

(3) зависит от числа элементов в сортируемом массиве

Номер 2

При сортировке слиянием массива из N элементов:

Ответ:

(1) необходимо использование дополнительной памяти для хранения N элементов

(2) ускорение пропорционально числу используемых процессоров

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

Номер 3

При упорядочивании массива из N элементов с помощью пирамидальной сортировки:

Ответ:

(1) необходимо использование дополнительной памяти для хранения N элементов

(2) число операций в худшем случае пропорционально N*log(N)

(3) при сортировке уже упорядоченного массива число операций пропорционально N

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

Номер 1

Что такое пирамида:

Ответ:

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

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

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

Номер 2

Что такое сбалансированное бинарное дерево:

Ответ:

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

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

(3) бинарное дерево называют сбалансированным, если число вершин дерева с корнем в левом потомке отличается не более чем на 1 от числа вершин дерева с корнем в правом потомке для любой вершины дерева

Номер 3

Что такое упорядоченная пирамида:

Ответ:

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

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

(3) пирамида называется упорядоченной, если вес любой вершины на уровне k не меньше веса любой вершины на уровне k-1

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

Номер 1

Использование гибридных методов сортировки позволяет:

Ответ:

(1) сократить число выполняемых операций

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

(3) увеличивает время выполнения алгоритма за счет его усложнения

Номер 2

Сверхлинейное ускорение возможно за счет:

Ответ:

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

(2) при сравнении с неэффективным последовательным алгоритмом

(3) невозможно

Номер 3

Верно ли, что:

Ответ:

(1) время выполнения пирамидальной сортировки массива из n элементов на вычислительной системе с неограниченной памятью пропорционально n*log(n) при наличии ограниченной кеш памяти

(2) число операций пирамидальной сортировки массива из n элементов на вычислительной системе с неограниченной памятью пропорционально n*log(n)

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

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

Номер 1

Укажите наиболее точную оценку числа тактов необходимых в худшем случае для упорядочивания 1000000 элементов массива методом быстрой сортировки, если операция сравнения и перестановки двух элементов занимает 1 такт:

Ответ:

(1) 1 000 000

(2) 6 000 000

(3) 1 000 000 000 000

Номер 2

Укажите наиболее точную оценку числа тактов необходимых в лучшем случае для упорядочивания 1 000 000 элементов массива методом пузырька сортировки, если операция сравнения и перестановки двух элементов занимает 1 такт:

Ответ:

(1) 1 000 000

(2) 6 000 000

(3) 1 000 000 000 000

Номер 3

Укажите наиболее точную оценку числа тактов необходимых для упорядочивания 1 000 000 элементов массива методом пирамидальной сортировки, если операция сравнения и перестановки двух элементов занимает 1 такт:

Ответ:

(1) 1 000 000

(2) 6 000 000

(3) 1 000 000 000 000

Введение в параллельные алгоритмы - тест 4