ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Актуальность темы работы
Цель работа
Решаемые задачи.
Научная новизна
Практическая полезность.
Методы исследований и достоверность результатов.
Реализация результатов.
Апробация работы.
Личный вклад диссертанта.
Публикации .
Содержание работы по главам
1. РАЗЛИЧЕНИЕ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ КАК НОВЫЙ УРОВЕНЬ ЗАДАЧ РАЗЛИЧЕНИЯ ГРАФОВ
1.1. Эквивалентность и толерантность графов и расположения их фрагментов.
1.2. Графы, фрагменты и помеченные фрагменты.
1.3. Группы автоморфизмов, индуцированные вершинной группой автоморфизмов Ат1 С.
1.3.1. Пример 1группы.
1.4. Задачи различения расположения фрагментов в графе.
1.4.1. Задачи различения расположения однотипных фрагментов
1.4.2. Задачи различения расположения произвольных фрагментов
1.4.3. Обсуждение постановок задач различения расположения фрагментов
1.4.4. Сведение задач различения графов к задачам различения расположения фрагментов.
1.4.5. Сводная таблица основных задач различения.
1.4.6. Инвариантное ядро задач различения 1 ИЯЗР1 в ССанализе
1.4.7. Инвариантное ядро задач различения 2 КЯЗР2 в ССанализе
1.4.8. и тэквивалентность.
1.4.9. Задачи различения тэквивалентности расположения фрагментов.
1.5. Подходы к решению задач из ИЯЗР1 и ИЯЗР2
1.5.1. Систематизация подходов к решению задач из ИЯЗР1
1.5.2. Сложность и методы решения задач из ИЯЗР1.
1.5.3. Систематизация подходов к решению задач из ИЯЗР2
Выводы и результаты по главе
2. ПЕРЕБОРНОГРУППОВОЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧ РАЗЛИЧЕНИЯ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ
2.1. Базовые задачи
2.1.1. Представление фрагментов в памяти компьютера
2.1.2. Построение порождающего множества группы автоморфизмов графа
2.1.3. Вид порождающего множества, используемый в данной работе
2.1.4. Представление порождающего множества, описанного выше.
2.1.5. Канонизация представления помеченного фрагмента на основе порождающего множества
группы автоморфизмов фрагмента.
2.1.6. Построение порождающего множества фиксаторастабилизатора подмножества вершин графа
2.2. Построение и исследование групп.
2.2.1. Представление порождающего множества Ьгруппы.
2.2.2. Поиск помеченного фрагмента в базе фрагментов
2.2.3. Построение порождающего множества группы.
2.2.4. Поиск орбит группы без построения порождающего множества группы
2.3. Решение задач из класса задач различения расположения фрагментов.
2.3.1. Решение задач различения расположения однотипных фрагментов
2.3.2. Решение задач различения расположения произвольных фрагментов
2.3.3. Построение и анализ матрицы пересечения орбит помеченных фрагментов
2.3.4. Пример характеризации расположения фрагментов в графе
2.4. Экспериментальная оценка вычислительной сложности алгоритмов.
2.5. Перспективы дальнейшего развития методов переборногруппового подхода
Выводы и результаты по главе
3. СТРУКТУРНОХАРАКТЕРИСТИЧЕСКИЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧ РАЗЛИЧЕНИЯ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ.
3.1. Использование структурных инвариантов
3.2. модели и 6модели графа для визуализации и решения задач различения расположения
фрагментов графа
3.3. Построение и исследование моделей и 6моделей
3.3.1. Способы задания базисов структурных дескрипторов.
3.3.2. Определение рбер и их весов.
3.3.3. Решение задач из класса задач различения расположения фрагментов на основе моделей.
3.3.4. Решение задач из класса задач различения расположения фрагментов на основе моделей.
3.3.5. Построение отношений эквивалентности и сходства графов на основе и модслей
3.4. Построение и исследование графов расположения цепей
3.4.1. модели с равными долями
3.4.2. Определение графа расположения цепей ГРЦ.
3.4.3. Эффективный метод построения ГРЦ.
3.4.4. Обозначения ГРЦ
3.4.5. Алгоритм построения ГРЦ
3.4.6. Доказательство корректности алгоритма
3.4.7. Некоторые свойства ГРЦ.
3.4.8. Пример построения ГРЦ
3.4.9. Исследование симметрии цепей исходного графа с использованием ГРЦ
3.4 Обобщение ГРЦ для анализа фрагментов других типов.
3.4 Результаты экспериментов
3.5. Усиление чувствительности структурных инвариантов
3.5.1. Итерационные методы усиления чувствительности
3.5.2. Итерационное уточнение разбиения множества вершин на классы эквивалентности по
модели .
3.5.3. Параметризация процедуры построения матрицы структурных инвариантов и проведение экспериментов по исследованию чувствительности инвариантов итерационного типа
3.6. Перспективы развития методов структурнохарактеристического подхода
Выводы и результаты по главе
4. ПОДСИСТЕМЫ АСНИ ДЛЯ ИССЛЕДОВАНИЯ АЛГОРИТМОВ СТРУКТУРНОГО СПЕКТРАЛЬНОГО АНАЛИЗА СИСТЕМ
4.1. История создания.
4.2. Общая архитектура АСНИ и место авторских подсистем в ней.
4.3. Программная реализация подсистем
4.4. Основные расширения АСНИ, реализованные автором
4.5. Учт симметрии расположения фрагментов для повышения эффективности решения задач
структурного спектрального анализа.
4.5.1. Развитие методологии монотонного расширения частичных решений.
4.5.2. Поиск всех канонических изоморфных вложений.
4.5.3. Максимальное изоморфное пересечение с учтом симметрии
4.5.4. Декомпозиция графа на неизоморфные фрагменты
4.5.5. Интерактивный поиск гамильтоновых цепей и циклов
4.6. Система проведения экспериментов и полигон исследования эффективности алгоритмов
4.6.1. Схема эксперимента
4.6.2. Сохранение результатов
4.6.3. Анализ результатов
4.6.4. Пример многоэтапного вычислительного эксперимента.
4.6.5. Вычислительные эксперименты, которые могут проводиться с использованием программных разработок автора.
4.7. Исследование эффективности подходов к решению задач различения расположения
фрагментов.
4.7.1. Используемые методики и тестовые данные.
4.7.2. Результаты вычислительных экспериментов.
4.7.3. Границы применимости
4.7.4. Выводы и рекомендации по применению
Выводы и результаты по главе
5. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ И ПРОГРАММНЫХ СРЕДСТВ ДЛЯ РЕШЕНИЯ ТЕОРЕТИЧЕСКИХ И ПРИКЛАДНЫХ ЗАДАЧ.
5.1. Результаты теоретических исследований.
5.1.1. Исследования, связанные с анализом симметрии графов.
5.1.2. Исследования итерационных процедур уточнения разбиения фрагментов на классы эквивалентности.
5.1.3. Исследование эквивалентных примарных фрагментов, полученных удалением неэквивалентных вершин и рбер
5.1.4. Исследования отношения эквивалентности графов с учтом расположения орбит фрагментов
5.2. Результаты применения в учебном процессе
Результаты по главе
ЗАКЛЮЧЕНИЕ
Выводы.
СПИСОК ЛИТЕРАТУРЫ
- Київ+380960830922