Рассмотрены вопросы алгоритмизации комбинаторно-оптимизационных задач структурного синтеза на графах. Большое внимание уделено формализации таких задач и методам их решения, основанным на идее отсечения, ветвей и границ, поиска в глубину, в ширину, двоичной свертки. Описаны основные этапы построения алгоритмов и подходы к оценке их точности и сложности; точные и приближенные алгоритмы решения таких задач, как построение минимального остовного дерева, замкнутого цикла минимальной длины, кратчайшего маршрута, разрезания гиперграфа схемы и др. Выполнена оценка вычислительной и емкостной сложности большинства алгоритмов. Содержание учебника соответствует курсу лекций, который автор читает в МГТУ им. Н.Э.Баумана. Для студентов вузов, обучающихся по специальностям, связанным с информатикой. Будет полезна инженерам, работающим в данной области.

Введение
1. Постановка и формализация
комбинаторно-оптимизационных
задач
1.1. Комбинаторно-оптимизационные задачи
структурного синтеза и их постановка
1.2. Этапы полного решения прикладной
задачи структурного синтеза
1.3. Элементы теории графов
Контрольные вопросы и задания
2. Математические модели объектов
проектирования и структуры
их представления
2.1. Требования к математическим моделям
объектов проектирования
2.2. Представление объектов проектирования
неориентированным графом и гиперграфом
2.3. Представление схем ориентированным
графом
2.4. Математические модели монтажного
пространства
2.5. Базовые структуры данных
2.6. Анализ структур данных, используемых
для представления графов Контрольные вопросы и
задания
3. Методы решения
комбинаторно-оптимизационных задач
3.1. Стратегии декомпозиции множества
решений и дерево поиска
3.2. Методы поиска решения, использующие
идею отсечения
3.3. Метод ветвей и границ
3.4. Метод итерационного улучшения
3.5. Метод параллельно-последовательной
свертки
Контрольные вопросы и задания
4. Построение и анализ алгоритмов
4.1. Точность и сложность алгоритма
4.2. Основные этапы построения алгоритма
4.3. Описание алгоритмов операциями теории
множеств, графов и математической логики
4.4. Методика анализа вычислительной
сложности алгоритмов
4.5. Особенности реализации операций над
множествами и отношений
между ними
Контрольные вопросы и задания
5. Алгоритмы декомпозиции схем ЭВМ
5.1. Постановка задачи схемной компоновки
5.2. Последовательный алгоритм разрезания
гиперграфа схемы
5.3. Алгоритм параллельного разрезания
гиперграфа схемы
5.4. Итерационный алгоритм улучшения
компоновки при задании схемы гиперграфом
5.5. Алгоритм дихотомического разрезания
гиперграфа схемы по
методу ветвей и границ
Контрольные вопросы и задания
6. Задачи идентификации объектов и поиска
идентичных частей
6.1. Математическая модель задачи
идентификации схем
6.2. Исследование алгоритмических моделей
решения задачи идентификации
6.3. Алгоритм решения задачи идентификации
6.4. Математическая модель задачи покрытия
схемы заданным набором модулей
6.5. Исследование алгоритмических моделей
задачи изоморфного наложения
6.6. Алгоритм решения задачи покрытия
Контрольные вопросы и задания
7. Алгоритмы свертки
7.1. Задача свертки и ее формальная
постановка
7.2. Неуравновешенная двоичная свертка
7.3. Уравновешенная двоичная свертка
7.4. Выделение минимальных массивов
гиперграфа
Контрольные вопросы и задания
8. Алгоритмы размещения
8.1. Постановка задачи размещения
8.2. Последовательный алгоритм размещения
8.3. Итерационный алгоритм размещения
Контрольные вопросы и задания
9. Алгоритмы решения задачи коммутации
9.1. Алгоритм Прима
9.2. Алгоритм Дейкстры
Контрольные вопросы и задания
10. Дополнительные приемы снижения
вычислительной сложности
алгоритмов
ЮЛ. Упорядочивание множеств
10.2. Представление множеств
характеристическими векторами
10.3. Использование отображения множества
вершин гиперграфа в
само себя
Контрольные вопросы и задания
Приложения
Список литературы
Предметный указатель