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

На правах рукописи

Й04Ь04<И <

ДЖАСИМ МАЛАТХ РАХИМ

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 7 ИЮН 2010

Москва, 2010

004604447

Работа выполнена на кафедре Прикладной математики Московского Энергетического Института (Технического Университета)

Научный руководитель: кандидат технических наук, доцент

Кохов Виктор Алексеевич

Официальные оппоненты: доктор технических наук, профессор

Фальк Вадим Николаевич

кандидат технических наук, доцент Незнанов Алексей Андреевич

Ведущая организация: Институт вычислительной математики и

математической геофизики СО РАН (Новосибирск)

Защита состоится £5 2010 г. в IV час. 00 мин.

на заседании диссертационного совета Д 212.157.01 при Московском Энергетическом институте (Техническом Университете) по адресу: 111250, Москва, Красноказарменная ул., д. 13 (ауд. М-704)

С диссертацией можно ознакомиться в библиотеке

Московского Энергетического Института (Технического Университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба направлять по адресу: 111250, г. Москва, ул. Красноказарменная, д. 14, Ученый Совет МЭИ (ТУ).

Автореферат разослан «2о,о5> 2010 г.

Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук, доцент

Фомина М.В.

Общая характеристика работы

Актуальность темы исследований.

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

Из анализа научных работ следует, что при создании ИПС и АСНИ, связанных с анализом структур систем, используют три основных подхода к поиску:

• методы поиска на основе точной идентификации;

• методы поиска на основе частичной идентификации;

• методы поиска на основе наиболее сходной (наилучшей) идентификации. Три выделенных подхода определяют три разновидности сходства структур.

Пррпя« гnvг^пя методов трсоуст наличия эффективных алгоритмов распознавание изоморфизма (идентификации, канонизации) ГМС и находит применение при разработке ИПС, связанных со структурным поиском.

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

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

Как отмечено в ряде работ, сдерживающим фактором на пути создания интеллектуальных экспертных систем с правдоподобными рассуждениями в области информатики является отсутствие развитых теорий сходства и инструментальных программных средств для определения и исследования сходства структурированных нечисловых объектов (графов, мультиграфов, гиперграфов).

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

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

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

В настоящее время в решении задач распознавания изоморфизма графов, распознавания изоморфного вложения графов и смежных с ними задач достигнут большой теоретический и практический прогресс. Но задачи характеризации структур с учетом расположения фрагментов, изучены намного слабее. Исследования, связанные с учетом расположения фрагментов в структурах, актуализировались в конце 90-х годов прошлого века в связи с развитием приложений химической теории храфов {()8АК-анализа, анализа и др.), правдоподобных рассуждений, структурного распознавания образов, структурной лингвистики. Эти исследования шли в достаточно узких областях (например, большинство предложенных топологических индексов явно или неявно учитывали расположение простейших фрагментов) и проводились несистематически. Не существует даже устоявшейся терминологии, пригодной как для теоретических, так и для прикладных исследований. Эта проблема актуализировалась ещё больше после того, как Журавлёв Ю.И. и его ученики с наиболее общих теоретических позиций показали, что при решении задач распознавания выражение глобальных (интегральных) свойств через локальные вполне возможно.

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

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

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

1) класс задач различения ГМС с учетом расположения фрагментов;

2) класс задач определения сложности ГМС с определением суммарного вклада фрагментов заданного вида в общую сложность.

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

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

Для достижения указанной цели в работе решаются следующие задачи:

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

• классификация задач различения деревьев и лесов (ациклических обыкновенных графов) и разработка методов их решения;

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

• разработка методов решения задач различения расположения фрагментов в ЛС;

• разработка методов решения задач определения сходства АС на основе их сложности;

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

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

В реши 1 с показана исрсисмиьиОСхь и эффсмиьнисхь учет расположения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Диссертантом лично выполнены.

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

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

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

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

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

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

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (ll^* наименования) и приложений. Диссертация содержит страницы машинописного текста.

Содержание работы

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

В первой главе приведен обзор по задачам различения графов, их классификациям и основным методам к их решению. Выделено, что в наиболее общем виде базовая задача различения пары графов определяется следующими параметрами: DP = <G\,Gi; ст, t>, где t - тип с-эквивалентного вложения графа (фрагмента) в граф.

Рассмотрены следующие задачи: (1) определение орбит группы графа; (2) определение классов ст-эквивалентности вершин, где с задается базисом структурных дескрипторов; (3) канонизация матрицы смежности вершин графа; (4) определение ст-эквивалентности графов, где а задается базисом структурных дескрипторов; (5) определение о-эквивалентного вложения графа в граф, где ст задается базисом

структурных дескрипторов расширяют инвариантное ядро задач различения до класса задач различения пары графов. Предложена классификации задач различения для ациклических обыкновенных графов (АОГ), включающая 14 задач из класса Р и 24 задачи из класса ЫРС.

Выделены два концептуально разных метода решения базовых М'-полных задач различения пары графов и имеющих обобщение для решения задач анализа сходства графов: (1) метод, использующий конструкцию Визипга-Леви, и основанный на применении операции модульного произведения графов и разборки графов на клики наибольшего порядка; (2) метод монотонных расширений частичных решений (ММРЧР), предложенный Коховым В.А., основанный на развитии идей конструктивного перечисления комбинаторных объектов, и обобщении алгоритмов определения изоморфного вложения одного графа в другой. Проведен подробный сравнительный анализ методов.

К недостаткам первого метода, по сравнению со вторым, следует отнести: (1) принципиальную не применимость для разработки алгоритмов решения задач изоморфного ьложСпИл как частичный гра^ илк частичный подграф. Ото объясняется потерей в модульном произведении информации о связях между вершинами исходных графов. По этой же причине: (1) невозможно применение каких-либо специальных методов сокращения перебора при анализе исходных графов; (2) при поиске клик реализуется перебор в ширину, что при отсутствии эффективных механизмов его сокращения определяет относительно высокие требования к оперативной памяти ПЭВМ при работе алгоритмов и приводит к большой емкостной и вычислительной сложности алгоритмов; (3) невозможно строить алгоритмы, с априори заданным фрагментом как частью решения, которые необходимы в различных прикладных областях (химическая информатика, распознавание образов и др.).

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

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

Из анализа научных работ сделан вывод, что дальнейшее развитие методов решения задач различения и определения сложности ГМС становится невозможным без разработки основ теории структурных инвариантов граф-моделей систем с акцентом на характеризацию и исследование структурных инвариантов расположения фрагментов в ГМС в единой концепции взаимосвязи «Фрагмент-БазисСтруктурныхДескрипторов-Структура».

