Теория и практика параллельных вычислений

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

Номер 1

Задача сортировки данных обычно формулируется как:

Ответ:

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

(2) задача разделения элементов набора значений на несколько частей

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

Номер 2

Внутренняя сортировка это:

Ответ:

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

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

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

Номер 3

Нижняя оценка необходимого количества операций для упорядочивания набора из n значений определяется выражением:

Ответ:

(1)

(2)

(3)

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

Номер 1

Базовая операция "сравнить и переставить" состоит из:

Ответ:

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

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

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

Номер 2

Базовая операция "сравнить и переставить" обычно используется в:

Ответ:

(1) последовательных алгоритмах сортировки

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

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

Номер 3

Базовая операция "сравнить и разделить" отличается от операции "сравнить и переставить":

Ответ:

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

(2) выбором ведущего элемента

(3) тем, что она не содержит операций обменов данными между процессами

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

Номер 1

Трудоемкость алгоритма пузырьковой сортировки оценивается выражением:

Ответ:

(1)

(2)

(3)

Номер 2

Трудоемкость параллельного алгоритма чет-нечетной сортировки оценивается выражением:

Ответ:

(1)

(2)

(3)

Номер 3

Общее число итераций параллельного алгоритма чет-нечетной сортировки при использовании p процессоров равно:

Ответ:

(1) p

(2) plog₂ p

(3) p²

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

Номер 1

Параллельный вариант алгоритма Шелла состоит в следующем:

Ответ:

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

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

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

Номер 2

Основными отличиями параллельного алгоритма Шелла от метода чет-нечетной перестановки являются:

Ответ:

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

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

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

Номер 3

Общее наименьшее количество итераций параллельного алгоритма Шелла равно:

Ответ:

(1) log₂ p

(2) p²

(3) plog₂ p

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

Номер 1

Алгоритм быстрой сортировки основан на:

Ответ:

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

(2) упорядочивании элементов равноотстоящих пар элементов, используя метод сортировки вставками

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

Номер 2

При надлежащем выборе ведущих элементов в алгоритме быстрой сортировки исходный массив данных оказывается упорядоченным после выполнения:

Ответ:

(1) log₂ n итераций

(2) n² итераций

(3) n log₂ n итераций

Номер 3

В худшем случае трудоемкость быстрой сортировки оценивается выражением:

Ответ:

(1)

(2)

(3)

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

Номер 1

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

Ответ:

(1) правильность выбора ведущего элемента

(2) исходная упорядоченность данных на процессорах

(3) близость процессоров физической структуры сети в топологии гиперкуба

Номер 2

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

Ответ:

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

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

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

Номер 3

Три схемы распараллеливания алгоритма быстрой сортировки различаются:

Ответ:

(1) стратегией выбора ведущего элемента

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

(3) стратегией выбора ведущего процесса

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

Номер 1

Для того чтобы выбрать ведущий элемент в параллельном алгоритме быстрой сортировки выполняются следующие действия:

Ответ:

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

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

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

Номер 2

Один из этапов параллельного алгоритма быстрой сортировки состоит том, что:

Ответ:

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

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

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

Номер 3

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

Ответ:

(1) два подмножества процессоров по p/2 процессоров в каждом и, таким образом, исходный N-мерный гиперкуб также оказывается разделенным на два гиперкуба размерности N-1

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

(3) два подмножества процессоров по p/2 процессоров в каждом и, таким образом, исходный N-мерный гиперкуб также оказывается разделенным на два гиперкуба размерности N/2

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

Номер 1

В обобщенном алгоритме быстрой сортировки в дополнение к обычному методу быстрой сортировки предлагается:

Ответ:

(1) конкретный способ выбора ведущих элементов

(2) конкретный способ выбора ведущих процессоров

(3) оптимальным способом рассылки ведущего элемента остальным процессорам

Номер 2

При выполнении алгоритма обобщенной быстрой сортировки в качестве ведущего элемента обычно выбирается:

Ответ:

(1) средний элемент блока данных какого-либо процессора системы (например, первого процессора)

(2) наименьший элемент среди средних элементов блоков данных процессоров системы

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

Номер 3

Для поддержки упорядоченности в ходе выполнения алгоритма обобщенной быстрой сортировки процессоры должны выполнять:

Ответ:

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

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

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

Теория и практика параллельных вычислений - тест 9