Обсуждение участника:Sarseev

Материал из Алговики
Перейти к навигации Перейти к поиску

п 2.4

Примечание: задержка с последней правкой вызвана трёхдневным перебоем в работе системы BlueGene, из-за чего было невозможно доделать недостающие графики. --Сергей Арсеев (обсуждение) 22:24, 3 декабря 2016 (MSK)

  • нет пояснений к первым двум графикам - нужно нечто аналогичное пояснению третьего.

Замечания от 2016_12_11 1

Раздел 1.1

"ребром, длина которого ..."

Лучше не "длина", а "вес".

Раздел 1.3

[math]O(|E|*log(|E|)) = O(n^2*log(n^2)) = O(2*n^2*log(n)) = O(n^2*log(n))[/math] Так и пишите везде.

Раздел 1.5

Текст алгоритма не является содержательным.

Раздел 1.8

Туманная фраза "Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую сложность [math]O(n*log(n))[/math]."

во-первых, непонятна: что такое [math]n[/math]?

во-вторых, противоречит оценке сложности [math]O(n^2*log(n))[/math]

в-третьих, не содержит указания на используемое число процессоров

в-четвертых, требует указания конкретных ссылок и/или описания соответствующих алгоритмов.

Раздел 2

Что и как распараллелено https://github.com/gpiskas/MinSpanTree_Kruskal_MPI_OpenMP?

Фактически есть три этапа:

- построение полного графа

- построение остовного дерева

- выявление заданного числа рёбер максимальной длинны

Какова степень параллелизма каждого из этапов?

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

Верно ли, что каждый из этапов имеет оценку вычислительной сложности [math]O(n*log(n))[/math]?

Почему, и при каком числе процессоров?


Пока рисунки "висят в воздухе", вне связи с остальным текстом.

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


--Lira (обсуждение) 22:12, 11 декабря 2016 (MSK)