Выделены основные сферы прикладной значимости разработки алгоритмов изоморфного вложения АС, среди которых построение и сравнение онтологий различных предметных областей; (2) семантический %>ей-поиск документов и др.

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

Задача 1. Изоморфизм двух орграфов без контуров (1С). УСЛОВИЕ. Заданы два орграфа без контуров 0\=(1\,Е{), Ог{]72,Е}).

ВОПРОС. Существует ли взаимно однозначное соответствие между множествами V\, V2, которое сохраняет отношение смежности?

Задача 2. Изоморфизм слабосвязному подграфу (ICWS). УСЛОВИЕ. Заданы два орграфа без контуров Gi=(Fi,£i), G2=(V2,Ei). ВОПРОС. Существуют ли в G\=(VhE\) слабосвязный подграф G*=(V*JE*), такой, что 0*~CJ2, то есть Эср: К2оР и Vv^e V2 Цу,\))&Е2 <н> (ф(п),ф( v,))e£*], где F*?

Задача 3. Изоморфизм слабосвязному фрагменту (ICWF). УСЛОВИЕ. Заданы два орграфа без контуров G\={V\,E\), Gi^iV^Ei). ВОПРОС. Существуют ли слабосвязпый фрагмент G*=(V*,E*), такой, что

G*«G2, то есть Эф: Е2<^Е* и Vv^v,е V2 [fovjeij о (ф(г>,-),ф(у;))е£*], где v,)eF*?

По вычислительной сложности задача различения 1 принадлежит классу NPI, задача различения 2 принадлежат классу Р, если G2 - ордерево, a Gi - орлее, и классу NPC, даже если G2 - орлее, a G\ - ордерево . Задача различения 3 в общем случае принадлежит классу NPC.

На основе выделения четырех параметров: (1) р - число компонент связности в анализируемых G\,G2; (2) Д - вид различения Gi,G2; (3) frag - вид части графа 6ъ в которую вкладывается G2; (4) REZ - вид решаемой задачи по числу и типу результатов, предложена классификация задач определения изоморфного вложения пары АОРГ. В результате выделено 34 вида задач, образующих первый класс инвариантного ядра задач в СС-анализе АС, объединенных в 9 подклассов. Далее приведено описание алгоритма решения задачи «изоморфизм поддереву» и обоснована его принадлежность по вычислительной сложности к классу Р.

На основе оригинальной методики, включающей использование генераторов АС с тремя уровнями сложности (низким, средним, высоким), приведены результаты получения экспериментальных оценок вычислительной сложности (ЭОВС) при решении четырех задач: (1) изоморфизм поддереву; (2) определение всех канонических изоморфных вложений (КИВ) дерева в дерево; (3) изоморфизм подлеса дереву; (4) определение всех КИВ леса в дерево.

Анализ полученных результатов позволяет сделать вывод о высокой эффективности решения задачи определения одного и всех канонических изоморфных вложений леса в деревья по атгоритму, построенному на основе ММРЧР.

Приведено описание базового алгоритма изоморфизм орграфу без контуров и определены ЭОВС решения задачи для четырех представительных семейств АОРГ: (1) случайные с разной плотностью; (2) растущие ордеревья; (3) орграфы без контуров, построенные на основе ориентации средних по сложности планарных графов; (4) орграфы без контуров, близкие к полным орграфам без контуров.

На рис.1 приведены примеры результатов определения ЭОВС двух сравниваемых в работе алгоритмов (авторский А4 и VF2', как один из наиболее эффективных зарубежных алгоритмов) вложения. Результаты приведены для планарных АОРГ средних по сложности.

Приведен сравнительный аначиз эффективности решения задач различения для обыкновенных графов и АОРГ.

На основе анатиза полученных результатов по определению ЭОВС алгоритмов изоморфного вложения сделаны следующие выводы:

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

' P. Foggia, C. Sansone, M. Vento. A Performance Comparison of Five Algorithms for Graph Isomorphism, H international Workshop on Graph-based Representation in Pattern Recognition, Jschia, Italy, pp. 188-199,23-25 May, 2001.

Возможна обработка деревьев и ордеревьев с числом вершин до 32 ООО и вкладываемым фрагментов с числом вершин до 1 ООО.

2. Для решения задачи изоморфного вложения леса в дерево разработан достаточно эффективный алгоритм, позволяющий решать задачи с числом вершин дерева до 1000.

3. Сравнительный анализ алгоритма A4 с алгоритмом VF2 показывает, что он не уступает по эффективности VF2, а в ряде случаев и превосходят его по эффективности, особенно при распознавании отсутствия вложения. Границей применимости являются АОРГ с числом вершин до 12 000 и фрагментом в 500-1000 вершин, если анализируемые АОРГ принадлежат классу средних по сложности АС.

4. Алгоритмы A4 и VF2 эффективнее работают для АОРГ, чем для обыкновенных графов.

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

Одно вложение как подграф для планарных ср. (p(G2)=250)

1 150

ад о.

ш 100

V?2 = 2,840x^+1,095х+ ОД-

R1 = 0,999 Л4 = 0,575хг+5,921х + 3

тч N N Ш П

Число вершин в G,

Одно вложение как фрагмент для пленарных cp.(p(ff2)=248)

330 --------------------------------------

300 ) УГ2»».795и»*1.Ш«*(ЩЗ i R» = 0,999

¿250 ---------------

А4 = 0,603хЧ 5,24SX+52.55

Число вершин в Ct

Нет вложения как подграф (p(S2)=S0)

ь1_л 999

A4 = 48Д8Х2 -'46,27х) R'=l .

»л « г*

Число вершин 8 Gt

Нет вложения как подграф для ср. планарных p(G2)=2S0

f4 m m Число вершин в Сг

Рис. 1. ЭОВС алгоритмов изоморфного вложения планарных средних по сложности АОРГ

(1) формирования и исследования систем отношений эквивалентного расположения путей в АС; (2) различения расположения путей в АС; (3) различения АС с учетом расположения путей, заданной длины.

Формализованные постановки задач различения расположения фрагментов для обыкновенных графов и основные подходы к их решению впервые предложены Коховым

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

Приведены формализованные постановки и выделены задачи, образующие третий подкласс задач различения в СС-анализе АС (табл. 1).

Таблица 1.

№ Обозначение Задача (вариант ^-эквивалентности)

3 3.1. Различение расположения пары фрагментов типа Л, (1

3.1.1 Л «Л Автоморфное расположение / V 7)

3.1.2 f'1 сs f1,2 Расположение с вложением /"1 в/"2 в смысле подграфа

3.1.3 Г С/"2 Расположение с вложением /"1 в/''2 в смысле фрагмента

фрагмента /

3.2.1 Автоморфное расположениее^фотносительно/'

3.2.2 f csff'a Расположение с вложением в/"2 в смысле подграфа относительно

3.2.3 f"! с//и Расположение с вложением в/'2 в смысле фрагмента относительно /

Далее рассмотрен метод решения базовых задач различения расположения путей в АС на основе построения и использования цветных трансграфов путей. Цветные трансграфы путей являются надграфами для орграфов без контуров и позволяют взаимнооднозначно с сохранением симметрии анализируемого орграфа соотнести каждому пути вершину в надграфе. Исходный орграф без контуров является скелетным (без учета цвета, задающего длину пути) трансграфом путей (ТГП) с длиной 0 и 1.

На рис. 2 приведены примеры двух видов скелетных ТГП для орграфа без контуров в.

<J>

С - исходный орграф без контуров (GP0*(G)) (число автоморфизмов 2)

А - ориентация новых дуг с учетом ориентации дуги исходной АС без сохранения дуг исходной АС (вР^)) (число автоморфизмов 8) В - ориентация новых дуг с учетом ориентации дуги исходной АС с сохранением дуг исходной АС (5Р*{в)) (число автоморфизмов 2)

