Алгоритм Шилоаха-Вишкина поиска компонент связности - История изменений

ASA в 11:49, 6 июля 2022

2022-07-06T11:49:45Z

← Предыдущая версия		Версия от 11:49, 6 июля 2022
Строка 34:		Строка 34:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~
	== Литература ==		== Литература ==
	<references />		<references />

Apaokin в 12:04, 19 июня 2018

2018-06-19T12:04:55Z

← Предыдущая версия		Версия от 12:04, 19 июня 2018
Строка 44:		Строка 44:
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
	* Ligra {{Buttonlinkimp\|35}}
	* Gap {{Buttonlinkimp\|40}}
	== Литература ==		== Литература ==
	<references />		<references />

Apaokin в 11:39, 19 июня 2018

2018-06-19T11:39:51Z

← Предыдущая версия		Версия от 11:39, 19 июня 2018
Строка 45:		Строка 45:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			* Ligra {{Buttonlinkimp\|35}}
			* Gap {{Buttonlinkimp\|40}}
	== Литература ==		== Литература ==
	<references />		<references />

ASA в 13:53, 14 марта 2018

2018-03-14T13:53:44Z

← Предыдущая версия		Версия от 13:53, 14 марта 2018
Строка 50:		Строка 50:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Shiloach-Vishkin algorithm for finding the connected components]]

ASA в 11:21, 29 июля 2015

2015-07-29T11:21:38Z

← Предыдущая версия		Версия от 11:21, 29 июля 2015
Строка 8:		Строка 8:
	}}		}}

	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм Шилоаха-Вишкина'''<ref>Shiloach, Yossi, and Uzi Vishkin. “An <math>O(\log n)</math> Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.</ref> (англ. Shiloach-Vishking Algorithm) предназначен [[Связность в графах\|для поиска компонент связности]] неориентированного графа. Используется структура данных, аналогичная [[Система непересекающихся множеств\|системе непресекающихся множеств]]. В модели CRCW PRAM алгоритм приписывает каждой вершине идентификатор компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.		'''Алгоритм Шилоаха-Вишкина'''<ref>Shiloach, Yossi, and Uzi Vishkin. “An <math>O(\log n)</math> Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.</ref> (англ. Shiloach-Vishking Algorithm) предназначен [[Связность в графах\|для поиска компонент связности]] неориентированного графа. Используется структура данных, аналогичная [[Система непересекающихся множеств\|системе непресекающихся множеств]]. В модели CRCW PRAM алгоритм приписывает каждой вершине идентификатор компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.

	=== Математическое описание ===		=== Математическое описание алгоритма ===
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===

	Алгоритм изначально параллельный и при последовательной реализации фактически превращается в [[Система непересекающихся множеств\|систему непресекающихся множеств]].		Алгоритм изначально параллельный и при последовательной реализации фактически превращается в [[Система непересекающихся множеств\|систему непресекающихся множеств]].
Строка 25:		Строка 25:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Время работы алгоритма составляет <math>O(\ln n)</math> на <math>n + 2m</math> процессорах в модели CRCW PRAM.		Время работы алгоритма составляет <math>O(\ln n)</math> на <math>n + 2m</math> процессорах в модели CRCW PRAM.

	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма===		=== Свойства алгоритма ===
	== Программная реализация ~~алгоритмов~~ ==
			== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	== Литература ==		== Литература ==
			<references />

	~~<references />~~		[[Категория:Начатые статьи]]

Daryin: Общее описание алгоритма

2015-06-06T18:47:35Z

Общее описание алгоритма

Новая страница

{{algorithm
| name = Алгоритм Шилоаха-Вишкина
| serial_complexity = <math>O((m + n) \ln n)</math>
| pf_height = <math>O(\ln n)</math>
| pf_width = <math>n + 2m</math>
| input_data = <math>O(m)</math>
| output_data = <math>n</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Алгоритм Шилоаха-Вишкина'''<ref>Shiloach, Yossi, and Uzi Vishkin. “An <math>O(\log n)</math> Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.</ref> (англ. Shiloach-Vishking Algorithm) предназначен [[Связность в графах|для поиска компонент связности]] неориентированного графа. Используется структура данных, аналогичная [[Система непересекающихся множеств|системе непресекающихся множеств]]. В модели CRCW PRAM алгоритм приписывает каждой вершине идентификатор компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.

=== Математическое описание ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===

Алгоритм изначально параллельный и при последовательной реализации фактически превращается в [[Система непересекающихся множеств|систему непресекающихся множеств]].

=== Последовательная сложность алгоритма ===

Последовательная сложность алгоритма Шилоаха-Вишкина <math>O((m + n) \ln n)</math>.

=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===

Время работы алгоритма составляет <math>O(\ln n)</math> на <math>n + 2m</math> процессорах в модели CRCW PRAM.

=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

<references />