Участник:Midmedian/Алгоритм Федуччи-Маттеуса: различия между версиями

Версия 18:46, 22 октября 2019

Автор описания: И.А.Бабкин

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритмов

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

Алгоритм Федуччи-Маттеуса (FM-алгоритм)^[1] является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) за линейной время.

1.2 Математическое описание алгоритма

Пусть дан гиперграф [math]P=(C,N)[/math], где [math]C[/math] - это пронумерованный набор ячеек (вершин), соединённых пронумерованным набором сетей (гиперрёбер) [math]N[/math]. Гарантируется, что гиперграф состоит как минимум из двух ячеек и что каждая из ячеек содержится хотя бы в одной из сетей.

Количество ячеек в [math]i[/math]-ой сети обозначим как [math]n(i)[/math], а размер [math]j[/math]-ой ячейки (количество сетей, в которые входит ячейка) за [math]s(j)[/math].

Размер блока [math]B[/math] определим, как

[math]|B|=\sum\limits_{i=1}^{|N|} n(i)=\sum\limits_{i=1}^{|C|} s(i)[/math].

Задача заключается в разделении [math]P[/math] на непересекающиеся блоки [math]A[/math] и [math]B[/math] размерами [math]|A|[/math] и [math]|B|[/math] соответственно так, чтобы выполнялось условие

[math]\frac{|A|}{|A|+|B|} \cong r[/math],

где [math]r[/math] - коэффициент разделения ([math]0 \lt r \lt 1[/math]).

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 Литература

↑ Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions //19th Design Automation Conference. – IEEE, 1982. – С. 175-181.

[1] Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions //19th Design Automation Conference. – IEEE, 1982. – С. 175-181.

[1]

@@ Строка 5: / Строка 5: @@
 === Общее описание алгоритма ===
+'''Алгоритм Федуччи-Маттеуса (FM-алгоритм)'''<ref>Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions //19th Design Automation Conference. – IEEE, 1982. – С. 175-181.</ref> является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) за линейной время.
+=== Математическое описание алгоритма ===
+Пусть дан гиперграф <math>P=(C,N)</math>, где <math>C</math> - это пронумерованный набор ячеек (вершин), соединённых пронумерованным набором сетей (гиперрёбер) <math>N</math>. Гарантируется, что гиперграф состоит как минимум из двух ячеек и что каждая из ячеек содержится хотя бы в одной из сетей.
+''Количество ячеек'' в <math>i</math>-ой сети обозначим как <math>n(i)</math>, а ''размер'' <math>j</math>-ой ячейки (количество сетей, в которые входит ячейка) за <math>s(j)</math>.
+''Размер блока'' <math>B</math> определим, как
+:<math>|B|=\sum\limits_{i=1}^{|N|} n(i)=\sum\limits_{i=1}^{|C|} s(i)</math>.
-=== Математическое описание алгоритма ===
+Задача заключается в разделении <math>P</math> на непересекающиеся блоки <math>A</math> и <math>B</math> размерами <math>|A|</math> и <math>|B|</math> соответственно так, чтобы выполнялось условие
+:<math>\frac{|A|}{|A|+|B|} \cong r</math>,
+где <math>r</math> - ''коэффициент разделения'' (<math>0 < r < 1</math>).
 === Вычислительное ядро алгоритма ===