Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур

Тема работы: Разработка методов и программных средств для решения задач различения и анализа сложности ациклическихктур.

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

работы.

К центральным проблемам исследования по информационным семантическим системам (ИСС), то есть системам, перерабатывающим осмысленную информацию для достижения целей относятся, сравнение и принятие решения. В настоящее время исследования по созданию и широкому применению ИСС, активно ведутся как в нашей стране, так и за рубежом [1,2]. Сравнение и принятие решения — основная семантическая операция.

Важным понятием в ИСС является понятие структуры. Понятие структуры представляется важным с точки зрения классификации существующих и вновь создаваемых форм семантических систем [2,3]. Принято разнообразие основных структур определять разнообразием графовых моделей систем (ГМС) и ах обобщений.

Анализ сложности структур и разнообразие несходства и подобия в больших объединениях структур сделали необходимым развитие и расширение концепций подструктурной характеризации. Широкий теоретический и прикладной спектр применения структурного анализа привел к выделению новой дисциплины — прикладной теории графов [4].

Особую роль методы прикладной теории графов играют именно в развитии информационных технологий (теории трансляции, оптимизации программ, организации сложных структур данных, визуализации данных, построении человеко-машинных интерфейсов и др.) [4]. Одним из основных классов задач прикладной теории графов является класс задач различения графов и различения расположения фрагментов графов. История развития методов решения задач различения графов насчитывает более 50 лет. В настоящее время в решении задач построения и исследования инвариантов графов для решения задач различения и распознавания изоморфизма графов, распознавания изоморфного вложения графов и смежных с ними задач достигнут большой теоретический и практический прогресс [58]. Но задачи характеризации структур в различных базисах подструктур, задачи определения одного, всех или всех канонических изоморфных вложений одной структуры в другую изучены намного слабее. Исследования, связанные с учетом расположения фрагментов в структурах актуализировались в конце 90-х годов прошлого века в связи с развитием приложений химической теории графов (0&-47?-анализа, ORRR-анализа и др.)? правдоподобных рассуэюдений, структурного распознавания образов, структурной лингвистики. Эти исследования шли в достаточно узких областях (например, большинство предложенных топологических индексов явно или неявно учитывали расположение простейших фрагментов) и не систематически. Не существует даже устоявшейся терминологии, пригодной как для теоретических, так и для прикладных исследований. Эта проблема актуализировалась ещё больше после того, как Журавлёв Ю. И. и его ученики [9] с наиболее общих теоретических позиций показали, что при решении задач распознавания выражение глобальных (интегральных) свойств через локальные (в нашем смысле в различных конечных базисах структурных фрагментов) вполне возможно.

В прикладном плане задачи поиска одинаковых текстовых документов или документов, включающих заданные текстовые фрагменты, или сходных с заданным порогом сходства документов, в сети Интернет и базах семантической информации, представленной семантическими сетями, являются особенно актуальными при создании следующего поколения Интернета, относящегося к Интеллектуальному Интернету [2, 10].

Как выделено в [7,8,11−20] учёт расположения фрагментов ГМС наполняет новым содержанием отношения «подсистема-надсистема». Задачи различения и сходства расположения фрагментов ГМС обобщают задачи сравнительного анализа ГМС, принимая во внимание надсистему, в которую входят рассматриваемые фрагменты. Решение этих задач позволяет выделять новые подходы к формированию и исследованию стратифицированных систем отношения эквивалентности и толерантности ГМС с учётом распололсения и сходства расположения фрагментов, расширяет возможности подструктурной характеризации ГМС. Особенно ярко различия в расположении фрагментов проявляются в симметрии (асимметрии) расположения фрагментов. Учёт симметрии — общеметодологический принцип повышения эффективности компьютерной обработки структурной информации, как в задачах анализа, так и синтеза структур.

Работа продолжает исследования научного руководителя диссертантаКохова В.А., которые привели к созданию новой научной дисциплины «структурный спектральный анализ систем» (СС-анализ), и позволяют на единой методологической основе строить достаточно эффективные алгоритмы решения большинства задач из классов базовых задач структурной информатики [6−8, 11−13] .

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

В СС-анализе структур систем выделены 7 базовых классов задач [6−8]:

1) Задачи характеризации структур систем на основе порождающих и базовых граф-моделей в расширяемых базисах структурных дескрипторов (СД).

2) Задачи различения структур систем с учетом расположения их фрагментов. Анализ отношений эквивалентности структур систем с учетом расположения фрагментов, характеризуемого базисом СД.

