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

Ш347691!

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

Ибрахим Али Рашид

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

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

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

Я

7(3

Москва. 2009

003476919

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

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

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

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

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

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

математической геофизики Сибирского Отделения Российской Академии Наук (ИВМиМГ СО РАН) (Новосибирск)

Защита состоится 09 октября 2009 г. в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при Московском Энергетическом институте (Техническом Университете) по адресу: 111250, Москва, Красноказарменная ул., д. (ауд. f -/í>¿)

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

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

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

Автореферат разослан « $ » сентября 2009 г.

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

диссертационного совета Д 212.157.01

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

кандидат технических наук, доцент

Фомина М.В.

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

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

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

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

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

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

Особую роль методы прикладной теории графов играют именно в развитии информационных технологий (теории трансляции, оптимизации программ, организации сложных структур данных, визуализации данных, построении человеко-машинных интерфейсов и др.). Одним из основных классов задач прикладной теории графов является класс задач различения графов и различения расположения фрагментов графов. История развития методов решения задач различения графов насчитывает более 50 лет. В настоящее время в решении задач распознавания изоморфизма графов, распознавания изоморфного вложения графов и смежных с ними задач достигнут большой теоретический и практический прогресс. Но задачи поиска максимального общего фрагмента двух структур и на основе этого определение сходства структур, изучены намного слабее. Исследования, связанные с учетом расположения фрагментов в структурах актуализировались в конце 90-х годов прошлого века в связи с развитием приложений химической теории графов (¿ЯЛЯ-анализа, £Ш?й-анализа и др.), правдоподобных рассуждений, структурного распознавания образов, структурной лингвистики. Эти исследования шли в достаточно узких областях (например, большинство предложенных топологических индексов явно или неявно учитывали

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

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

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

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

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

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

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

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

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

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

Научная новизна исследования состоит в следующем:

1) предложены модели, характеризующие ациклические структуры систем с учетом расположения фрагментов, позволяющие:

a. Расширить и обобщить подструктурный подход к анализу сходства ациклических структур;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. Основные результаты диссертационной работы,

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

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

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

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

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

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

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

«Фрагмент -БазисСтруктурныхДескрипторов-Структура».

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

Во второй главе приведены теоретические основы подструктурного подхода (ПП) к анализу сходства графов. В ПП выделены две группы методов:

1. Методы, использующие максимальные общие фрагменты пары графов.

2. Методы, использующие базисы структурных дескрипторов.

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

Для определения метрических расстояний между графами используются подструктурные метрики (ЖУ-метрики):

1) );

2) А(СД)=1 Г(С)|+|£(е)!+| ]'\Щ\+\Е(т-2(! ПМСЩРМ| +|£(МУ(СЛ))|),

где МСБ - максимальный общий порожденный подграф, Л/СУ*" -максимальная общая подструктура (частичный подграф максимальный по кардинальному числу).

Для определения сходства графов используется коэффициент сходства:

М(С,й)=ц (А,В)= | МСР(в,Н) 12/( | в! х | н\),

и коэффгщиент несходства КЮ1{С,Н)=\Л - А/5/(С,Я).

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

Анализ теоретических основ подструктурного подхода и объемные вычислительные эксперименты по определению сходства (расстояний) графов и АС:

• проанализировано 30399 графов и более 335000 АС;

• решено 5751575 задач для определения максимального общего

подграфа для всех пар графов и АС,

привели к выделению следующих недостатков подструктурного подхода.

1. Малая «чувствительность» к различению орграфов, находящихся на расстоянии 1. На расстоянии 1 от заданного орграфа находятся все орграфы, которые можно построить добавлением, либо удалением дуги или одиночной вершины.

2. Жесткая детерминированность - полученное значение метрики или коэффициента сходства (несходства) нельзя далее уточнять.

3. Подход не учитывает наличие значимых фрагментов, их расположение и взаимное расположение в структуре орграфа.

4. Подход не учитывает качественных характеристик максимальных сбщ^х фрагментов (например, их сложность).

5. Узкий диапазон пространства для проведения кластеризации.

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