Рис. 2. Примеры скелетных трансграфов путей из двух разных классов

Кохов В.А. Метод анализа структурной сложности и сходства систем в различных базисах фрагментов. Тезисы докладов международной конференции «Информационные средства и технологии» международного форума информатизации МФИ-97, ТЗ. Москва, 1997.- С.43-48.

Нетрудно показать, что, ордеревья - это класс ЛС, в которых количество путей растет полиномиально с ростом числа вершин. Следовательно, время работы алгоритма построения ТГП на ордеревьях будет оцениваться как 0(р2). Объемные вычислительные эксперименты по построению ТГП двух анализируемых видов показали, что в отличие от обыкновенных графов ТГП АС только с учетом сохранения дуг исходной АС сохраняют справедливость гипотезы Кохова В.А.: «Группа автоморфизмов вершин АС изоморфна группе автоморфизмов вершин трапеграфа путей с ориентацией новых дуг в направлении анализируемого пути и сохранением дуг исходной АС».

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

Далее приведено построение класса базовых моделей (Ь-моделей) на основе ТГП и их обобщений (¿-моделей) с целью разработки метода приближенного решения задач различения расположения путей в орграфах без контуров. Пример матричного представления Ь-модели вида Р'>уссРи(С) и ее диаграммы приведен на рис. 3.

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

Базис пут ей-т ипов шк

Пути Р0 Р1 Р"1 Яз

2 1 3 1 0

4 1 3 1 0

3 1 2 3 1

1 1 2 3 1

14 0 1 1 0

23 0 1 1 0

24 0 1 2 0

12 0 1 2 1

43 0 1 2 1

143 0 0 1 0

123 0 0 1 0

243 0 0 1 1

124 0 0 1 1

1243 0 0 0 1

Рис. 3. Матрица М_Р1п>ссн>(С) и диаграмма граф-модели

инвариантом АС, каждая строка которой, является инвариантом, характеризующим расположение фрагмента АС по отношению к другим фрагментам.

В соответствии с видом достройки пути выделены 4 вида Ъ-моделей: (1) Ас%(б) - достройка каждого пути до пути-подграфа (символ в), включающего достраиваемый путь; (2) Р^с/ЧО - достройка каждого пути до пути-фрагмента, включающего достраиваемый путь; (3) Р1е\гс?Рм>(0) - достройка каждого пути от его конца до пути-подграфа (символ 8), включающего достраиваемый путь; (4) ЛсЛ^б) " достройка каждого пути от его конца до пути-фрагмента, включающего достраиваемый путь. В соответствии с этими четырьмя видами Ъ-моделей выделены 4 вида скелетных видов Ь-моделей, обозначенные как Р!^Р(С), Р'сРЮ, Р1'\*сРч>{0).

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

Задача построения трансграфов путей для орграфов без контуров принадлежит классу ЫРС. ЭОВС алгоритма построения ТГП дли орграфов без контуров определялись для различных семейств орграфов без контуров. На рис. 4 приведен пример результатов ппре п^трцча ЗОНС алгоритма построения ¿-модели вида для *1еты**2Х

семейств АС, построенных на основе случайной ориентации для: случайных графов плотности 50% (график у4); транзитивных графов степени 3 (график у!); транзитивные степени 4 (графику2); сильно регулярных графов вида ЛТ/(графикуЗ).

180000 160000 140000 120000 юоооо 80000 60000 40000 20000 о

у4 = 57,966х» -<- 915,73х2 - 3582.6Х * 4272,2 >|»7

К2 = 0,9952

уЗ

■ 662,17х* -=

- 2979Х * 3815,3 О.ЭЭ82-

У2 = 122.27х2 - 524.19х * 671.39

I*» = 0,9985

У1

■ 4.3057Х2 ■ -К» =

15.526Х + 22,364> 0,9968

1Г*

20

40 60 80

ЮО 120 140 160 180 200 220 240 число вершин

Рис. 4. ЭОВС алгоритмов построения ¿-моделей на разных семействах АС

Анализ результатов определения ЭОВС алгоритмов построения Ь-моделей свидетельствует об: (I) эффективности решения задач различения и сходства расположения цепей всех длин в деревьях с числом вершин до 1000; (2) достаточной для практического применения эффективности решения задач различения и сходства расположения путей всех длин в орграфах без контуров.

Сделаны выводы о том, что метод использования ¿-моделей для АС позволяет: (1) построить методологию иерархического монотонного уточнения расположения путей в АС, а предел такого уточнения (орбиты /-групп путей), дает метод использования моделей; (2) выделять и решать новые классы задач различения и определения сходства АС, такие, как различение и сходство АС с учетом расположения фрагментов или с учетом сходства расположения фрагментов.

Методы построения ¿-моделей в совокупности с ^-моделями впервые создают систему исследования полноты стратифицированных расширяемых по индексам сложности базисов СД при решении задач различения и сходства АС, задач различения и сходства расположения фрагментов в АС. Базисы АС состоят из структур без кошуров и их надграфов, что существенно сокращает длину базиса СД и приводит к разработке более эффективных алгоритмов различения и сходства АС в сравнении с различением

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

