Введение к работе
Актуальность темы исследований.
Анализ научных работ в области АСНИ и информационно-поисковых систем (ИПС) структурной информации (интеллектуальный weft-поиск текстовых документов, разработка онтологии предметных областей, анализ схем программ, структурное распознавание образов, органическая химия, теория цепей, математическая биология, генетика, социология, экология и др.), за последние 30 лет показывает, что наибольшее их число было связано с вопросами точного структурного и подструктурного поиска.
Из анализа научных работ следует, что при создании ИПС и АСНИ, связанных с анализом структур систем, используют три основных подхода к поиску:
методы поиска на основе точной идентификации;
методы поиска на основе частичной идентификации;
методы поиска на основе наиболее сходной (наилучшей) идентификации. Три выделенных подхода определяют три разновидности сходства структур.
ГТ**пня« rrtvnna методов Tnc6vex наличия эффективных алгоритмов ^аспознаванн? изоморфизма (идентификации, канонизации) ГМС и находит применение при разработке ИПС, связанных со структурным поиском.
Вторая группа методов требует наличия эффективных атгоритмов распознавания изоморфного вложения одной граф-модели систем (ГМС) в другую, и находит применение в наиболее часто разрабатываемых ИПС, связанных с подструктурным поиском, и использующих не только структурную, но, и числовую, и текстовую информацию.
Третья, наиболее перспективная группа методов, ориентирована на разработку ИПС, АСНИ, СИИ, СПР, в которых ищутся самые близкие по сходству ГМС с учетом дополнительной числовой и текстовой информации. Эти методы требуют эффективных атгоритмов определения сходства ГМС, выраженного в количественном виде, для поиска наиближайших соседей по сходству с ГМС, которая анализируется. К таким алгоритмам относятся алгоритмы определения максимального изоморфного пересечения пары ГМС и семейства ГМС. Успех разработки таких ИПС напрямую зависит от создания математических теорий сходства ГМС и разработки как эвристических, так и точных эффективных атгоритмов поиска одного или всех общих фрагментов пары.
Как отмечено в ряде работ, сдерживающим фактором на пути создания интеллектуальных экспертных систем с правдоподобными рассуждениями в области информатики является отсутствие развитых теорий сходства и инструментальных программных средств для определения и исследования сходства структурированных нечисловых объектов (графов, мультиграфов, гиперграфов).
Таким образом, проблема определения сходства структур, представленных графами, и во всем многообразии форм (точная идентификация, частичная идентификация, наиболее адекватная идентификация) является центральной комбинаторной проблемой структурного анализа систем.
Анатаз сложности структур и разнообразие несходства и подобия в больших объединениях структур сделали необходимым развитие и расширение концепции подструктурной характеризации.
Широкий теоретический и прикладной спектр применения структурного анализа систем привел к выделению новой дисциплины - прикладной теории графов. Особую роль методы прикладной теории графов играют именно в развитии информационных технологий (теории трансляции, оптимизации программ, организации сложных структур данных, визуализации данных, построении человеко-машинных интерфейсов и др.). Одним из основных и актуальных для решения классов задач прикладной теории графов является класс задач различения графов и различения расположения фрагментов графов. История развития методов решения задач различения графов насчитывает более 50 лет.
В настоящее время в решении задач распознавания изоморфизма графов, распознавания изоморфного вложения графов и смежных с ними задач достигнут большой теоретический и практический прогресс. Но задачи характеризации структур с учетом расположения фрагментов, изучены намного слабее. Исследования, связанные с учетом расположения фрагментов в структурах, актуализировались в конце 90-х годов прошлого века в связи с развитием приложений химической теории ірафов (QSAR-анализа, QRRR-тэлта. и др.), правдоподобных рассуждений, структурного распознавания образов, структурной лингвистики. Эти исследования шли в достаточно узких областях (например, большинство предложенных топологических индексов явно или неявно учитывали расположение простейших фрагментов) и проводились несистематически. Не существует даже устоявшейся терминологии, пригодной как для теоретических, так и для прикладных исследований. Эта проблема актуализировалась ещё больше после того, как Журавлёв Ю.И. и его ученики с наиболее общих теоретических позиций показали, что при решении задач распознавания выражение глобальных (интегральных) свойств через локальные вполне возможно.
Учёт расположения фрагментов ГМС наполняет новым содержанием отношения «подсистема-надсистема». Задачи различения и сходства расположения фрагментов ГМС обобщают задачи сравнительного анализа ГМС, принимая во внимание надсистему, в которую входят рассматриваемые фрагменты. Решение этих задач позволяет исследовать отношения эквивалентности и толерантности ГМС с учётом расположения и сходства расположения фрагментов, расширяет возможности подструктурной характеризации ГМС. Особенно ярко различия в расположении фрагментов проявляются в симметрии (асимметрии) расположения фрагментов. Учёт симметрии - общеметодологический принцип повышения эффективности компьютерной обработки структурной информации, как в задачах анализа, так и синтеза структур.
Работа продолжает исследования научного руководителя диссертанта -Кохова В.А., которые привели к созданию новой научной дисциплины «структурный спектральный анализ систем» (СС-анализ).
Центральной теоретической проблемой СС-анализа ГМС является построение монотонно расширяемых по индексам сложности систем базисов структурных инвариантов (дескрипторов) ГМС и исследование чувствительности (полноты) инвариантов при решении задач различения ГМС, определения их сложности и сходства. Выделены семь основных классов задач СС-анализа, среди которых в данной диссертационной работе рассматриваются два класса задач:
класс задач различения ГМС с учетом расположения фрагментов;
класс задач определения сложности ГМС с определением суммарного вклада фрагментов заданного вида в общую сложность.
Ввиду широкой теоретической и прикладной значимости ациклических структур (деревьев и орграфов без контуров) основное внимание при разработке алгоритмов и программ в диссертации уделено ациклическим структурам.
Целью диссертационной работы является создание методов и программных средств для эффективного решения задач различения и определения сложности ациклических структур систем (АС), представленных графами-деревьями и ориентированными графами без контуров. Это позволит повысить эффективность компьютерных методов сравнительного анализа ГМС и их применения при создании новых поколений информационно поисковых систем структурной информации и СИИ с правдоподобными рассуждениями, широко использовать их в научных и прикладных исследованиях, связанных со структурным анатазом систем.
Для достижения указанной цели в работе решаются следующие задачи:
разработка методов построения и исследования инвариантов, характеризующих расположение фрагментов в ациклических структурах с использованием расширяемых базисов структурных дескрипторов;
классификация задач различения деревьев и лесов (ациклических обыкновенных графов) и разработка методов их решения;
классификация задач различения орграфов без контуров с учетом расположения их фрагментов и разработка методов их решения;
разработка методов решения задач различения расположения фрагментов в АС;
разработка методов решения задач определения сходства АС на основе их сложности;
построение программной подсистемы «Различение, сложность и сходство ациклических структур» и её использование в учебном процессе и научных исследованиях.
Научная новизна
В pduulc Никитина исрсисмшшОСіь и зффемиинисіь учета расположения
фрагментов при решении задач различения и определения сложности АС с использованием вычислительной техники. Разработанные методы и программные средства отличаются новыми возможностями в части:
повышения эффективности поиска и анализа сходства структурной информации, представленной семантическими сетями;
использования новых ЭВМ-ориентированных методов формирования и исследования отношений толерантности и подобия структур систем при их характеризации в базисе путей;
характеризации расположения фрагментов в ациклических структурах и характеризации ациклических структур с учётом расположения фрагментов с наиболее общих теоретико-графовых и теоретико-групповых позиций;
расширения сферы применения и повышения эффективности методов различения, анализа сложности и сходства структур, представленных обыкновенными графами, на класс ациклических структур.
Практическая значимость работы заключается в создании методов и на их основе базового программного обеспечения, позволяющего повысить качество и эффективность решения задач структурного анализа систем, связанных с их различением, анализом сложности и сходства. Результаты важны для приложений структурной информатики и могут быть применены в системах искусственного интеллекта и поддержки принятия решений, в структурном распознавании образов и интеллектуальном анализе данных, семантическом шеб-поиске документов в базах знаний, Интернете и др.
Результаты работы внедрены в учебный процесс МЭИ(ТУ), ГУ-ВШЭ и научно-исследовательскую работу кафедры Прикладной математики АВТИ МЭИ (ТУ).
Методы исследований и достоверность результатов. Задачи, поставленные в работе, решаются с помощью методов теории графов, прикладной теории графов, теории групп, теории анализа вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др. В работе использованы результаты, которые получили Кохов В.А, Фараджев И.А., Грызунов А.Б., Ткаченко СВ., Незнанов А.А, Скоробогатов BA.,J.R. Ullmann, B.D.McKay, G.F. Royle, Luks, L.E.Druffel и др.
Достоверность научных результатов подтверждена теоретическими выкладками, результатами тестирования, а также сравнением полученных результатов с результатами, приведенными в научной литературе.
При обработке сложных исходных данных сравнивались результаты, полученные различными методами решения одной и той же задачи.
Реализация результатов. Разработанные программные средства используются в научных исследованиях ИВМиМГ СО РАН, учебном процессе и научно-исследовательской работе кафедры Прикладной математики МЭИ (ТУ), кафедры «Анализ данных и искусственный интеллект» ГУ-ВШЭ.
Апробация работы
Основные положения и результаты диссертации докладывались и обсуждались на четырнадцатой международной конференции «Информационные средства и технологии», г. Москва, (2006 г.), тринадцатой и шестнадцатой международных научно-технических конференциях студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (г. Москва, 2007г., 2010г.).
Личный вклад диссертанта. Работа развивает методы структурного спектрального анализа систем для повышения качества и эффективности обработки структурной информации на ПЭВМ.
Диссертантом лично выполнены.
Классификация задач различения ациклических структур, лежаших в основе системного анализа и развития возможностей применения подструктурной характеризации систем.
Разработка методов как точного, так и приближенного решения задач различения ациклических структур с учетом расположения фрагментов (цепей и путей).
Создание метода, в рамках использования базовых моделей, для решения задач определения сложности и общих вкладов фрагментов (цепей и путей) в сложность ациклических структур.
Исследование разработанных алгоритмов и их реализаций, заключающееся в установлении границ применимости, определении теоретических и экспериментальных оценок вычислительной сложности, сравнении с ранее существующими алгоритмами.
Реализация разработанных алгоритмов в виде подсистемы «Различение, сложность и сходство ациклических структур» для АСНИ «GraphModel Workshop» (GMW) и программных средств учебного назначения.
Публикации. Основные результаты диссертационной работы, опубликованы в пяти печатных работах, включая одну статью в журнале, рекомендуемом ВАК для публикации основных результатов диссертационных работ.
Структура и объём работы. Диссертация состоит из введения, четырех глав,
заключения, списка литературы (11^ наименования) и приложений. Диссертация содержит 1 страницы машинописного текста.
