Временная верификация и оптимизация размещения компонентов предельных по быстродействию ЭВМ

• Автор: Ирбенек, Валентин Сергеевич
• Шифр специальности: 05.13.12
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 193 с. : ил

1.1. Алгоритмы решения зада чи о назна чениях.

1.1.1. Точный алгоритм решения задачи о назначениях на матрицах общего вида

1.1.2. Алгоритмы решения задачи о назначениях на матрицах специального вида

1.1.3. Приближенный алгоритм решения задачи о назначениях.

1.2. Применение алгоритмов решения задачи о назначениях в САПР электронной

АППАРАТУРЫ.
1.2.1. Назначение интерфейсных сигналов на периферийные элементы интегральных схем и на контакты рагьчов многослойных печатных плат

1.2.2. Проектирование проводных соединений при корпусировании интегральных схем.

1.3. Алгоритм раскраски ребер мультиграфа.

1.4. Применение алгоритма раскраски ребер мультиграфа в САПР электронной аппаратуры

Заключение.
СПИСОК ЛИТЕРА ТУРЫ
ГЛАВА 2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ РАЗБИЕНИЯ И РАЗМЕЩЕНИЯ
Введение


В работе 7 предложен алгоритм, позволяющий за время 0п сделать итерацию по заданному вектору Л и набору основ с дефектом не равным нулю найти новый вектор и набор основ, имеющий меньший дефект. Взяв в качестве исходных нулевой вектор А и некоторый набор основ для него, задача решается последовательными итерациями, число которых не может превышать п. Итерация алгоритма заключается в следующем. Пусть для некоторого вектора А мы имеем набор основ с1,с2у2,. Отметим некоторый свободный столбец. Пусть его номер равен 5,. Получим, что для некоторого , Ад, сй А , то есть элемент стал А минимальным. Назовем его альтернативной основой и отметим столбец с номером л2 у, содержащий основу этой строки имеем теперь два отмеченных столбца. Теперь будем строить новый набор основ. Заметим, что в каждой строке имеется не более одной альтернативной основы. Назовем заменой основы в строке следующую операцию альтернативная основа в этой строке объявляется основой, а старая основа перестает быть основой. Произведем замену основы в строке, в которой находится последняя альтернативная основа. При этом в последнем отмеченном столбце количество основ уменьшится на 1. В столбце, где появилась новая основа, возьмем старую основу и произведем замену основ в соответствующей строке и так далее, пока не появится основа в столбце с номером 5,. Тем самым мы получили нужный нам вектор А и набор основ для него с дефектом, равным т . Легко видеть, что каждая итерация описанного алгоритма требует Си2 действий, не считая действий, идущих на вычисление 5 на каждом шаге итерации. Поскольку количество итераций не превышает п, нас интересует только время вычисления 6.