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

• Ибрахим Али Рашид
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Ибрахим Али Рашид

ВВЕДЕНИЕ.

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

Цель работы.

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

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

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

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

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

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

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

Публикации.

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

главам.

1. ОБЗОР ОСНОВНЫХ ПОДХОДОВ К АНАЛИЗУ СХОДСТВА ГРАФОВЫХ МОДЕЛЕЙ СИСТЕМ.

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

1.2. Основные теоретические результаты по анализу отношений толерантности.

1.3. Алгебраическое сходство и математические пространства, используемые в анализе сходства

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

1.4.1. Краткий обзор подходов.

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

C. Частичное упорядочение графов относительно выбранных стандартов.

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

Введение диссертации (часть автореферата) на тему «Разработка методов и программных средств для анализа сходства ациклических структур»

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

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

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

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

Концепции «подструктура» и «подсистема» являются основой для изучения теорий и теоретических знаний. Концепция подструктуры является такой значимой, например, в химии органических соединений, что для систематизации рассмотрения природы химических структур и подструктур были привлечены методы теории графов и создана химическая теория графов. Как отмечено в [5] понятие подструктура дает естественный подход к сложной природе химического соединения. Анализ сложности структур и разнообразие несходства и подобия в больших объединениях структур сделали необходимым развитие и расширение концепг^ий под структурной характеризации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанные программные средства используются в научных исследованиях

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

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

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

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

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

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

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

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

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

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

Публикации

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Ибрахим Али Рашид

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

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

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

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

4. На основе анализа двух основных подходов к решению задач определения МОФ ГМС выделен метод монотонных расширений частичных решений как наиболее перспективный для разработки эффективных алгоритмов и дающих возможность получать точный или близкий к точному результат за ограниченное время поиска решения. На его основе разработаны алгоритмы и программы (в среде Borland Developer Studio2006, расширения выполнены в виде DDL библиотеки.) для решения базовых задач определения МОФ двух АС и определены экспериментальные оценки вычислительной сложности алгоритмов по оригинальной научной методике (на средних по сложности АС из разных семейств и по разным сценариям исследования).

5. Впервые предложен метод расширения возможностей 1111 на основе использования более полной и наряду с количественной также и качественной информации (индексы сложности всех МОФ) при определении МОФ двух АС.

6. На основе использования двух классов структурных инвариантов графов (§- и и ¿-модели) применена наиболее общая концепция подструктурной характериза-ции для АС позволившая:

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

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

• создать эффективные алгоритмы анализа сходства и повысить размер анализируемых на сходство АС

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

7. Разработаны алгоритмы и их программные реализация для построения ¿-моделей и ¿-моделей. Приведены экспериментальные оценки вычислительной сложности построения моделей. Установлено, что на основе использования Ь-моделей и ¿(¿)-моделей можно эффективно анализировать сходство АС с существенным расширением пространства кластеризации АС (по сравнению с 1Ш) и числами вершин до 600, в то время как 1111 позволяет анализировать сходство АС с числом вершин до 50.

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

9. Проведенные объемные вычислительные эксперименты с использованием АСНИ «ОМТУ» позволили получить оригинальные научные результаты определения сходства АС с учетом расположения фрагментов:

• для всех деревьев с числом вершин от 3 до 17 (более 31 ООО) с учетом расположения цепей и поддеревьев;

• для всех орграфов без контуров с числом вершин от 3 до 8 (более 250000) с учетом расположения путей;

• и результатов определения сходства расположения фрагментов в АС:

• для цепей деревьев с числом вершин от 3 до 17;

• для путей орграфов без контуров с числом вершин от 3 до 7.

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

ЗАКЛЮЧЕНИЕ

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

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

1. Перспективы развития вычислительной техники./ под ред. Ю.М. Смирнова. Кн. 1-2. М.: Высшая школа, 1989.2.11-ая национальная конференция по искусственному интеллекту с международным участием. КИИ-2008: Труды конференции. В 3-х т. М.: Физматлит, 2008.

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

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

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

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

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

7. Химические приложения топологии теории графов / Ред. Р. Кинг, М.: Мир. — 1987. С. 222-235.

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

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

10. Willett P., Willett J. Similarity and Clustering in Chemical Information Systems. — John Wiley & Sons, 1987.

11. M. Randic. Similarity Based on Extended Basis Descriptors. // J.ChemJnf Comput. Sei. 1992, vol. 32, - pp. 686-692.

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

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

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

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

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

17. Кохов B.A., Грызунов А.Б., Картовицкий A.JI. 111111 для автоматизированного исследования сходства и сложности молекулярных графов.Тезисы докл. IX Всесоюзной конференции «Химическая информатика».Черноголовка. 1992. С. 132133.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40. Кохов В.А. Методы анализа сходства графов и сходства расположения цепных фрагментов в графе. // Научная сессия МИФИ-2007: Сб. науч. трудов. Т.З, М. : МИФИ, 2007.-С. 180-181.

41. Кохов В.А., Незнанов A.A., Ткаченко C.B. Современные подходы к анализу сходства структур систем и их реализация в АСНИ «GRAPHMODEL WORKSHOP». Тезисы докладов научной сессии МИФИ-2008. Т10. Интеллектуальные системы и технологии. М. МИФИ. 2008. С.77-78.

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

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

44. 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.

45. 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.

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

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

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

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

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

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

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

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

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

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

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

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

58. Sean М. Falconer and Dmitri Maslov. Weighted hierarchical alignment of Directed acyclic graphs, University of Victoria, University ofVaterloo.

59. Simon Handley. On the Use a Directed Acyclic Graph to Represent a Population of Computer Programs, Computer Scinece Department Stanford University, 1994.

60. 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.

61. Siome Goldenstein, Chtistian Vogler, Dimitris. Metaxas Directed Acyclic Graph Representation of Deformable Models, University of Pennsylvania,2003.

62. Margaret Mitchell. Use of Directed Acyclic Graph Analysis in Generating Instructions for Multiple Users, Language Technology Group Nacquarie University,Sydney, 2001.

63. Simon Handley. On the Use a Directed Acyclic Graph to Represent a Population of Computer Programs, Computer Scinece Department Stanford University, 1994.

64. Stan Liao, Kurt Keutzer, Steven Tjiang. A New Viewpoint on Code Generation for Directed Acyclic Graphs, Synopsys,Inc.,1998.

65. Henry F. Korth. The Optimal Locking Problem in a Directed Acyclic Graph, 1981.

66. Jelle J. Goeman, Ulrich Mansmann. Miltiple testing on the directed acyclic graph of gene ontology, Leiden University Medical Center, Dept. of Medical Statistics,2006.

67. Jason Cong, Zheng Li, Rajive Bagrodia. Acyclic Midti-Way Partitioning of Boolean Networks, Department of Computer Science University of California, Los Angeles, 1994.

68. P. Бел л май. Динамическое программирование.-М.: Иностранная литература, 1960.401 с.

69. Химические приложения топологии и теории графов. Пер с англ. /Под ред. Р Кинга. — М.: Мир, 1987. С.259-265.

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

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

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

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

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

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

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

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

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

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

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

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

82. Незнанов A.A., Кохов В.А. Алгоритмизация решения переборных задач анализа графов. М.: Издательство МЭИ, 2006. 80 с.104. www,graphmodel. сот.

83. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. — Новосибирск: изд-во ИМ СО РАН, 1999.