3) Задачи упорядочения структур систем на основе их спектральной сложности с учетом вкладов фрагментов в общую сложность. Анализ отношений порядка на структурах систем с использованием расширяемых базисов СД.

4) Задачи определения отношения квазипорядка (разбиение множества структур на упорядоченные непересекающиеся классы) на структурах систем. Анализ отношений квазипорядка на структурах систем с использованием расширяемых базисов СД.

5) Задачи определения сходства структур систем с учетом сходства расположения фрагментов в структуре системы. Анализ отношений толерантности (ставящих в соответствие каждой структуре подмножество других структур-базисов) структур систем в расширяемых базисах СД.

6) Задачи прорисовки диаграмм структур систем с учетом симметрии расположения фрагментов и их вкладов в общую сложность структуры системы.

7) Задачи визуализации методов интерактивного решения JVP-полных задач на структурах систем и результатов решения задач СС-анализа, связанного с базовыми морфизмами и их обобщениями над структурами систем (изоморфизмы, автоморфизмы, изоморфные вложения, изоморфные пересечения, гомеоморфизмы, ' гомеоморфные вложения, гомеоморфные пересечения и др.). .

Ввиду широкой теоретической и прикладной значимости ациклических структур (деревьев и орграфов без контуров) (АС) основное внимание при разработке алгоритмов и программ уделено ациклическим структурам.

Цель работы.

Целью диссертации являетсясоздание методов и программныхсредств — для эффективного решения задач различения и определения сложностиациклических структур систем (АС), представленных графами-деревьями или ориентированными графамибез контуров: Это позволит повысить эффективность компьютерных методов сравнительного анализа ГМС и их применения при создании новых поколений информационно поисковых систем структурной информации и СИИ с правдоподобными рассуждениями, широко использовать их в? научных и прикладных исследованиях, связанных со структурным анализом систем.

Решаемые задачи.

1. Разработка метода построения и исследования инвариантов, характеризующих расположение фрагментов в АС с использованием монотонно^расширяемых базисов структурных дескрипторов;

2. Классификация задач различения АС и разработка методов их решения.

3. Классификация задач определения сложности АС и разработка методов их решения.

4. Разработки. методов и программных средств для решения задач различения расположения фрагментов в АС.

5. Разработки методов и программных средств для решения задач различения АС с учетом расположения фрагментов вАС.

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

7. Построение программной подсистемы «Различение и сложность ациклических структур» и её использование в учебном процессе и научных исследованиях.

Научная новизна.

В работе показана перспективность и эффективность учёта расположения фрагментов при решении задач различения и определения сложности АС с использованием вычислительной техники. Разработанные методы и программные средства отличаются новыми возможностями в части:

— характеризации расположения фрагментов в ациклических структурах и характеризации ациклических структур с учётом расположения фрагментов с наиболее общих теоретико-графовых и теоретико-групповых позиций;

— расширения сферы применения и повышения эффективности методов различения и анализа сложности структур, представленных обыкновенными графами, на класс ациклических структур;

— повышения эффективности поиска и обработки структурной информации, представленной семантическими сетями;

— использования новых ЭВМ-ориентированных методов формирования и исследования отношений эквивалентности и подобия структур систем при их характеризации в базисе путей.

Практическая полезность работы.

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

Результаты работы внедрены в учебный процесс МЭИ (ТУ), ГУ-ВШЭ и научно-исследовательскую работу кафедры Прикладной математики АВТИ МЭИ (ТУ).

Методы исследований и достоверность результатов.

Задачи, поставленные в работе, решаются с помощью методов теории графов, прикладной теории графов, теории групп, теории анализа вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др. В работе существенно использованы результаты, которые получили Кохов В. А, Фа-раджев И.А., Грызунов А. Б., Ткаченко С. В., Незнанов А. А, Скоробогатов В. А., J. R. Ullmann, В. D. McKay, G. F. Royle, P. Willett, E. Luks, L. E. Druffel и др.

Достоверность научных результатов подтверждена теоретическими выкладками, результатами тестирования, а также сравнением полученных результатов с результатами, приведенными в научной литературе.

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

Реализация результатов.

Разработанные программные средства используются в научных исследованиях ИВМиМГ СО РАН, учебном процессе и научно-исследовательской работе кафедры Прикладной математики МЭИ (ТУ), кафедры «Анализ данных и искусственный интеллект» ГУ-ВШЭ.

Апробация работы.

Основные положения и результаты диссертации докладывались и обсуждались на четырнадцатой международной конференции «Информационные средства и технологии», г. Москва, (2006 г.), тринадцатой и шестнадцатой международных научно-технических конференциях студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (г. Москва, 2007 г., 2010 г.).

Личный вклад диссертанта.

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

1. Классификация задач различения двух ациклических структур, лежащих в основе системного анализа и развития возможностей применения под-структурной характеризации систем.

2. Разработка методов как точного, так и приближенного решения задач различения ациклических структур с учетом расположения фрагментов (цепей и путей).

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

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

5. Реализация разработанных алгоритмов в виде подсистемы «Различение и сложность ациклических структур» для АСНИ «GraphModel Workshop» (.

Публикации.

Основные результаты диссертационной работы, опубликованы в четырех печатных работах, включая одну статью в журнале, рекомендуемом ВАК для публикации основных результатов диссертационных работ. Структура и объём работы.

Диссертация состоит из введения, четырех глав, заключения, списка литературы (115 наименований) и двух приложений. Диссертация содержит 158 страниц машинописного текста.

Основные результаты работы:

1. Ввиду широкой научной и прикладной значимости выделен класс ациклических структур как наиболее перспективный для построения эффективных алгоритмов решения задач различения АС и их применения при семантическом поиске текстовых документов в базах документов и Интернете и сравнении моделей знаний.

2. Предложена классификация задач различения АС, на основе которой выделены:

• для деревьев 14 видов задач из класса Р и 24 вида из класса NPC;

• для орграфов без контуров 34 задачи из класса NPC.

3. Разработаны две системы моделей (g-, 6-модели) и методов, учитывающих точное (до орбит /-групп АС) и приближенное расположение цепных фрагментов и направленные на расширение возможностей структурного анализа систем и повышение эффективности его применения при решении трех классов задач различения:

• различение орграфов без контуров;

• различение расположения цепных фрагментов в ациклических структурах;

• различение ациклических структур с учетом расположения цепных фрагментов.

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

5. На основе анализа двух основных подходов к решению задач различения графов выделен метод монотонных расширений частичных решений как наиболее перспективный для разработки эффективных алгоритмов точного решения базовых задач различения. На его основе разработаны алгоритмы и программы (в среде Borland Developer Studio2006, расширения выполнены в виде DLL библиотеки, объем авторского исходного кода 121 КБ, количество компилируемых строк кода 2117, объем машинного кода 226 КБ) для решения базовых задач различения АС и определены экспериментальные оценки вычислительной сложности алгоритмов по оригинальной научной методике.

6. Разработаны алгоритмы сокращенного перебора для решения TVP-полных задач в классе АОГ:

• изоморфное вложение леса в дерево;

• все изоморфные вложения леса в дерево;

• все канонические изоморфные вложения леса в дерево, определены ЭОВС алгоритмов и границы применимости их программных реализаций.

7. Предложены методы характеризации АС на основе моделей сложности и результаты решения ТУР-полных задач различения АС на основе индексов и вектор-индексов сложности. Приведены результаты сравнительного анализа 4 видов моделей сложности. Приведен сравнительный анализ трех подходов к определению сложности АС.

8. На основе анализа ЭОВС алгоритмов показано, что эффективная реализация базовых алгоритмов сравнения АС позволяет обрабатывать АС средней сложности:

• при изоморфизме — до 1500 вершин;

• при изоморфном вложении — до 1000 вершин (фрагмент 200−500 вершин);

• при использовании^{-моделей} (например, вида VP0.50 для средних по сложности деревьев — до 32 000 вершин).

9. Предложенные алгоритмы и программы позволили создать подсистему иерархического поиска структурной информации в больших базах АС и решать 5 видов задач поиска документов, представленных орграфами без контуров.

10.На основе разработанных программ создана подсистема «Различение и сложность ациклических структур», в рамках АСНИ «GMW», которая используется в учебном процессе и научных исследованиях студентов МЭИ (ТУ) при изучении базовой дисциплины «Информатика, раздел „Основы структурной информатики“» и спецдисциплин «Теория графов и комбинаторика», «Дискретная математика», «Анализ и проектирование эффективных алгоритмов», студентов ГУ-ВШЭ, научных исследованиях ИВМиМГ СО РАН.

ЗАКЛЮЧЕНИЕ

.

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