Введение
1. Определение объекта исследования и постановка задачи 12
1.1. Анализ задачи разрезания и выбор математических моделей 12
1.2. Формальная постановка задачи разрезания 16
1.3. Задача выбора структур данных для реализации алгоритмов декомпозиции схем 17
1.4. Анализ методов решения задачи разрезания 19
Выводы 23
2. Проблема выбора структур данных 25
2.1. Анализ структур данных и операций над ними 25
2.2. Исследование операций над линейными структурами данных 35
2.3. Исследование операций над древовидными и сетевыми структурами .45
2.4. Классификация базовых структур данных и матрица сложностей базовых операций 60
2.5. Формальная постановка и методика решения задачи выбора структур данных 64
2.6. Локально-оптимальный алгоритм выбора структур данных 73
2.7. Выбор структур данных для последовательного алгоритма разрезания гиперграфа 77
Выводы 86
3. Алгоритмы декомпозиции схем по методу двоичной свертки 88
3.1. Математическая модель процесса композиции и особенности алгоритмов свертки 88
3.2. Алгоритмы свертки без учета связности 92
3.3. Алгоритмы свертки с учетом связности 97
3.4. Сравнительный анализ полученных результатов 101
3.5. Выбор структур данных 103
Выводы 112
4. Алгоритм дихотомического разрезания гиперграфа по методу ветвей и границ 114
4.1. Математическая модель процесса дихотомического разрезания гиперграфа по методу ветвей и границ 114
4.2. Доказательство применимости метода ветвей и границ для декомпозиции схем 117
4.3. Схемы реализации метода ветвей и границ 121
4.4. Способы формирования дерева решений 125
4.5. Способы кодирования вершин дерева решений и оценка сверху их емкостной сложности 128
4.6. Кодирование огибающей цепи 132
4.7. Алгоритм дихотомического разрезания гиперграфа по методу ветвей и границ 137
4.8. Выбор структур данных и определение вычислительной сложности
алгоритма 141
Выводы 151
5. Экспериментальная часть 153
5.1. Система автоматизированной декомпозиции схем 153
5.2. Экспериментальное исследование вычислительной сложности алгоритмов двоичной свертки... 154
5.3. Исследование возможности применения алгоритма дихотомического разрезания гиперграфа по методу ветвей и границ и двоичной свертки для декомпозиции схем 157
5.4. Экспериментальные исследования качественных характеристик алгоритмов 160
Выводы 163
Заключение 165
Список литературы