В научном аспекте предложенные методы позволили расширить известные ранее подходы к решению задач различения и сходства АС. Кроме того, появилась возможность ставить и решать новые классы задач различения и сходства. Эти задачи связаны с анализом расположения и сходства расположения цепных фрагментов в АС, а так же различения и сходства АС с учетом расположения и сходства расположения цепных фрагментов заданного типа.

Глава 4 посвящена вопросам исследования точности решения задач различения на основе индексов и вектор-индексов сложности АС. Разработка моделей характеризации сложности АС в различных базисах структурных дескрипторов с учетом вкладов фрагментов базиса в общую сложность АС является новой задачей в СС-анализе АС. В главе предложены понятия индекса и вектор-индекса, характеризующие сложность АС в расширяемом базисе путей (цепей). Выбор базиса путей (цепей для деревьев), как первоочередного для исследования АС, обоснован следующими причинами: (1) любые АС ¡мсл'счают г.утп; (2) пути отражают как локальные (пути малою длины), 1 и глобальные (пути большой длины) свойства АС; (3) пути - наиболее легко конструктивно перечислимые фрагменты в сравнении с другими фрагментами АС; (4) пути относятся к классу монотонно наращиваемых по сложности структурных базисов для характеризации АС; (5) в базисе путей естественным образом задается строгий порядок. Чувствительность базиса путей при различении АС исследуется в данной работе.

Приведено описание алгоритма вычисления индексов и вектор-индексов сложности АС. На рис. 5 приведем пример орграфа без контуров, результаты вычисления индекса сложности которого в базисе путей, приведены в табл. 2.

^ _ - _ 1 а ж я в э -

Рис. 5. Вид окна АСНИ «С>/И'» с результатом вычисления индекса сложности

Таблица 2. Все пути АС, изображенной на рис. 5

Длина пути 0 Пути Число путей

(2) (3) (4) (5) (6) (7) (8) (9) (10) 10

1 (1,2) (1,3) (2,4) (2,5) (4,6) (5,6) (6,10) (3,7) (3,8) (7,9) (8,9)( 9,10) 12

2 (1,2,4)(1,2,5) (2,4,6)(2,5,6)(4,6,10)(5,6,10)(1,3,7) (1,3,8)(3,7,9)(3,8,9) (7,9,10)(8,9,10) 12

3 (1,2,4,6)(1,2,5,6)(2,4,6,10К2,5,6,10)(1,3,7,8Х1,3,8,9)(3,7,9,10)(3,8,9,10) 8

4 (1,2,4,6,10)(1,2,5,6,10)(1,3,7,9,10)(1,3,8,9,10) 4

Согласно формуле вычисления индекса сложности, в которой количество канонических изоморфных вложений путей каждой длины (P¡) умножается на сложность пути (ISC(Pj)) получим:

1SC(G) = 10*ISC(PO)+\2*ISC(PI)+\2*ISC(P2)+S*ISC(P3)+4*ISC(P4) = 826;

/5С(Ро)=1; 1SC(P¡)=3; /5С(Р2)=3* ISC(P0)+2*ISC(P¡}=9;

1SC(P3)=4* ISC{Pa)+3* 1SC{P i)+2* 15С{Р2)=Ъ\;

ISC(Pa) = 5*ISC(P0)+4*JSC(P¡)+3*ISC(p2)+2*lSC(P^m.

В итоге для рассматриваемого орграфа без контуров получим:

(1) ISC(G)=&26; (2) VJSC{G) = < 10; 36; 108; 248; 424 >.

Заметим, что проблема определения всех простых путей всех возможных длин между парой вершин орграфа, является ЛР-полной проблемой.

Далее для орграфов без контуров 2<р<9 (более 21 ООО ООО орграфов) приведены полученные оригинальные результаты результаты:

1. Решения задач различения и установлено: что (а) индексы и вектор-индексы сложности в базисе путей не являются полными инвариантами для решения задач различения орграфов без контуров; (Ъ) наиболее точное решение задач различения достигается при построении индексов и вектор-индексов в базисе путей-фрагментов; (с) базис цепей при различении деревьев имеет большую дискриминирующую способность, чем базис путей при различении орграфов без контуров; (d) для более точного решения задач различения орграфов без контуров необходимо базис путей расширять полупутями.

2. Классификации орграфов без контуров по характеристикам симметрии и сложности.

3. Точности различения на основе сравнения J-моделей четырех видов: (a) V<zsP; (Ь) Vе с?Р; (с) Vcp; (d) Vc.P с выделением результата о максимальном значении чувствительности различения равной 0,85 для é-модели вида Vе сР.

Далее рассмотрены вопросы применения разработанных алгоритмов при решении задач поиска информации в объемных базах структурной информации с помощью подсистемы поиска в АСНИ «GAW». Архитектура подсистемы поиска документов (семантических сетей) приведена на рис. 6.

Структурно подсистема делится на две части: ядро и набор программных расширений. Ядро подсистемы выполнено в виде одного исполнимого файла и содержит в себе следующие компоненты: (1) модуль анализа результатов, позволяющий визуализировать, сравнивать и анализировать данные, содержащиеся в БД; (2) модуль поиска, позволяющий выбирать сценарий поиска; (3) модуль управления базами семантических сетей, предоставляющий интерфейс пользователю для работы с базами структур - добавление, удаление, упорядочение; (4) модуль для работы с БД. С каждой базой структур связана база данных, содержащая результаты проведённых экспериментов. Помимо самих результатов, база содержит информацию о времени решения задачи и информацию о том, как и когда они были получены; (5) модуль запуска решателей позволяющий составить список решателей и запустить его на всех структурах базы или подмножестве структур, определенных по построенному ранее фильтру; (6) модуль выбора и запуска решателей задач (динамически загружаемых библиотек или исполнимых

файлов), осуществляющих вид сравнения СС; (7) модуль импорта и экспорта граф-моделей документов, позволяющий работать со структурами в различных форматах и

Ядро подсистемы « Поиск документов;»"

Модуль анализа результатов поиска семантических сетей

Модуль поиска СС сетей по видам и критериям поиска

Управление базами

семантических

сетей

Модуль работы с

БД

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

Решатели •задач сравнения семантическ их сетей

7 Импорт и

экспорт

структур из

различных

форматов,

генераторы

структур

.Программные расширении

8 Программы,

созданные

студентами в

ходе

выполнения

KP и TP

База СС

База результатов

Данные

Рис. 6. Архитектура подсистемы «Поиск документов» генерировать или конструктивно перечислять структуры, заданного вида; (8) написанные студентами программы, которые интегрируются в подсистему и становятся её частью.

В настоящее время особенно актуальна задача быстрого поиска структурной информации с учетом семантики запроса. Текстовые документы при семантическом поиске все чаще представляются в виде семантических сетей. Это связано с развитием языков представления информации в структурированной и атрибутированной форме с учётом семантики (XML, RDF, OWL, OIL и др.) и актуальным переходом от World Wide Web к Semantic Web. Центральное внимание уделено логико-вычислительным семантическим сетям, которые визуально представляются орграфами без контуров с весами на вершинах.

Разработанные архитектура и средства структурного поиска позволяют найти требуемую структуру в базе по заданному шаблону. Для этого созданы решатели для различения и определения сходства структур.

Для задания поискового запроса в подсистеме «Поиск документов» необходимо: (1) построить структуру-шаблон; (2) задать тип поискового запроса; (3) выбрать решатель для задачи сравнения структур в целях поиска.

Создание структуры-шаблона ничем не отличается от создания обычной структуры средствами редактора структур АСНИ «GMW.».

Модуль поиска позволяет найти в базе структуры с использованием различных критериев поиска: 1) подструктурного поиска ГМС:

