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

Введение к работе

Актуальность темы работы

Графовые модели систем (ГМС) - математические модели структур систем и процессов. Разнообразные классы ГМС (от обыкновенных графов до взвешенных гиперграфов) применяются практически во всех областях науки и практики. Совершенствование инструментальных средств (компьютерной техники) привело к бурному развитию методов структурного анализа систем и позволило сделать качественный скачок и привело к выделению прикладной теории графов. Хотя методы прикладной теории графов зародились и играют свою особую роль в информационных технологиях (теории связи и кодирования, теории трансляции, оптимизации программ, организации сложных структур данных, построении высокопроизводительных вычислительных комплексов, визуализации данных, построении человеко-машинных интерфейсов и др.), постоянно повышается их значимость в других областях.

Одной из базовых задач является задача анализа структурной сложности ГМС. Структурная сложность - очень емкое и многоаспектное понятие, которое лежит в основе системной сложности и напрямую используется при решении задач различения и анализа сходства ГМС, оценки результатов синтеза структур, визуализации структурной информации. Примерами могут служить задачи в областях полнотекстового поиска (сравнение структурных моделей текста), онтологического инжиниринга (запросы к онтологиям), логистики (интегральная оценка транспортных сетей), анализа социальных сетей (сравнение сообществ), хим- и биоинформатики (QSAR-анализ), и др. Другим типом задач являются задачи синтеза структуры системы (телекоммуникационной сети, системы управления и т.п.), обладающей заданными свойствами: структурной сложностью, надёжностью, симметрией и др.

Объектом работы являются ГМС в виде транзитивных графов степени 4 и ориентированных графов. Предметом - их характеристики структурной сложности (индексы, вектор-индексы, ^-модели) и симметрии (от порядка группы автоморфизмов до структуры стационарных подгрупп). Работа продолжает исследования в области прикладной теории графов, проводимые В.А. Коховым, А.А. Незнановым. В ней рассматриваются вопросы создания программных средств, использующих взаимосвязь структурной сложности, сходства и симметрии для графовых моделей различных классов.

Цель работы. Цель диссертационной работы - исследование методов анализа структурной сложности и симметрии ГМС, а также создание программных средств, решающих базовые задачи анализа структурной сложности и задачи синтеза ГМС. Предполагается, что это повысит эффективность компьютерных методов анализа сходства и синтеза ГМС и позволит шире использовать их в научных и прикладных исследованиях.

Решаемые задачи. Для достижения поставленной цели в работе решаются следующие задачи.

1. Даётся обзор и анализируются классические модели структурной сложности ГМС, в частности, оригинальный представительный класс моделей, предложенный В.А. Коховым и реализованный в виде программных средств для класса обыкновенных графов С.В. Ткаченко и А.А. Незнановым.

1. Производится дополнительная классификация и синтез семейств транзитивных графов степени 4, исследуется их характеристики структурной сложности и визуализация диаграмм, разрабатываются алгоритмы генерации бесконечных семейств транзитивных графов.

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

3. Разработанные алгоритмы реализуются в форме универсальных программных библиотек и прикладных программных средств.

4. Исследуются алгоритмы и их реализации: доказывается их корректность, устанавливаются границы применимости с получением эмпирических оценок вычислительной сложности, сравниваются с известными ранее.

5. Реализованные программные средства применяются для получения теоретических и прикладных результатов, внедряются в учебный процесс.

Научные результаты и их новизна

