Обсуждение участника:Sarseev: различия между версиями
Zhum (обсуждение | вклад) |
Lira (обсуждение | вклад) (→Замечания от 2016_12_11 1: новая тема) |
||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
п 2.4 | п 2.4 | ||
| − | + | Примечание: задержка с последней правкой вызвана трёхдневным перебоем в работе системы BlueGene, из-за чего было невозможно доделать недостающие графики. --[[Участник:Sarseev|Сергей Арсеев]] ([[Обсуждение участника:Sarseev|обсуждение]]) 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|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 22:12, 11 декабря 2016 (MSK) | ||
Текущая версия на 22:12, 11 декабря 2016
п 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)