• «найти такой же [граф]» - поиск структуры, изоморфной структуре-шаблону;

• «найти содержащий [граф]» - поиск структуры, в которую структура-шаблон изоморфно вкладывается;

• «найти содержащийся [граф]» - поиск структуры, изоморфно вкладывающейся в структуру-шаблон;

• «найти не содержащий [граф]» - поиск структуры, в которую структура-шаблон изоморфно не вкладывается;

• «найти не содержащийся [граф]» - поиск структуры, изоморфно не вкладывающейся в структуру-шаблон;

• «найти похожий [граф]» - поиск структуры, сходной со структурой-шаблоном;

2) поиска с использованием фильтров ГМС;

3) поиска по названию ГМС;

4) поиска ГМС, имеющих сходство с заданной ГМС не менее указанного значения.

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

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

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

На рис. 7 приведен пример вида окна АСНИ «GMW» с результатом поиска в базе из 250 ООО АС (режим найти и показать). Найден орграф с номером 242379, включающий орграф-шаблон как фрагмент за 192 мс. на ПЭВМ (2.83 GHz, 4Gb).

Рис. 7. Вид окна АСНИ «GMW» с результатом поиска структуры

Так например, при поиске в базе всех АС (р=8, 4 936 811 АС) орграфов без контуров, включающих систему орграфов-шаблонов, уточняющих на каждом этапе иерархического поиска модель шаблона, потребовалось выполнить 4 этапа поиска с созданием соответствующих фильтров. В результате пространство поиска сокращалось до 124, 63, 32 и было выделено 16 АС, отвечающих заданным условиям.

На рис. 8 приведен пример семантической сети-шаблона (р=23), для которой на рис. 9 приведен пример найденной семантической сети (р=200) в базе из 1 ООО семантических сетей по запросу «найти содержащий [граф]», т.е. поиск структуры, в которую структура-шаблон изоморфно вкладывается как фрагмент.

Ва'Ш^Ш^ЙИаУО... . .. . ..'14'... . ..'.. «да «КЯЙ 9 ► в а.л т ' ,

Ркс. 8. Диаграмма фрагмента, изоморфно вкладываемого в АС

рис. 9. Диаграмма АС с весами на вершинах, включающая АС-шаблсн как фрагмент

Время поиска, указанной АС с весами на вершинах, в базе из 1000 АС составило 74 мс с учетом 4 весов вершин в структуре-шаблоне и 10 весов вершин в каждой АС анализируемой базы. Для сравнения выделим, что аналогичный поиск без учета весов вершин АС составил 548 мс.

Из полученных результатов и ЭОВС алгоритмов можно сделать вывод о том, что эффективная реализация базовых алгоритмов сравнения АС позволяет за приемлемое время (менее минуты на одну АС на компьютере с процессором 2.83 GHz, 4Gb оперативной памяти) обрабатывать АС следующего порядка: (1) при полной идентификации - до 1500 вершин; (2) при частичной идентификации - до 1000 вершин (фрагмент до 500); (3) при приближённой характеризации время определяется видом используемых ¿-моделей. Например, при использовании полного структурного спектра в базисе путей (цепей) малых длин (от 0 до 6) - до 1000 вершин.

В приложении 1 приведены основные определения, описания разработанных алгоритмов и их программных реализаций с анализом вычислительной сложности.

В üpii.TOmCii.iii 2 прИБСдоп список ксхюльзусмых сокращении.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

2. Предложена классификация задач различения АС, на основе которой, выделены: (1) для деревьев 14 видов задач из класса Р и 24 вида из класса NPC; (2) для орграфов без контуров 34 задачи из класса NPC.

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

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

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

6. Разработаны алгоритмы сокращенного перебора для решения ОТ-полных задач в классе АОГ: (1) изоморфного вложения леса в дерево; (2) поиска всех изоморфных вложения леса в дерево; (3) все канонические изоморфные вложения леса в дерево. Определены ЭОВС алгоритмов и границы применимости их программных реализаций.

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

8. На основе анализа ЭОВС алгоритмов показано, что эффективная реализация базовых алгоритмов сравнения АС позволяет обрабатывать АС средней сложности: (1) при изоморфизме - до 1500 вершин; (2) при изоморфном вложении - до 1000 вершин (фрагмент 200-500 вершин); (3) при использовании Ь-моделей (например, вида У_Р0-50 для средних по сложности деревьев - до 32 000 вершин).

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

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

Список работ, опубликованных по теме диссертации:

1. Кохов В.А., Джасим М.Р., Кохов В.В. Графовые модели для анализа сложности структур систем. Вестник МЭИ, №1,2010. - С. 103-116.

2. Кохов В.А., Горшков С.А., Ибрахим А.Р., Джасим М.Р. АСНИ «Мастерская граф-моделей»: подсистема структурного спектрального анализа деревьев. Труды докладов международной конференции «Информационные средства и технологии», МФИ-2006, Т2. Москва, МЭИ, 2006.-С. 104-108.

3. Ибрахим А.Р., Джасим М.Р., Кохов В.А. Программный комплекс для структурного спектрального анализа ациклических графов. Труды докладов 13 международной НТК «Радиоэлектроника, электротехника и энергетика», Т1. М., МЭИ, 2007. - С. 360-361.

4. Джасим М.Р., Кохов В.А. Система моделей для анализа сложности графов. Труды докладов 16 международной НТК «Радиоэлектроника, электротехника и энергетика», Т1. М., МЭИ, 2010. - С. 357-358.

