Графы в задачах анализа и синтеза структур сложных систем (Овчинников В.А.) [2014, Монография, пособие, PDF]

1. Элементы теории графов
1.1. Общее определение графа
1.2. Ультраграф
1.3. Гиперграф
1.4. Ориентированный граф
1.5. Неориентированный граф
1.6. Смешанные графы, графы с кратными ребрами и весами
1.7. Некоторые особые графы, вершины и ребра. Части графов
1.8. Особые множества вершин и ребер графов
2. Синтез и анализ структур сложных систем
2.1. Общая характеристика задач синтеза и анализа структур сложных систем
2.2. Задачи позиционирования
2.3. Коммутационные задачи
2.4. Задачи декомпозиции структур и композиции их элементов
2.5. Задачи установления идентичности структур
2.6. Задачи выделения подмножества компонентов, обладающих заданными свойствами
2.7. Задачи анализа и преобразования алгоритмов
2.8. Содержательная постановка комбинаторно-оптимизационной задачи
3. Математические модели объектов и задач структурного синтеза и анализа
3.1. Требования к математическим моделям объектов проектирования
3.2. Информация о структуре системы и ее монтажной области
3.3. Модель схемы в виде ультраграфа
3.4. Представление схем ориентированным графом
3.5. Модель схемы в виде гиперграфа
3.6. Представление схем неориентированным и смешанным графами
3.7. Модели монтажного пространства
3.8. Формальная постановка задачи позиционирования
3.9. Модели коммутационных задач
3.10. Модели задач декомпозиции структур
3.11. Формальная постановка задачи установления идентичности структур
3.12. Модели задач выделения подмножеств особых компонентов
4. Операции над ультра- и гиперграфами
4.1. Проектные процедуры и операции над графами
4.2. Добавление вершин и ребер
4.3. Удаление вершин и ребер
4.4. Стягивание ребер и подразбиение ребра
4.5. Удаление вершины из образов и прообразов множества ребер и ребра из образов и прообразов множества вершин
4.6. Формирование части графа, свертка подмножества вершин и декомпозиция вершины
4.7. Дополнение, объединение и пересечение графов и их частей
5. Модели алгоритма и структурных конструкций
5.1. Информационно-логическая модель алгоритма
5.2. Модели структурных конструкций, структурного алгоритма и их свойства
5.3. Автоматизация анализа вычислительной и емкостной сложности алгоритма
6. Структуры данных и их модели
6.1. Базовые и производные структуры данных
6.2. Двухуровневые структуры данных
6.3. Комбинированные структуры данных
6.4. Отношения на элементах записи множеств и их модели
6.5. Модели одноуровневых структур данных
6.6. Модели двухуровневых и комбинированных структур данных
6.7. Синтез комбинированных структур данных для представления графов
6.8. Методика формального синтеза комбинированных структур данных
7. Описание алгоритмов операциями теории множеств, математической логики и теории графов
7.1. Проектные операции и процедуры решения задач структурного синтеза
7.2. Реализация операций теории множеств структурными конструкциями в элементарном базисе алгоритмов
7.3. Операции над упорядоченными множествами
7.4. Оценка эффективности использования операций над упорядоченными множествами
7.5. Язык описания алгоритмов операциями теории множеств и математической логики
7.6. Синтаксис и семантика языка формального описания алгоритмов с использованием операций над графами
7.7. Применение операций над графами в алгоритмах схемно-топологического проектирования
8. Способы снижения вычислительной сложности алгоритмов на графах и множествах
8.1. Основные способы снижения вычислительной сложности алгоритмов
8.2. Снижение вычислительной сложности алгоритмов за счет корректности формальной постановки задачи, выбора метода ее решения и посредством снижения размерности входа
8.3. Преобразования алгоритмов, вытекающие из принципа формирования множеств, представляющих решение
8.4. Преобразования, определяемые способами задания множеств и графов
8.5. Снижение вычислительной сложности, связанное со свойствами и характеристиками графов
8.6. Преобразования, использующие свойства множеств, предикатов и операций над ними
8.7. Формализация оптимизирующих преобразований алгоритмов
8.8. Пример использования оптимизирующих преобразований при разработке алгоритма