Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Джасим Малатх Рахим

• Джасим Малатх Рахим
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Джасим Малатх Рахим

ВВЕДЕНИЕ.

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

Цель работы.

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

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

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

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

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

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

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

Публикации.

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

главам.

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

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат технических наук Джасим Малатх Рахим, 2010 год

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.