5. Кохов В.А., Джасим М.Р., Кохов В.В. Интегрированная среда визуального и алгоритмического решения задач поиска, сравнительного анализа и определения сложности ациклических графовых моделей систем. // ПСУН по дисциплинам «Структурный анализ систем», «Теория графов и комбинаторика», «Дискретная математика», «Построение и анализ эффективных алгоритмов» и др. / Паспорт от 18.06.2009 г. - М., МЭИ, 2009.

Подписано в печать Д бХ-Юг. Зак. Тир. 100 П .л. 1,25

Полиграфический центр МЭИ (ТУ) 111250, г. Москва, ул. Красноказарменная, д. 13

ВВЕДЕНИЕ.

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

Цель работы.

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

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

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

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

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

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

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

Публикации.

Содержание работы по

главам.

1. ЗАДАЧИ РАЗЛИЧЕНИЯ ГРАФОВ И МЕТОДЫ ИХ РЕШЕНИЯ.

1.1. Сравнительный анализ структур систем - центральная проблема СС-анализа систем.

1.2. Задачи различения графов.

1.3. Основные методы для решения задачи определения изоморфного вложения графа в граф.

1.3.1. Метод с использованием конструкции Визинга-Леви.

1.3.2. Метод монотонных расширений частичных решений.

1.3.3. Сравнительный анализ методов.

1.4. Орграфы без контуров их свойства и применение.

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

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