Задача 1. Наибольший общий слабосвязный подграф двух АС (Л/СИ'.?).

УСЛОВИЕ. Заданы два орграфа без контуров Сг\, С/2 и положительное целое число К.

ВОПРОС. Существуют ли С,ь С2*с^С 2 такие, что они являются слабосвязиыми подграфами, соответственно в С\, Со и

IУ(6, *)1 = ИС2*)| Ж и С, *« Ог *?

Задача 2. Наибольший общий слабосвязный фрагмент двух орграфов (ЛЯ л /-).

УСЛОВИЕ. Заданы два орграфа без контуров ОС- и положительное целое число К.

ВОПРОС. Существуют ли Ог*с 'Сг такие, что они являютои

слабосвязиыми фрагментами, соответственно в С ], С 2 и

\Е(в ] *)1 = 1е(6 2 *)! Ж и с, ** в 2 *?

На рис.1 приведен пример результата решения задачи 1, полученный подсистемой «Сходство ациклических структур» в АСНИ «бМИ'».

Рис. I. Вид окна с анимационной демонстрацией всех максимальных изоморфны* пересечении по слабосвязнъш подграфам двух АС в АСНИ чС

На основе обобщения результатов анализа задач определения общего фрагмента (С/7), возникающих в теоретических и прикладных исследованиях, выделен набор из 4 параметров (табл. 1) для классификации задач СР .

Таблица 1. Параметры классификации задач определения общего фрагмента орграфов

№ Параметр | Смысл параметра Виды значений параметра

1 р 1 Вид соотношения частей в орграфах, 1 которыми являются общие фрагменты

2 SI Вид результата по количеству общих фрагментов Одно любое, все, все неизоморфные С/"

3 | С j Вид соотношения CF по типу связности в АС Слабо связный - слабо связный; односторонне связный -односторонне связный

4 Neig ! Окрестность точного решения А=1..3

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

Neig\=mах( \Vifi }-Д; Л^2=тах( |£(/)1 )-А, где А - целое число.

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

(1) вид соотношения фрагментов/],^ как трех частей С],С у,

(2) величину окрестности А (Л-0 - точное решение; Д>0 - решение в заданной окрестности);

(3) вид результата по числу решений (одно; все);

(4) вид результата по типу связности (к) в анализируемых АС (слабо связные (к= I), односторонне связные (&"=2));

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

Далее приведен обзор по методам решения задач определения МС5 и МСР, выделены два основных подхода: (1) алгоритмы на основе использования клик в модульном произведении анализируемых графов; (2) алгоритмы на основе метода монотонных расширений частичных решений (ММРЧР), представляющего собой направленный перебор по достройке начального (возможно пустого) решения до максимально возможного с учетом симметрии анализируемых графов, инвариантов, позволяющих отбрасывать бессмысленные достройки, и специфики класса анализируемых ГМС. Приведен сравнительный анализ и выделено, что наиболее перспективным с точки зрения разработки эффективных алгоритмов является метод монотонных расширений частичных решений так как:

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

2. Есть возможность задания частичного решения.

3. Он на единой методологической основе конструктивного перечисления фрагментов в топологии анализируемых орграфов, имеет развитие в методологию решения шести из семи классов базовых задач СС-анализа систем.

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

Алгоритмы определения общих фрагментов, основанные на ММРЧР, и их программные реализации разработаны автором и внедрены в АСНИ «ОМТ¥». Они позволяют работать с ациклическими структурами, имеющими веса ка вершинах, что делает их широкодоступными для применения при решении задач в различных прикладных областях, например, при семантическом поиске документов в базах документов.

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

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

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

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

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

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

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

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

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

Далее предложен метод построения цветных (сдр-модели) и скелетных (cgp-ыoдeля) трансграфов путей для АС, как класса ¿--моделей, позволяющих:

1) Наиболее эффективно анализировать сходство с учетом расположения путей в АС.

2) Визуализировать расположение цепных фрагментов АС на основе диаграммы АС.

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

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

