Алгоритм Прима: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) (Общее описание алгоритма) |
Daryin (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| + | |||
| + | * [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html prim_minimum_spanning_tree]</code>), сложность <math>O(m \ln n)</math>. | ||
| + | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия 01:54, 11 июня 2015
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Описание схемы реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Описание ресурса параллелизма алгоритма
- 1.9 Описание входных и выходных данных
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритмов
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Описание локальности данных и вычислений
- 2.3 Возможные способы и особенности реализации параллельного алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Алгоритм Прима[1][2] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе.
1.2 Математическое описание
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Описание схемы реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Описание ресурса параллелизма алгоритма
1.9 Описание входных и выходных данных
1.10 Свойства алгоритма
2 Программная реализация алгоритмов
2.1 Особенности реализации последовательного алгоритма
2.2 Описание локальности данных и вычислений
2.3 Возможные способы и особенности реализации параллельного алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- Boost Graph Library (функция
prim_minimum_spanning_tree), сложность [math]O(m \ln n)[/math].
3 Литература
- ↑ Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.
- ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