К центральным проблемам исследования по информационным семантическим системам (ИСС), то есть системам, перерабатывающим осмысленную информацию для достижения целей относятся, сравнение и принятие решения. В настоящее время исследования по созданию и широкому применению ИСС, активно ведутся как в нашей стране, так и за рубежом [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» (<GMW) и программных средств учебного назначения.

Публикации

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

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

ЗАКЛЮЧЕНИЕ

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

1. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. 1104 с.

2. Молекулярные графы в химических исследованиях. Тез. докладов конф. -Калинин. 1990. 117 с.

3. Кохов В.А. Основы химической структурной информатики. Тезисы докладов международной конференции «Информационные средства и технологии» международного форума информатизации МФИ-97, ТЗ. Москва, 1997. С.37-42.

4. Кохов В.А. Основы структурной информатики. Тезисы докладов международной конференции «Информационные средства и технологии» международного форума информатизации МФИ-98, ТЗ. Москва, 1998. С.42-47.

5. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации. // Проблемы кибернетики, Т. 33, 1978. С. 5-68.

6. Ибрахим Али Рашид Разработка методов и программных средств для анализа сходства ациклических структур. Диссертация к.т.н. 2009. С. 151.

7. Кохов В.А. Граф-модели в структурном спектральном анализе систем. Тезисы докладов международной конференции «Информационные средства и технологии», МФИ-2004, Т1. Москва, МЭИ, 2004. С.211-214.

8. Кохов В.А. Структурная информатика: содержание и проблемы. Тезисы докладов международной конференции. МФИ-2001,ТЗ. Москва, СТАНКИН, 2001.1. С.42-45.

9. M. Randic. Similarity Based on Extended Basis Descriptors. // J.Chem.Inf. Com-put. Sci. 1992, vol. 32, - pp. 686-692.

10. M. Rundic, C.L. Wilkins. Graph Theoretical Approach to Recognition of Structure Similarity in Molecules. //J. Inf. Comput. Sci. —vol. 19, no. 1 .pp. 16-39, 1979.

11. Кохов В.А. Метод построения и исследования топологических индексов молекулярных графов //Тезисы докладов межвузовской конференции «Молекулярные графы в химических исследованиях», Калинин. 1990. — С.41-42.

12. Кохов В.А. 111111 для анализа и синтеза граф-моделей регулярных топологий //Системное моделирование (СМ-18), Новосибирск, 1991, С.114-134.

13. Кохов В.А. Методы и программное обеспечение для сравнительного анализа граф-моделей информационных систем.//Материалы международной НТК «Проблемы функционирования информационных сетей». Новосибирск, 1991. — С.191-198.

14. Kokhov V.A. Methods, Algorithms and Programs for Analysis of Molecular Graph Similarity //The Fourth Japan-USSR Simposium on Computer Chemistry. October 28-30, 1991. Toyohashi University of Technology, Japan. 1991. p.53-54.

15. Кохов B.A., Грызунов А.Б., Картовицкий АЛ. П1111 для автоматизированного исследования сходства и сложности молекулярных графов.Тезисы докл. IX Всесоюзной конференции «Химическая информатика».Черноголовка. 1992. — С.132-133.

16. Кохов В.А. Метод определения подобия и сходства молекулярных графов на основе полных структурных спектров. Тезисы докл. IX Всесоюзной конференции «Химическая информатика», Черноголовка, 1992, 4.1. — С. 22-24.

17. Лебедев К.С., Кохов В.А., Шарапова О.Р. и др. Опознание крупных структурных фрагментов неизвестного соединениях помощью поисковой системы по ИК-спектрам //Сибирский химический журнал.- 1993. Вып.1. С. 50-56.

18. Кохов В.А. Структурные спектры и их применение для определения подобия и сходства графов. Труды ВЦ СО РАН, сер. Системное моделирование, вып. 1 (19), Новосибирск, 1993, С. 25-45.

19. Кохов В.А. Метод количественного определения сходства графов на основе структурных спектров //Приложения теории графов в химии Новосибирск, 1993. Вып. 149: Вычислительные системы. С.51-83.

20. Кохов В.А. Метод количественного определения сходства графов на основе структурных спектров. Известия АН СССР, сер. Техническая кибернетика. N5, 1994. С.143-160.

21. Кохов .В.А. Метод анализа структурной сложности и сходства систем в различных базисах фрагментов. Тезисы докладов международной конференции «Информационные средства и технологии» международного форума информатизации МФИ-97, ТЗ. Москва, 1997.- С.43-48.

22. Ткаченко С.В., Кохов В.А. Обобщенный подструктурный подход к анализу сходства систем. Тезисы докладов шестой международной НТК студентов и аспирантов, Т1. Москва, 2000. С.243-244.

23. Ткаченко С.В., Кохов В.А. Методы анализа структурного сходства систем. Тезисы докладов седьмой международной НТК студентов и аспирантов, Т1. Москва, 2001.-С.241-242.

24. Кохов В.А., Ткаченко С.В. Компьютерные методы исследования сходства расположения фрагментов структур. Тезисы докладов 8 международной НТК «Радиоэлектроника и электроника в народном хозяйстве», Tl. М., МЭИ, 2002. -С.290-291.

25. Ткаченко С.В., Кохов В.А. Средства формального концептуального анализа для исследования сходства графовых моделей систем. Тезисы докладов 9 международной НТК «Радиоэлектроника, электротехника и энергетика», Tl. М., МЭИ, 2003.-С.312-313.

26. Кохов В.А. Методы анализа сходства систем с учетом расположения фрагментов. Тезисы докладов международной конференции «Информационные средства и технологии», МФИ-2003, Т1. Москва, МЭИ, 2003. С.213-215.

27. Горшков С.А., Кохов В.А. Эффективность подструктурного подхода к анализу сходства древовидных структур. Тезисы докладов 10 международной НТК «Радиоэлектроника, электротехника и энергетика», Tl. М., МЭИ, 2004. С.315-316.

28. Кохов В.А., Ткаченко С.В. Метод иерархического исследования сходства структур систем. Тезисы докладов научной сессии МИФИ-2004. ТЗ. Интеллектуальные системы и технологии. М. МИФИ. 2004. С. 184-185.

29. Незнанов А.А., Кохов В.А. Сходство подсистем в топологии надсистемы. Тезисы докладов научной сессии МИФИ-2004. ТЗ. Интеллектуальные системы и технологии. М. МИФИ. 2004. С.198-199.

30. Кохов В.А., Незнанов А.А., Ткаченко С.В. Компьютерные методы анализа сходства графов. Девятая Национальной конференция по искусственному интеллекту с международным участием. КИИ-2004: Труды конференции. В 3-х т. Том 1. М.: Физматлит, 2004. С. 162-171.

31. Кохов. В.А., Незнанов А.А., Горшков А.А. 111111 «СТРИН+»: подсистема сравнительного анализа структур. Тезисы докладов международной конференции «Информационные средства и технологии», МФИ-2004, Т1. Москва, МЭИ, 2004. С.215-218.

32. Горшков А.А., Кохов В.А. Эффективность подструктурного подхода к анализу сходства двудольных графов. Тезисы докладов 11 международной НТК «Радиоэлектроника, электротехника и энергетика», Т1. М., МЭИ, 2005. С.332-333.

33. Кохов В.А., Незнанов А.А., Ткаченко С.В. Программные средства иерархического поиска в базах структурной информации. Тезисы докладов международной конференции «Информационные средства и технологии», МФИ-2005, Т2. Москва, МЭИ, 2005. С.83-86.

34. Кохов В.А. Модели и методы для анализа сходства структур систем с учетом сходства расположения фрагментов. Тезисы докладов научной сессии МИФИ-2006. ТЗ. Интеллектуальные системы и технологии. М. МИФИ. 2006. -С.144-145.

35. Незнанов А.А., Кохов В;А. Программный комплекс для анализа сходства структур систем. Тезисы докладов научной сессии МИФИ-2006. ТЗ. Интеллектуальные системы и технологии. М. МИФИ. 2006. — G.162-163.

36. Кохов В.А. Модели и методы анализа сходства графов для поиска структурной информации. Тезисы докладов. международной конференции «Информационные средства и технологии», МФИ-2005, Т2. Москва, МЭИ, 2005; С.79-82.

37. Незнанов A.A., Кохов В.А. Подсистема. АСНИ «Graph Model Workshop» для анализа сложности и сходства структур с учётом сходства расположения фрагментов. // Научная сессия МИФИ-2007: Сб. науч. трудов. Т.З, М. : МИФИ, 2007. С. 182-183.

38. Кохов В.А. Граф-модели для анализа сходства граф-моделей структур на основе их сложности. 11 Национальная конференция по искусственному интеллекту с международным участием. КИИ-2008: Труды конференции. В 3-х т. Том 2. М.: Физматлит, 2008. С.70-78.

39. Adamson G.W., Bush J.A. A Metod for the Automatic Classification of Chemical Strusture. //Inform.Stor.Ret., 9, pp. 561-568.

40. Bunke H., Sharer K. A Graph Distance Metric Based on the Maximum Common Subgraph. //Pattern Recognition Letters, vol. 19, no. 3-4, 1998, pp. 255-259.

41. Rundic M., Wilkins C.L. Graph Theoretical Approach to Recognition of Structure Similarity in molecules. //J. Inf. Comput. Sci.- vol.19, no.l. 1979. pp. 16-39.

42. WillettP. Modern Approach to Chemical Reaction Searching. Goneer. 1986.

43. Лебедев K.C. Компьютерные методы решения структурно-аналитических задач на основе банков данных по молекулярной спектроскопии (МС, ИК, ЯМР). Автореферат диссертации на сосикание ученой степени д.х.н.- Новосибирск, 1993.- 65с.

44. Лебедев К.С., Кохов В.А., Шарапова О.Р. и др. Опознание крупных структурных фрагментов неизвестного соединения с помощью поисковой системы по ИК-спектрам. //Сибирский химический журнал. 1993. Вып.1.- С. 50-56.

45. Девятая национальная конференция по искусственному интеллекту с международным участием. КИИ-2004: Труды конференции. В 3-х т. М.: Физматлит, 2004.

46. Ganter В., Wille R. Formal concept analysis. Springer. 1999. 285 p.

47. Финн В.К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф Бэкона Д.С. Милля // Семиотика и информатика, 20. -1983. - С.35-101.

48. Кузнецов С.О., Финн В.К. Распространение процедур ЭС типа ДСМ на графы. //Техн.кибернетика, 1988, №5, С.4-11.

49. Klein D. G. Chemical Graph-Theoretical Cluster Expensions. //Int. Journal Quantum Chem. 1986. S20. -pp. 153-173.

50. Алгоритмы и программы решения задач на графах и сетях //Нечепуренко М.И., Попков В.К., Кохов В.А. и др. Новосибирск: Наука, 1990. 515 с

51. Шрейдер Ю.А. Равенство, сходство, порядок. — М.: Наука, 1971. — 256 с.

52. Johanson М. A. A Review and Examination of the Mathematical Spaces Underlying Molecular Similarity Analysis. //Journal of Math. Chem., 1989, vol. 3. no. 2, pp. 117-146.

53. Кохов В.А. Методы анализа сходства систем с учетом расположения фрагментов. Тезисы докладов международной конференции «Информационные средства и технологии», МФИ-2003, Т1. Москва, МЭИ, 2003. С.213-215.

54. Кохов В.А. Концептуальные и математические модели сложности графов. М.: Издательство МЭИ, 2002. 160 с.

55. Грызунов А.Б. Разработка методов структурного различения графовых моделей дискретных систем. Автореферат дисс. . канд.техн.наук. — М.: МЭИ. -1987.-20 с.

56. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.

57. Визинг В.Г. Сведение проблемы изоморфизма и изоморфного вхождения к задаче нахождения неплотности графа. /Тезисы докл. III Всесоюзн. конф. по пробл. теорет. киб. Новосибирск, 1974. С. 124.

58. Бессонов Ю.Е. О решении задачи поиска наибольших пересечений графов на основе анализа проекций модульного произведения. //Вычислительные системы. Новосибирск, 1985. Вып. 112: Алгоритмический анализ структурной информации. — С.3-22.

59. Бессонов Ю.Е. Оценка трудоемкости поиска клик в графе с известной плотностью методом рекурсивного разбора. // Вычислительные системы. Новосибирск, 1984. Вып. 103: Алгоритмы анализа структурной информации. С.3-5.

60. Бессонов Ю.Е., Скоробогатов В.А. Об одном семействе схем рекурсивного разбора графов. // Вычислительные системы. Новосибирск, 1982. Вып. 92: Машинные методы обнаружения закономерностей анализа структур и проектирования. С.3-49.

61. Бессонов Ю.Е., Скоробогатов В.А. Обобщенные модульные произведения и структурное подобие графов. //Вычислительные системы. Новосибирск, 1985. Вып. 112: Алгоритмический анализ структурной информации. С.23-32. •

62. Грызунов А.Б., Кохов В.А. Метод сокращения перебора на основе учета симметрии при решении TVP-полных задач на графах //Моск.Энерг.ин-т. — М, 1987. 58 с. деп. ВИНИТИ, 18.08.87, №6029-В87.

63. Алгоритмические исследования в комбинаторике. Под ред. Фараджева И.А. — М.: Наука, 1978. 188 с.

64. Арлазаров B.JL, Зуев И.И., Усков А.В., Фараджев И.А. Алгоритм приведения конечных неориентированных графов к каноническому виду. // Журнал вычислит. мат. и мат. физ., 1974, Т.14, №3. С. 737-743.

65. Пролубников> А.В. Алгоритм поиска приближенного решения задачи проверки изоморфизма подграфов. // Математические структуры и моделирование: Сб. научн. тр. Под ред. А.К. Гуца. Омск: Омск. гос. университет, 2003. Вып. 10. — С. 59-66.

66. Грызунов А.Б., Кохов В.А. Эффективные алгоритмы изоморфного вложения и пересечения графов. // Тезисы докл. межвузовской конференции «Молекулярные графы в химических исследованиях». Калинин, 1990. — С. 15-16.

67. L.P. Cordelia, P. Foggia, C. Sansone, M. Vento, Performance evaluation of the VF Graph Matching Algoritmh, Proc. of the 10th ICIAP, IEEE Computer Society Press, pp. 1172-1177, 1999.

68. Messmer B.T., Bunke H., Subgraph isomorphism in polynomial time. II Technical Report TR-IAM-95-003, 1995. 33 p.

69. Messmer B.T., Bunke H., A decision tree approach to graph and subgraph isomorphism detection, Pattern Recognition, vol. 32, 1999. —pp. 1979-1998.

70. J. R. Ullmann. An Algorithm for Subgraph Isomorphism. II Journal of the Association for Computing Machinery, vol. 23, 1976,pp. 31-42.

71. Скоробогатов B.A., Хворостов П.В. Методы и алгоритмы анализа симмет-рий графов. // Алгоритмы анализа структурной информации, выпуск 103. Новосибирск, 1984.-С. 6-25.

72. Кохов В.А. Некоторые инварианты конечных графов и их применение. Диссертация . к.т.н. М. МЭИ. 1978.

73. Редуцированное представление

74. Pauline Markenscoff and Dwight Joe, Computation of Tasks Modeled by Directed Acyclic Graphs on Distributed Computer Systems:Allocation Without SubTask Replication, University of Houston, 1984

75. P. Foggia, C. Sansone, M. Vento. A Performance Comparison of Five Algorithms for Graph Isomorphism. II International Workshop on Graph-based Representation in Pattern Recognition, Ischia, Italy, pp. 188-199, 23-25 May, 2001.

76. Незнанов А.А. Методы и программные средства для различения расположения фрагментов графовых моделей систем. — Автореф. дисс. на соискание учёной степени к.т.н., М.: МЭИ (ТУ), 2005 г. 20 с.

77. Ибрахим А.Р, Джасим М.Р., Кохов В.А. Программный комплекс для структурного спектрального анализа ациклических графов. Труды 13-ой международной НТК «Радиоэлектроника, электротехника и энергетика», Tl. М., МЭИ, 2007.-С. 360-361.

78. Юб.Кохов В.А., Кохов В.В., Ибрахим А.Р. Система моделей для анализа сходства графов с учетом расположения цепей.// Вестник МЭИ, №5, 2009.- С.5-10.

79. Кохов В.А., Кохов В.В., Джасим М.Р. Графовые модели для анализа структурной сложности систем.// Вестник МЭИ, №1, 2010.- С. 103-116.

80. Искусственный интеллект: применение в химии. Пер. с англ. /Под ред. Т. Пирс, Б. Хони. — М: Мир. 1988. - 430 с.

81. Кохов В.А., Кохов В.В. Модели и методы анализа сходства сетей на основе их сложности. X международная научно-практическая конференция (ПФИС-2008). Труды конференции. Новосибирск, 2008. С. 253-258.

82. Десятая национальная конференция по искусственному интеллекту с международным участием. КИИ-2006: Труды конференции. В 3-х т. М.: Физматлит, 2006.

83. Ш.Кохов В.А., Ткаченко С.В. Исследование алгоритмов структурной информатики с помощью ППП «ПОЛИГОН-СТРИН». М.: Издательство МЭИ, 2005. -68 с.

84. Кохов В.В., Фальк В.Н. Структурная информатика: система моделей для анализа сходства орграфов. Труды 16-ой международной НТК «Радиоэлектроника, электротехника и энергетика», Tl. М., МЭИ, 2010. С. 350-351.

85. З.Кохов В.А. Граф-модели для визуализации расположения цепей в структурах. Тезисы докладов международной научно-технической конференции «Информационные средства и технологии», МФИ-2007, ТЗ. Москва, МЭИ, 2007. С. 69-72.

86. Джасим М.Р., Кохов В.А. Структурная информатика: система моделей для анализа сложности графов. Труды 16-ой международной НТК «Радиоэлектроника, электротехника и энергетика», Tl. М., МЭИ, 2010. С. 352-353.

87. Кохов В.А., Ибрахим А.Р., Кохов В.В. Система моделей для анализа сходства графов с учетом расположения цепей // Вестник МЭИ, №5, 2009. — С. 5-13.