Автореферат (1137128)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

На правах рукописиСтаричкова Юлия ВикторовнаИсследование методов и разработка программных средстванализа структурной сложности и симметрииграфовых моделей системСпециальность 05.13.11 – Математическое и программное обеспечениевычислительных машин, комплексов и компьютерных сетейАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата технических наукМосква, 20132Работа выполнена на кафедре анализа данных и искусственного интеллекта Национального исследовательского университета «Высшая школа экономики»Научный руководитель:Официальные оппоненты:Незнанов Алексей Андреевичкандидат технических наук, доцент, доцент кафедры анализа данных и искусственного интеллекта федерального государственного автономного образовательного учреждения высшего профессионального образования Национального исследовательского университета «Высшая школа экономики»Лаговский Борис Андреевичдоктор технических наук, доцент, профессор кафедры прикладной математики федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный техническийуниверситет радиотехники, электроники и автоматики» (МГТУ МИРЭА)Троицкий Виктор Валерьевичкандидат технических наук, доцент, начальник отдела разработки ЗАО «СУП Медиа»Ведущая организация:Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физикотехнический институт (государственный университет)»Защита состоится «17» апреля 2013 г.

в 14:00 на заседании диссертационного совета Д 212.131.05 при МГТУ МИРЭА по адресу:Москва, 119454, пр-т Вернадского, д. 78, Д412С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.Автореферат разослан «15» марта 2013 г.Отзывы на автореферат в двух экземплярах, заверенные печатью, просимнаправлять по адресу 119454, г. Москва, пр-т Вернадского,78, диссертационныйсовет Д 212.131.05Ученый секретарьдиссертационного советак.т.н, доцентЕ.Г. Андрианова3Общая характеристика работыАктуальность темы работыГрафовые модели систем (ГМС) – математические модели структур системи процессов. Разнообразные классы ГМС (от обыкновенных графов до взвешенных гиперграфов) применяются практически во всех областях науки ипрактики.

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

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

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

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

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

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

Разработанные алгоритмы реализуются в форме универсальных программных библиотек и прикладных программных средств.5. Исследуются алгоритмы и их реализации: доказывается их корректность, устанавливаются границы применимости с получением эмпирическихоценок вычислительной сложности, сравниваются с известными ранее.6. Реализованные программные средства применяются для получениятеоретических и прикладных результатов, внедряются в учебный процесс.Научные результаты и их новизна1.

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

В соответствии с предложенной классификацией ТГС4 разработан универсальный расширяемый программный комплекс генерации семейств ГМС,позволяющий, в том числе, безызбыточно порождать все ТГС4 до 30 вершинвключительно с различными вариантами полностью симметричных диаграмм.4. Для семейств ТГС4 получены результаты сравнительного анализа характеристик симметрии и структурной сложности с использованием индексов ивектор-индексов спектральной сложности, b-моделей в различных базисах, позволившие упорядочить семейства по различным мерам структурной сложности.Практическая полезность. Теоретические результаты работы и программные средства анализа структурной сложности ГМС позволят использовать более широкий спектр отношений эквивалентности структур, а также повысить эффективность в приложениях структурной информатики, химическойструктурной информатики, онтологического инжиниринга, структурного распознавания образов.Оригинальная классификация и методы генерации семейств ТГС4 позволят повысить качество систем управления и топологий вычислительных системc точки зрения сложности, надёжности и живучести.5Методы исследований и достоверность результатов.

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

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

Москва, 2009-2010), на тринадцатой национальнойконференции по искусственному интеллекту с международным участием КИИ2010 (г. Тверь, 2010), на семинарах ИППИ РАН и НИУ ВШЭ (г. Москва, 2012).Личный вклад диссертанта. Работа продолжает развитие методов прикладной теории графов и методов структурного спектрального анализа, разработанного В.А. Коховым. Личный вклад диссертанта состоит в:1) анализе современных моделей структурной сложности ГМС, описаниипредставительных базисов структурных дескрипторов для орграфов, созданииоригинальных программных средств анализа сложности орграфов в различныхбазисах структурных дескрипторов;2) выделении бесконечных и конечных семейств ТГС4, безызбыточно покрывающих все ТГС4 до 30 вершин, создании программных средств синтеза ивизуализации представителей семейств ТГС4;3) проведении научных исследований на основе объёмных вычислительных экспериментов, позволивших для рассматриваемых классов и семействГМС (ТГС4, орграфов, планарных графов) провести сравнительный анализ характеристик симметрии и структурной сложности в ранее не рассмотренныхбазисах.Публикации.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации