Исследование методов и разработка программных средств анализа структурной сложности и симметрии графовых моделей систем

• Автор: Старичкова, Юлия Викторовна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 436 с. : ил. + Прил. (с. 129-436: ил.)

Содержание
ВВЕДЕНИЕ
Объект и предмет работы
Актуальность
Цель работы
Решаемые задачи
Научная новизна
Практическая полезность
Методы исследований и достоверность результатов
Апробация работы
Личный вклад диссертанта
Публикации
Содержание работы по главам
1. СТРУКТУРЫ СИСТЕМ, ИХ СЛОЖНОСТЬ И СИММЕТРИЯ
1.1. Предмет исследования
1.2. Значимость понятия «структурная сложность»
1.3. Основные определения, связанные с понятием системы
1.4. История развития представлений о сложности систем
1.5. Модели структур систем
1.5.1. Фрагменты и помеченные фрагменты графовых моделей
1.5.2. Смысл вложения фрагмента в граф
1.6. Основные подходы к определению сложности систем
1.6.1. Сложность по Шеннону
1.6.2. Сложность по Колмогорову
1.7. Структурная сложность
1.7.1. Подход на основе вектор-индексов спектральной сложности
1.7.2. Теоретико-информационный подход к определению сложности через симметрию
1.7.3. Объединение различных подходов
1.7.4. Топологические индексы
1.8. Структурные модели структурной сложности и система вМЭ
1.8.1. Исторический экскурс
1.8.2. §-модели (базовые модели системы вМв)
1.8.3. Стратификация g-мoдeлeй
1.8.4. Ь-модели
1.8.5. Обозначения Ь-моделей
1.8.6. Пример построения Ь-модели
1.8.7. g(b)s-мoдeли
1.9. Различение графовых моделей
1.9.1. Постановки задач
1.10. Структурное сходство
1. ЮЛ.Подструктурный подход к определению структурного сходства
1.10.2.Сходство как близость мер структурной сложности
1.11. Визуализация структур
1.11.1. Понятие прорисовки графовой модели
1.11.2.Классификация методов прорисовки
1.11.3. Изобразительные соглашения при прорисовке
1.11.4. Прорисовки на плоскости
1.11.5. Прорисовка транзитивных графов
1.12. Выводы и результаты по главе

2. СТРУКТУРНАЯ СЛОЖНОСТЬ ОРГРАФОВ
2.1. Основные понятия, связанные со спецификой исследования фрагментов орграфов
2.2. Спектральная сложность
2.2.1. Индексы и вектор-индексы структурной спектральной сложности
2.2.2. Базисы путей и контуров
2.2.3. Алгоритм вычисления индексов ССС в базисе путей
2.2.4. Экспериментальная оценка временной сложности работы алгоритмов вычисления индексов
ССС в различных базисах СД
2.2.5. Базис ориентированных цепных фрагментов
2.2.6. Индексы и вектор-индексы структурной спектральной сложности в базисе ориентированных цепных фрагментов
2.3. i-модели орграфов в базисе ориентированных цепных фрагментов
2.3.1. Алгоритмы построения b-моделей
2.3.2. Используемое в реализации пространство параметризации
2.3.3. Пример
2.3.4. Зависимость вычислительной сложности от длины базиса
2.3.5. Анализ сходства b-моделей
2.4. Результаты вычислительных экспериментов
2.5. Выводы и результаты по главе
3. КЛАССИФИКАЦИЯ СЕМЕЙСТВ ТРАНЗИТИВНЫХ ГРАФОВ
3.1. Значимость транзитивных графов
3.2. Постановка задачи
3.3. История развития исследования ТГС4
3.4. Необходимые определения
3.5. Подход к классификации ТГС4
3.5.1. Описание порождаемых семейств
3.5.2. Система классификации семейств ТГС4
3.6. Корректность и полнота классификации
3.7. Лес семейств ТГС4
3.8. Исследование характеристик симметрии семейств ТГС4
3.9. Исследование сложности семейств ТГС4
3.10. Классификация ПТГ с учетов характеристик симметрии
3.10.1. Анализ выделенных семейств
3.11. Сложность планарных транзитивных графов
3.11.1.Постановка задачи
3.11.2. Классификация планарных транзитивных графов по сходству расположения орбит цепей
3.12. Выводы и результаты по главе
4. ПРОГРАММНЫЕ РАЗРАБОТКИ
4.1. Общие сведения о программных разработках
4.2. Автоматизированная система научных исследований «Graph Model Workshop»
4.3. Программный комплекс «Сложность орграфов в цепных базисах»
4.3.1. Функциональность, объемные характеристики и архитектура
4.3.2. Тестирование комплекса
4.3.3. Проектные решения и вычислительная сложность
4.3.4. Интерфейс с пользователем
4.3.5. Пример сценария использования
4.3.6. Внедрение
4.4. Программный комплекс «TransGen»
4.4.1. Функциональность, объемные характеристики и архитектура
4.4.2. Проектные решения и вычислительная сложность

4.4.3. Расширяемость системы шаблонов
4.4.4. Интерфейс с пользователем и проведение вычислительных экспериментов
4.4.5. Внедрение
4.5. Выводы и результаты по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ 1. СПИСОК СОКРАЩЕНИЙ
ПРИЛОЖЕНИЕ 2. РАЗЛИЧЕНИЕ ОРГРАФОВ ПО МОДЕЛЯМ СТРУКТУРНОЙ СЛОЖНОСТИ
4.6. Индексы сложности орграфов
4.7. Индексы сложности бесконтурных орграфов
4.8. Индексы сложности планарных орграфов
4.9. Индексы сложности планарных бесконтурных орграфов
4.10. Модели сложности для классов орграфов в базисе путей различной длины
4.10.1.Модели сложности для классов орграфов в базисе путей длины
4.10.2.Модели сложности для классов орграфов в базисе путей длины
4.10.3.Модели сложности для классов орграфов в базисе путей длины
4.11. Модели сложности для классов орграфов в базисе ОЦФ различной длины
4.11.1. Модели сложности для классов орграфов в базисе ОЦФ длины
4.11.2.Модели сложности для классов орграфов в базисе ОЦФ длины
ПРИЛОЖЕНИЕ 3. СЕМЕЙСТВА ТРАНЗИТИВНЫХ ГРАФОВ, ПОРОЖДАЕМЫЕ
ГЕНЕРАТОРОМ
4.12. Каталог бесконечных семейств ТГС4
4.13. Каталог конечных семейств ТГС4
4.14. Дерево семейств ТГС4
4.15. Интегральные характеристики семейств

(идентификационные типы)
Таблица 1.1 сопоставляет базис В с вершинами левой и правой доли.
Таблица 1.1. Канонические представлении помеченных фрагментов
I 1 2 3 4 5
№ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
/0- 1 2 3 4 1 1 2 2 3 1 1 1 1 2 2 2 3 1 2 1 1 1 1 1 1 2 3 1 1
2 4 3 4 4 2 3 3 4 3 4 4 4 2 3 2 3 2 3 3 4 3 4 2 3
4 2 4 2 4 1 3 2 4 4 3 4 4 2 4 2 1 2 3 4
4 2 3 4 2 3 4 1 4 2
Следующий рисунок и таблица представляют 6-модель графа <7 в базисе В и
её матрицу.