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

Материал из Алговики
Версия от 18:46, 22 октября 2019; Midmedian (обсуждение | вклад) (Добавлено общее описание алгоритма и кусочек математического описания.)
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

Размер блока B определим, как

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

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

\frac{|A|}{|A|+|B|} \cong r,

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

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. Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions //19th Design Automation Conference. – IEEE, 1982. – С. 175-181.