Далее подробно рассмотрен класс ¿-моделей как основы для построения систем базисных моделей (¿-моделей), позволяющих наиболее эффективно решать задачи анализа сходства АС. Приведен переход от класса ¿-моделей к классу Ь-моделей АС. Рассмотрена система подклассов выделенного класса. Каждый из подклассов приводит к постановкам новых видов задач исследования сходства АС. На рис. 2 приведен пример трех видов граф-моделей для одного из деревьев с числом вершин 5.

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

полиномиальная вычислительная сложность для деревьев и приведены экспериментальные оценки вычислительной сложности алгоритмов построения cgp- и ^-моделей. Время работы алгоритмов их построения прямо пропорционально количеству добавляемых в 1раф-модель вершин-путей и поэтому в общем случае экспоненциально возрастает с увеличением длин путей, анализируемых АС, симметрия которых отражается в с^р-моделях. Результаты анализа оценок алгоритмов показывают высокую эффективность работы процедуры построения трансграфов путей для средних по сложности планарных орграфов без контуров. Время работы практически линейно растёт с ростом числа путей. Наибольшая эффективность достигается на графах-деревьях и орграфах-деревьях, для которых разработаны специализированные алгоритмы. Для различных семейств ациклических структур приведены оценки эффективности алгоритмов построения Ь-моделей. Показана эффективность построения ¿-моделей для деревьев на основе создания специализированных алгоритмов.

1>ис. 2.

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

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

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

В четвертой главе рассмотрены 3 метода, расширяющие классический подструктурный подход к анализа сходства и повышающие эффективность его применения для АС:

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

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

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

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

Далее приведена классификация задач анализа сходства двух АС на основе подструктурного подхода. В табл. 2 приведены обозначения базовых задач анализа сходства.

Таблица 2.

N АЧ N2 Обозначение Содержание задач

1.1.1 СО. Сходство на основе связного СРтипа слабое-слабое вида П-П

1.1.2 ОО.^'Ог Сходство на основе связного СЕ типа ОД-ОД вида П-П

1.1.3 Сходство на основе связного СТЧипа слабое-слабое вида П-Ф

1.1 1.1.4 ВО^п^Ог Сходство на основе связного СТ типа ОД-ОД вида П-Ф

1.1.5 ПО, Сходство на основе связного СУ типа слабое-слабое вида Ф-П

1.1.6 Сходство на основе связного СТ'типа ОД-ОД вида Ф-П

1.1.7 ВС/'п^Сг Сходство на основе связного СУ типа слабое-слабое вида Ф-Ф

1 1.1.8 Пв/пп'г02 Сходство на основе связного С^' типа ОД-ОД вида Ф-Ф

1.2.1 ЛО/пд/Ог Сходство иа основе связного Д-СТ"типа слабое-слабое вида П-П

1.2.2 Сходство на основе связного Л-СТтипа ОД-ОД вида П-П

1.2.3 ДОД-чЛг Сходство на основе связного Л-СТтипа слабое-слабое вида П-Ф

1.2 1.2.4 ■ОС/пл»/^; Сходство на основе связного Д-С^типа ОД-ОД вида П-Ф

1.2.5 •ОС?! '"п^С?; Сходство на основе связного Д-С'/Чипа слабое-слабое вида Ф-П

1.2.6 Сходство на основе связного &.-СЕтипа ОД-ОД вида Ф-П

1.2.7 Сходство на основе связного Д-СЕ типа слабое-слабое вида Ф-Ф

1.2.8 оо/п^Ль Сходство иа основе связного Д-СУтипа ОД-ОД вида Ф-Ф

Подробно рассмотрен первый из новых методов анализа сходства. Он расширяет возможности подструктурного подхода на основе использования дополнительной к размеру МСБ информации (число всех максимальных изоморфных пересечений двух АС, число канонических максимальных изоморфных пересечений). Далее используются характеристики, позволяющие учитывать качественный состав МСЗ (например, индексы и вектор-икдексы сложности МС5>). На основе объемных вычислительных экспериментов по данному методу сделан вывод, что следует разрабатывать и другие методы к анализу сходства АС, желательно с большим значением чувствительности различения пар АС, анализируемых на сходство, чем при первом методе.

