Informatics

Метод быстрого вычисления линейного функционала для задачи размещения сверхбольших интегральных схем

В. Э. Погосян

Ереванский государственный университет

Аннотация: В алгоритмах последовательного улучшения размещения элементов сверхбольших интегральных схем часто необходимо вычислить значение функционала в зависимости от расположения одного элемента, считая остальные элементы неподвижными. В частности, требуется найти оптимальное место для данного элемента. Для решения этой задачи в статье предлагается эффективный алгоритм, который имеет сложность $O(n \log n)$, где $n$ есть количество цепей данного элемента.

Ключевые слова: Сверхбольшие интегральные схемы, эффективный алгоритм.

УДК: 681.3.068

Поступила в редакцию: 02.12.2002
Принята в печать: 10.03.2003