Алгоритм Ульмана - История изменений

ASA в 09:14, 6 июля 2022

2022-07-06T09:14:20Z

← Предыдущая версия		Версия от 09:14, 6 июля 2022
Строка 60:		Строка 60:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	Программа, реализующая поиск транзитного замыкания, состоит CPU части, отвечающей за общую координацию вычислений, использующей вспомогательные классы		Программа, реализующая поиск транзитного замыкания, состоит CPU части, отвечающей за общую координацию вычислений, использующей вспомогательные классы

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

	* C++: [http://cdelib.sourceforge.net Chemical Descriptors Library] (функция <code>[http://cdelib.sourceforge.net/doc/ullmann.html ullman]</code>).
	* C++: [http://mivia.unisa.it/datasets/graph-database/vflib/ VF Library].

	== Литература ==		== Литература ==

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

2018-03-14T13:50:57Z

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

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

			[[en:Ullman's algorithm]]

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

2018-03-06T14:13:48Z

← Предыдущая версия		Версия от 14:13, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

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

Teplov: /* Возможные способы и особенности параллельной реализации алгоритма */

2016-11-18T16:55:40Z

Возможные способы и особенности параллельной реализации алгоритма

← Предыдущая версия		Версия от 16:55, 18 ноября 2016
Строка 63:		Строка 63:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
			Программа, реализующая поиск транзитного замыкания, состоит CPU части, отвечающей за общую координацию вычислений, использующей вспомогательные классы

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====

Teplov: /* Ресурс параллелизма алгоритма */

2016-11-18T16:53:40Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 16:53, 18 ноября 2016
Строка 51:		Строка 51:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Перебор может быть эффективно параллелизован, в том числе с использованием графических ускорителей. Известны реализации, работающие напрямую с графовыми базами данных.		Перебор может быть эффективно параллелизован <ref>Abu-Khzam, F. N., Daudjee, K., Mouawad, A. E., & Nishimura, N. (2015). On scalable parallel recursive backtracking. Journal of Parallel and Distributed Computing. http://doi.org/10.1016/j.jpdc.2015.07.006 </ref>, в том числе с использованием графических ускорителей<ref>Wang, R., Guo, L., Ai, C., Li, J., Ren, M., & Li, K. (2015). An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU. EUC IEEE International Conference on High Performance Computing and Communications (HPCC) & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, 7(5), 1089–1096. http://doi.org/10.1109/HPCC.and.EUC.2013.154</ref>. Известны реализации, работающие напрямую с графовыми базами данных<ref>Teixeira, C. H. C., Fonseca, A. J., Serafini, M., Siganos, G., Zaki, M. J., & Aboulnaga, A. (2015). Arabesque: a system for distributed graph mining (pp. 425–440). Presented at the SOSP Symposium, New York, New York, USA: ACM Press. http://doi.org/10.1145/2815400.2815410</ref> <ref> Raman, R., van Rest, O., Hong, S., Wu, Z., Chafi, H., & Banerjee, J. (2014). PGX.ISO: Parallel and Efficient In-Memory Engine for Subgraph Isomorphism (pp. 1–6). Presented at the GRADES Workshop, New York, New York, USA: ACM Press. http://doi.org/10.1145/2621934.2621939</ref>.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Teplov: /* Ресурс параллелизма алгоритма */

2016-11-18T16:51:32Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 16:51, 18 ноября 2016
Строка 50:		Строка 50:
	=== Информационный граф ===		=== Информационный граф ===
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

			Перебор может быть эффективно параллелизован, в том числе с использованием графических ускорителей. Известны реализации, работающие напрямую с графовыми базами данных.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма ===		=== Свойства алгоритма ===

Teplov: /* Последовательная сложность алгоритма */

2016-11-18T16:50:44Z

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

← Предыдущая версия		Версия от 16:50, 18 ноября 2016
Строка 43:		Строка 43:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

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

	• полиномиальная, для фиксированного графа <math>H</math>		• полиномиальная, для фиксированного графа <math>H</math>

Teplov: /* Последовательная сложность алгоритма */

2016-11-18T16:50:27Z

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

← Предыдущая версия		Версия от 16:50, 18 ноября 2016
Строка 44:		Строка 44:

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

	• полиномиальная, для фиксированного графа <math>H</math>		• полиномиальная, для фиксированного графа <math>H</math>

	• линейная, для фиксированного графа <math>H</math> и планарного графа <math>G</math>.		• линейная, для фиксированного графа <math>H</math> и планарного графа <math>G</math>.

Teplov: /* Последовательная сложность алгоритма */

2016-11-18T16:50:12Z

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

← Предыдущая версия		Версия от 16:50, 18 ноября 2016
Строка 42:		Строка 42:

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

			Последовательная сложность алгоритма:
			• полиномиальная, для фиксированного графа <math>H</math>
			• линейная, для фиксированного графа <math>H</math> и планарного графа <math>G</math>.

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

Teplov: /* Схема реализации последовательного алгоритма */

2016-11-18T16:49:07Z

Схема реализации последовательного алгоритма

@@ Строка 31: / Строка 31: @@
 === Схема реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
 === Информационный граф ===