Методы и программные средства для различения расположения фрагментов графовых моделей систем

Методы и программные средства для различения расположения фрагментов графовых моделей систем

Автор: Незнанов, Алексей Андреевич

Шифр специальности: 05.13.11

Научная степень: Кандидатская

Год защиты: 2005

Место защиты: Москва

Количество страниц: 178 с. ил.

Артикул: 2851346

Автор: Незнанов, Алексей Андреевич

Стоимость: 250 руб.

ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Актуальность темы работы
Цель работа
Решаемые задачи.
Научная новизна
Практическая полезность.
Методы исследований и достоверность результатов.
Реализация результатов.
Апробация работы.
Личный вклад диссертанта.
Публикации .
Содержание работы по главам
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 и ИЯЗР
1.5.1. Систематизация подходов к решению задач из ИЯЗР
1.5.2. Сложность и методы решения задач из ИЯЗР1.
1.5.3. Систематизация подходов к решению задач из ИЯЗР
Выводы и результаты по главе
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. Результаты применения в учебном процессе
Результаты по главе
ЗАКЛЮЧЕНИЕ
Выводы.
СПИСОК ЛИТЕРАТУРЫ


Спектр отношений эквивалентности структур очень широк от отношения содержать одинаковое число элементов до отношения быть изоморфными. Отношение быть изоморфными является точной верхней гранью всех отношений эквивалентности структур, определяет наименьшие по мощности классы эквивалентности и хорошо изучено. Исследование рештки отношений эквивалентности структур актуальная проблема теории графов и смежных наук. Существует важный класс отношений, которые определяются в первую очередь не размерами графов, а тем, что и определяет структуру расположением фрагментов в них. Именно такие отношения эквивалентности определяют семейства графов. Они строятся на основе свойств группы автоморфизмов графа и характеристических инвариантов помеченных фрагментов графа. Отметим принципиальную разницу в исследовании проблем различения и установления сходства графов. Различные меры и коэффициенты структурного сходства порождают отношения толерантности 3 и также могут строиться на основе расположения фрагментов в графе. Потребность в исследовании отношений эквивалентности и толерантности структур в структурной информатике, химической структурной информатике, структурном распознавании образов, интеллектуальном анализе данных и других областях актуализировала развитие структурного спектрального анализа систем ССанализа Коховым В. Эта система покрыла не только большинство известных ранее характеристик, но и устранила многие белые пятна между ними. В свою очередь, на основе этой системы инвариантов можно навести порядок в многочисленных отношениях эквивалентного и толерантного расположения фрагментов графовых моделей структур и построить методологию систематического построения и исследования монотонно уточняемых стратифицируемых отношений между графами на основе структурных инвариантов, учитывающих расположение фрагментов. В основе этой методологии лежат задачи различения расположения произвольных фрагментов в графе, что акту авизирует развитие эффективных методов решения этих задач. Верхней гранью всех отношений эквивалентного расположения помеченных фрагментов в графе является отношение быть расположенными автоморфно, которое определяется группой автоморфизмов графа. Это отношение лежит в основе исследования симметрии расположения фрагментов, определяет минимальные классы неразличимости помеченных фрагментов и позволяет оценивать все остальные отношения эквивалентного расположения помеченных фрагментов. Определим терминологию, которая будет использоваться при описании отношений между ГМС и их фрагментами. Не определяемые здесь понятия теории графов можно найти в 8, , . В качестве ГМС будут рассматриваться обыкновенные графы, хотя на практике и при реализации программных средств часто будут использоваться графы с весами на вершинах иили рбрах. ГМС в виде ориентированных графов в данной работе не рассматриваются. Абстрактный тип произвольный граф, определнный с точностью до автоморфизма. Группу его вершинных автоморфизмов также с точностью до изоморфизма обозначим через . Граф назовм фрагментом графа , если изоморфно вкладывается вСв некотором смысле. В большинстве случаев будем считать, что смысл изоморфного вложения определн заранее. Помеченным графом называется граф, каждой вершине которого сопоставлен уникальный вес пометка, то есть каждая вершина которого имеет уникальный атрибут. Наличие пометок будем обозначать верхним индексом 1. Понятие пометок вершин графа отличается от понятия нумерации идентификации вершин с целью хранения структурной информации. Помеченным фрагментом типа I графа С назовм помеченный граф А пометками которого являются вершины графа 7, образующие вместе с некоторыми инцидентными им рбрами часть графа 7, изоморфную . Для различения абстрактного типа и типов реальных фрагментов графа будем называть тип фрагмента с заданной нумерацией вершин идентификационным типом. Специального обозначения вводить не будем, так как из контекста обычно ясно, введена нумерация вершин или нет. Не ограничивая общности, можно считать, что вершины нумеруются числами из натурального ряда 1,2, .

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.234, запросов: 244