Далее предложена и рассмотрена система методов анализа сходства АС с использованием трансграфов путей, построенных с учетом длин путей (0-1; 0-2; 0-3; ...;(0-(р-1))) исходной АС. Эти методы, используя поиск максимального общего подграфа для трансграфоз, впервые позволяют учитывать расположение путей разных длин в АС. Появилась возможность анализировать: (1) тенденции изменения сходства и выделять границы стационарности значений сходства при увеличении длин путей; (2) сходство АС относительно выделенного фрагмента в АС. Эти возможности программно реагазованы автором в виде подсистемы «СС-анализ ациклических структур» в АСНИ

«вмж».

Данный подход на основе системы ^-моделей позволил ввести и использовать новые характеристики для исследования сходства АС: (1) среднее расстояние между АС относительно страт ^-моделей; (2) индекс среднего сходства между АС относительно страт ^-моделей.

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

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

Третий из новых предложенных методов использует построение ¿-моделей и поиск их максимальных общих фрагментов, ¿-модели представлены матрицами достроек помеченных фрагментов АС до фрагментов, изоморфных элементам базиса путей, поддеревьев и др. Они позволяют при расширении базиса все более и более точно характеризовать расположение фрагментов в АС. На основе их максимального общего фрагмента легко ввести меру попарного расстояния или сходства АС. Приведен алгоритм построения ¿-моделей, позволяющих характеризовать расположение путей в базисе путей. На основе объемных вычислительных экспериментов показано, что исследование сходства на основе ¿-моделей является наиболее эффективным и чувствительным методом из всех рассмотренных методов, основанных на подструктурном подходе. Данный метод позволяет эффективно анализировать сходство АС с числом вершин до 400-600 и при этом учитывать расположение

путей в АС. Для деревьев и корневых растущих ордеревьев число Еерш;и-: возрастает до 5000.

На основе объемных вычислительных экспериментов (АС с числом вершин от 3 до 8 (более 240000)) приведены результаты сравнительного анализа по четырем методам анализа сходства. Рассмотрены: (I) задачи определения сходства расположения фрагментов в АС и методы их решения на основе ¿-моделей; (2) метод решения задачи определения сходства расположения фрагментов на основе ¿(¿»/-моделей, позволяющий при некоторой потере точности существенно повысить эффективность анализа сходства.

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

1600000 , 1400000 -1200000 -1000000 -800000 600000 -400000 200000 о

250 500 750 1000 1250 1500 1750 2000 2250 2500 | Рис. 3.

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

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

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

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

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

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

3. Ограничения на значения инварианта и коэффициента сходства. Исходная база АС не вменяется в процессе иерархического поиска.

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

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

Многокритериальный структурный поиск реализуется в АСНИ путём выбора на очередном этапе другой АС в качестве шаблона поиска.

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

Эффективная реализация базовых алгоритмов сравнения АС позволяет за приемлемое время (менее минуты на одну АС на компьютере с процессором AMD Athlon 64 3000+ и 1 ГБ оперативной памяти) обрабатывать АС следующего порядка: (1) при полной идентификации - до 1500 вершин; (2) при частичной идентификации - до 700 вершин; (3) при подструктурном сходстве -до 80 вершин; (4) при приближённой характеризации время определяется видом используемых ¿-моделей. Например, при использовании полного структурного спектра в базисе путей (цепей) малых длин (от 0 до 6) - до 500 вершин. Так например, при поиске в базе из 237318 АС при использовании числа цепей с длинами от 0 до 3 было получено 1 ] 526 АС при границе сходства

95%. При использовании системы вида

Р0-2 (95%)->А-2 (98%)->/><м (98%)-^ qP0. г (95%)->Л еЛи (92%)->Р,0-з сР<м (98%) 11526 2143 -> 183 -> 43 -»19 -» 3

в конечном итоге было выделено 3 АС при границе сходства 98%.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать /. 09< 09,", Зак. Тир. 100 П.л. 1,25

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

ВВЕДЕНИЕ.

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

Цель работы.

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

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

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

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

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

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

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

Публикации.

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

главам.

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) определять сходство расположения путей и классов путей.

ЗАКЛЮЧЕНИЕ

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

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.