игра брюс 2048
Главная / Программирование / Теория и практика параллельных вычислений / Тест 10

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

Упражнение 1:
Номер 1
Граф это:

Ответ:

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

 (2) множество линий (дуг), соединенных друг с другом 

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


Номер 2
Взвешенный граф это:

Ответ:

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

 (2) граф, вершинам которого приписаны некоторые числовые характеристики (веса) 

 (3) граф, разделенный на две части с равными весами 


Номер 3
Матрица смежности это:

Ответ:

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

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

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


Упражнение 2:
Номер 1
Задача поиска всех кратчайших путей обычно формулируется как:

Ответ:

 (1) для данного графа найти минимальные длины путей между каждой парой его вершин 

 (2) для данного графа найти минимальное расстояние среди всех пар его вершин 

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


Номер 2
Сложность последовательного алгоритма Флойда имеет порядок:

Ответ:

 (1) n3 

 (2) n2 

 (3) n2log2 n 


Номер 3
Показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид (без учета затрат на передачу данных):

Ответ:

 (1) Sp=p, Ep=1 

 (2) Sp=p, Ep=p 

 (3) Sp=1, Ep=p 


Упражнение 3:
Номер 1
Число итераций параллельного алгоритма Флойда равно:

Ответ:

 (1) n 

 (2) math 

 (3) n2 


Номер 2
Один из возможных способов агрегации вычислений для увеличения эффективности параллельного алгоритма Флойда состоит:

Ответ:

 (1) в горизонтальном разбиении обрабатываемой матрицы 

 (2) в диагональном разбиении обрабатываемой матрицы 

 (3) в поэлементном разбиении обрабатываемой матрицы 


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

Ответ:

 (1) только элементы одной из строк матрицы 

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

 (3) только элементы, лежащие на главной диагонали матрицы 


Упражнение 4:
Номер 1
Охватывающим деревом (или остовом) неориентированного графа называется:

Ответ:

 (1) подграф, который является деревом и содержит все вершины исходного графа 

 (2) бинарное дерево, содержащее все вершины исходного графа 

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


Номер 2
Минимально охватывающим деревом называется:

Ответ:

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

 (2) охватывающее дерево с минимальной высотой 

 (3) охватывающее дерево с минимальным количеством вершин 


Номер 3
Задача нахождения МОД формулируется как:

Ответ:

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

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

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


Упражнение 5:
Номер 1
Количество выполняемых операций при определении номера ближайшей вершины до охватывающего дерева и корректировке расстояний после расширения МОД ограничивается сверху величиной:

Ответ:

 (1) math 

 (2) math 

 (3) math 


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

Ответ:

 (1) Sp=p, Ep=1 

 (2) Sp=1, Ep=1 

 (3) Sp=p, Ep=p 


Номер 3
Трудоемкость нахождения МОД характеризуется:

Ответ:

 (1) квадратичной зависимостью от числа вершин графа 

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

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


Упражнение 6:
Номер 1
Задача оптимального разделения графа состоит в разбиении вершин графа на непересекающиеся подмножества:

Ответ:

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

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

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


Номер 2
Равновесность подмножеств вершин в задаче оптимального разделения графа:

Ответ:

 (1) может не соответствовать минимальности весов граничных ребер 

 (2) всегда соответствует минимальности весов граничных ребер 

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


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

Ответ:

 (1) к проблеме оптимального разделения графа 

 (2) к задаче поиска всех кратчайших путей 

 (3) к задаче нахождения минимального охватывающего дерева 


Упражнение 7:
Номер 1
Метод бинарного деления для решения задачи оптимального разделения графов заключается:

Ответ:

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

 (2) в рекурсивном разбиении на k равных частей исходного графа, где k – число вершин графа 

 (3) в рекурсивном разбиении на k2 равных частей исходного графа, где k – число вершин графа 


Номер 2
Для разбиения графа на k частей в методе бинарного деления для решения задачи оптимального разделения графов необходимо:

Ответ:

 (1) log2k уровней рекурсии 

 (2) k уровней рекурсии 

 (3) k/2 уровней рекурсии 


Номер 3
Для разбиения графа на k частей в методе бинарного деления для решения задачи оптимального разделения графов необходимо выполнить:

Ответ:

 (1) k-1 деление графа пополам 

 (2) k/2 делений графа пополам 

 (3) log2k делений графа пополам 


Упражнение 8:
Номер 1
Метод покоординатного разбиения для решения задачи оптимального разделения графов отличается от метода бинарного деления тем, что:

Ответ:

 (1) деление сети пополам происходит по наиболее длинной стороне 

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

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


Номер 2
На одном из этапов метода покоординатного разбиения для решения задачи оптимального разделения графов:

Ответ:

 (1) вычисляются центры масс элементов сети 

 (2) вычисляется центр графа 

 (3) вычисляется середина сети 


Номер 3
Для определения угла поворота в рекурсивном инерционном методе деления пополам при решении задачи оптимального разделения графов, используется:

Ответ:

 (1) главная инерционная ось сети 

 (2) кривые Пеано, построенные на основании сети 

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


Упражнение 9:
Номер 1
Основное отличие комбинаторных алгоритмов от геометрических методов, применяемых для решения задачи оптимального разделения графов, заключается:

Ответ:

 (1) в использовании графа, построенного для исходной сети, а не самой сети 

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

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


Номер 2
В отличие от геометрических схем комбинаторные методы решения задачи оптимального разделения графов не принимают во внимание:

Ответ:

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

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

 (3) информацию о связности элементов сети друг относительно друга 


Номер 3
Комбинаторные методы решения задачи оптимального разделения графов обычно обеспечивают:

Ответ:

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

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

 (3) более быстрое решение поставленной задачи 




Главная / Программирование / Теория и практика параллельных вычислений / Тест 10