4511
правок
Кластеризация на основе эффективности: различия между версиями
Перейти к навигации
Перейти к поиску
м
Кластеризация на основе эффективности (посмотреть исходный код)
Версия от 20:33, 1 апреля 2016
, 1 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
'''Определение 1.''' Кластеризация сети G = (V, E) представляет собой тройку <math>(H, \phi,\Sigma) \;</math>, где | '''Определение 1.''' '''Кластеризация''' сети G = (V, E) представляет собой тройку <math>(H, \phi,\Sigma) \;</math>, где | ||
1. H = (V', E') – ориентированный ациклический граф; | 1. H = (V', E') – ориентированный ациклический граф; | ||
| Строка 32: | Строка 32: | ||
Определение 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией w: V | '''Определение''' 2. Пусть дана комбинационная сеть G = (V, E) с весовой функцией <math>w: V \to R^+ \;</math>, весовой емкостью M и функцией задержки <math>\delta: V \to R^+ \;</math>. Мы говорим, что кластеризация <math>\Gamma = (H, \phi, \Sigma ) \;</math> является '''допустимой''', если для каждого кластера <math>C \in \Sigma \;</math> значение W(C) не превышает M. '''Задача кластеризации схемы''' заключается в вычислении допустимой кластеризации <math>\Gamma \;</math> сети G, такой, что задержка <math>\Gamma \;</math> минимальна среди всех допустимых кластеризаций G. | ||
В одной из первых работ по этой теме Лоулер и коллеги [ ] предложили алгоритм с полиномиальным временем исполнения для задачи кластеризации схемы в специальном случае, когда все вентильные задержки равны нулю (т.е. | |||
В одной из первых работ по этой теме Лоулер и коллеги [2] предложили алгоритм с полиномиальным временем исполнения для задачи кластеризации схемы в специальном случае, когда все вентильные задержки равны нулю (т.е. <math>\delta (v) = 0 \;</math> для всех v). | |||
== Основные результаты == | == Основные результаты == | ||