5. 1. Для обыкновенных, ориентированных, планарных ГМС получены новые результаты анализа структурной сложности орграфов: предложен и реализован вариант построения индексов, вектор-индексов и структурных моделей спектральной сложности (^-моделей) в ранее недостаточно исследованных базисах ориентированных цепных фрагментов, собраны данные о точности решения задач различения и анализа сходства ГМС, представленных орграфами.

   2. С целью облегчения синтеза регулярных топологий предложена расширенная классификация бесконечных и конечных семейств связных транзитивных графов степени 4 (ТГС4) по характеристикам симметрии, структурной сложности и вариантам симметричной прорисовки диаграмм.

   3. В соответствии с предложенной классификацией ТГС4 разработан универсальный расширяемый программный комплекс генерации семейств ГМС, позволяющий, в том числе, безызбыточно порождать все ТГС4 до 30 вершин включительно с различными вариантами полностью симметричных диаграмм.

   4. Для семейств ТГС4 получены результаты сравнительного анализа характеристик симметрии и структурной сложности с использованием индексов и вектор-индексов спектральной сложности, ^-моделей в различных базисах, позволившие упорядочить семейства по различным мерам структурной сложности.

   Практическая полезность. Теоретические результаты работы и программные средства анализа структурной сложности ГМС позволят использовать более широкий спектр отношений эквивалентности структур, а также повысить эффективность в приложениях структурной информатики, химической структурной информатики, онтологического инжиниринга, структурного распознавания образов.

   Оригинальная классификация и методы генерации семейств ТГС4 позволят повысить качество систем управления и топологий вычислительных систем c точки зрения сложности, надёжности и живучести.

   Методы исследований и достоверность результатов. Задачи исследования решаются в работе с помощью методов прикладной теории графов, теории групп, теории вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др. В работе существенно использованы результаты, полученные В.А. Коховым, С.В. Ткаченко, А.А. Незнановым, И.А. Фараджевым, B. D. McKay, G. F. Royle, E. Luks. Основой получения новых научных результатов являются объёмные вычислительные эксперименты с использованием авторских и сторонних программных средств. При малой сложности исходных данных результаты вычислительных экспериментов на тестовых наборах исходных данных совпадают с известными результатами. При обработке сложных исходных данных сравнивались результаты, полученные различными методами решения одной и той же задачи.

   Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 13-й и 14-й международных научно-технических конференциях студентов и аспирантов «радиоэлектроника, электротехника и энергетика» (г. Москва, 2008-2009), на международных форумах информатизации МФИ-2009, МФИ-2010 (международные конференции «Информационные средства и технологии», г. Москва, 2009-2010), на тринадцатой национальной конференции по искусственному интеллекту с международным участием КИИ- 2010 (г. Тверь, 2010), на семинарах ИППИ РАН и НИУ ВШЭ (г. Москва, 2012).

   Личный вклад диссертанта. Работа продолжает развитие методов прикладной теории графов и методов структурного спектрального анализа, разработанного В.А. Коховым. Личный вклад диссертанта состоит в:

   5. 4. 1. анализе современных моделей структурной сложности ГМС, описании представительных базисов структурных дескрипторов для орграфов, создании оригинальных программных средств анализа сложности орграфов в различных базисах структурных дескрипторов;

         2. выделении бесконечных и конечных семейств ТГС4, безызбыточно покрывающих все ТГС4 до 30 вершин, создании программных средств синтеза и визуализации представителей семейств ТГС4;

         3. проведении научных исследований на основе объёмных вычислительных экспериментов, позволивших для рассматриваемых классов и семейств ГМС (ТГС4, орграфов, планарных графов) провести сравнительный анализ характеристик симметрии и структурной сложности в ранее не рассмотренных базисах.

         Публикации. Основные результаты, полученные в процессе выполнения диссертационной работы, опубликованы в 3 статьях (из них - 2 из списка ВАК РФ), в трудах и тезисах докладов конференций, учебно-методических пособиях.

         Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы (76 наименований) и 3 приложений. Она содержит 127 страницу в основной части и 309 страниц приложений.

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

         Разработка и исследование методов и средств анализа информационных объектов на основе модели Система Взаимодействующих ТаблицСеменов, Александр Сергеевич

         Исследование и разработка моделей, методов и программных средств темпорального вывода в динамических интегрированных экспертных системахМозгачев, Алексей Васильевич

         Разработка и исследование программных методов и средств защиты систем удаленного мониторингаСильнов, Дмитрий Сергеевич

         

         Разработка и исследование стохастических методов и средств защиты программных систем ответственного назначенияИванов Михаил Александрович

         Разработка и исследование методов и средств построения адаптивных диагностических системБрыль, Владимир Николаевич

         Разработка и исследование методов и средств оценки качества баз знаний экспертных систем и технологий их созданияСимакова, Ольга Николаевна

         Исследование и разработка методов и программных средств для информационно-управляющих систем верхнего блочного уровняПолетыкин Алексей Григорьевич

         

         Исследование и разработка методов и программных средств временного (темпорального) вывода в интеллектуальных системах поддержки принятия решенийКуриленко Иван Евгеньевич

         Исследование методов и разработка алгоритмов и программных средств планирования обслуживания терминалов распределенных компьютерных системВоробьева, Ирина Александровна

         

         Исследование и разработка методов и средств создания эталонов для оценки защищённости корпоративных программных системПетров Сергей Андреевич