Диссертация (Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов)
Описание файла
Файл "Диссертация" внутри архива находится в папке "Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов". PDF-файл из архива "Модели, методы и программные средства анализа сходства орграфов и их применение при исследовании темпоральных орграфов", который расположен в категории "". Всё это находится в предмете "технические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата технических наук.
Просмотр PDF-файла онлайн
Текст из PDF
2ОглавлениеСПИСОК СОКРАЩЕНИЙ ............................................................................................................................... 5ВВЕДЕНИЕ ......................................................................................................................................................... 61. ОСНОВНЫЕ ПОДХОДЫ К ОПРЕДЕЛЕНИЮ СХОДСТВА ГРАФОВЫХ МОДЕЛЕЙ СИСТЕМ..............................................................................................................................................................................161.1.Задачи определения сходства графовых моделей систем и подходы к их решению .......................................
161.1.1. Подструктурный подход и его развитие .................................................................................................................. 161.1.2. Структурно-характеристический подход на основе инвариантов графов ............................................................... 201.2.Классификация задач определения максимальных общих частей и сходства двух орграфов ..........................
221.2.1. Классификация задач определения максимальных общих фрагментов двух орграфов ........................................ 221.2.2. Классификация задач определения сходства орграфов .......................................................................................... 251.3.Результаты вычислительных экспериментов определения сходства орграфов по П-подходу ..........................
261.3.1. Метод монотонных расширений частичных решений для определения MCS и MCF двух орграфов ............ 261.3.2. Результаты анализа П-подхода к определению сходства орграфов и его недостатки .................................... 271.4.Эффективность решения задач определения сходства на орлесах и ордеревьях ............................................. 281.4.1. Экспериментальные оценки вычислительной сложности алгоритма определения сходства двухордеревьев по методу монотонных расширений частичных решений ...................................................................... 281.4.2.
Экспериментальные оценки вычислительной сложности оригинального алгоритма определения сходствадвух ордеревьев .............................................................................................................................................................. 291.5.Задачи вычисления сходства ордеревьев и орлесов, имеющие прикладную значимость ................................ 301.5.1. Задача вычисления сходства пар ордеревьев и орлесов с весами на вершинах, решаемые поразработанному алгоритму ............................................................................................................................................
301.5.2. Задача поиска в базе орлесов, сходных с шаблоном ......................................................................................... 311.6.Основные результаты и выводы по главе ......................................................................................................... 352. МОДЕЛИ ОБОБЩЕННОЙ НАДСТРУКТУРНОЙ ХАРАКТЕРИЗАЦИИ ОРГРАФОВ .............372.1.Обобщенная модель орграфа в базисе полупутей и ее подмодели .................................................................. 382.1.1.
Порождающая граф-модель орграфа в базисе полупутей ................................................................................. 382.1.2. Подкласс порождающих граф-моделей орграфа в базисе полупутей .............................................................. 412.2.Стратификация порождающих моделей орграфа в базисе полупутей ..............................................................
452.3.Порождающие модели с выделенной вершиной и система методов решения задач определения сходстварасположения двух полупутей с уточнением результата............................................................................................... 462.3.1. Иерархические g-модели с выделенной вершиной в направленных орграфах .............................................. 462.3.2. Система стратификации g-моделей ..................................................................................................................... 482.4.Методы решения задач различения и сходства расположения полупутей с учетом их точного расположения ворграфе ..........................................................................................................................................................................
4932.4.1. Формализованная постановка задачи различения расположения полупутей заданного типа в орграфе ипример решения задачи ................................................................................................................................................. 492.4.2. Формализованная постановка задачи определения сходства расположения полупутей в орграфе на основеструктурных инвариантов ............................................................................................................................................... 502.4.3. Метод решения задачи определения сходства двух орграфов на основе сходства расположения полупутей...........................................................................................................................................................................................
512.5.Класс базовых моделей, построенных на основе g-моделей орграфов, и его основные подклассы ................. 522.5.1. Класс базовых моделей ......................................................................................................................................... 532.5.2. Примеры решения задач различения орграфов и различения расположения фрагментов в орграфе наоснове b-моделей ............................................................................................................................................................
542.5.3. Класс иерархических b-моделей .......................................................................................................................... 562.5.4. Система стратификации b-моделей ..................................................................................................................... 562.5.5. Метод количественного определения сходства орграфов с использование b-моделей ................................ 57⃗⃗ .............. 582.5.6.
Пример решения задачи определения сходства орграфов на основе b-моделей вида ⊆2.6.Основные результаты и выводы по главе ......................................................................................................... 603. АЛГОРИТМИЧЕСКИЕ ОСНОВЫ МЕТОДОВ НАДСТРУКТУРНОЙ ХАРАКТЕРАЗАЦИИДЛЯ АНАЛИЗА СХОДСТВА ОРГРАФОВ .................................................................................................623.1.Задача определения сходства орграфов и подструктурный подход к её решению .......................................... 623.2.Методы определения сходства орграфов на основе надграфов полупутей ......................................................
653.2.1. Классификация методов определения сходства двух орграфов ....................................................................... 653.2.2. Надграфы полупутей как основа нового метода определения сходства орграфов с точной характеризациейрасположения фрагментов в орграфе ........................................................................................................................... 653.2.3.
Главное свойство надграфов полупутей ............................................................................................................ 683.2.4. Связь изменений надграфов полупутей, порожденных изменениями анализируемых орграфов................ 733.3.Эффективные методы решения задач определения точного и частичного точного сходства орграфов большогопорядка ......................................................................................................................................................................... 753.3.1.
Сведение задачи распознавания изоморфизма надграфов к распознаванию изоморфизма их исходныхорграфов ........................................................................................................................................................................... 753.3.2. Алгоритм конструктивного распознавания исходного орграфа в надграфе полупутей .................................. 783.3.3.
Метод распознавания изоморфизма орграфов большого порядка .................................................................. 803.3.4. Метод распознавания изоморфного вложения для орграфов большого порядка.......................................... 813.3.5. Метод определения сходства двух орграфов большого порядка по П-подходу с использованием алгоритмасвертки надграфов полупутей ........................................................................................................................................ 823.4.Надструктурный подход к определению сходства орграфов ............................................................................ 843.4.1.
Страты надграфов полупутей и их применение для определения сходства орграфов ................................... 843.4.2. Пример анализа сходства и кластеризации орграфов по П- и Н-подходу ........................................................ 863.4.3. Экспериментальные оценки вычислительной сложности алгоритма построения надграфов полупутей дляордеревьев ....................................................................................................................................................................... 873.4.4.
