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

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

Ополченов Алексей Викторович

МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА СОЗДАНИЯ ЭКСПЕРТНЫХ СИСТЕМ ПРИНЯТИЯ РЕШЕНИЙ

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

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

наук

Москва - 2003 г.

Работа выполнена на кафедре Математического моделирования Московского энергетического института (Технического университета).

Научный руководитель

доктор технических наук, профессор Фролов Александр Борисович

Официальные оппоненты

доктор технических наук, профессор Гашков Сергей Борисович доктор технических наук, профессор Еремеев Александр Павлович

Ведущая организация

Московский Государственный Горный Университет

Защита состоится «24 » декабря 2003 г. в 1600 ч. на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (Техническом университете) по адресу: 111250, Москва, Красноказарменная ул., 17 (ауд. Г-306).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).

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

Автореферат разослан « » 2003 г.

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

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

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

профессор С . Ладыгин И.И.

п.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

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

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

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

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

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

ш v ишишщш. Схема имеет опРОС. НАЦИОНАЛЬНАЯ|

библиотека {

. там!

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

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

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

...м»«-, .м ;

I ни '.' ;

I ? |

'• ..« «<• ;

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

Этот подход реализован в настоящей работе на основе развиваемой с участием автора теории распознавания частично-упорядоченных объектов1 2 3 4, методами которой синтезируются информационные среды для вычисления значений k-значной функции, и теории поиска и хранения информации5, дающей метод получения нетривиальных верхних оценок времени поиска решения в таких средах.

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

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

Основные направления работы сводятся к решению следующих задач:

1 Фролов А Б, Фролов Д А, Яко Э Программируемые функциональные схемы для распознавания частично упорядоченных объектов Известия АН СССР, сер Техническая кибернетика №5, 1597.

1 Фролов А.Б, Яко Э Алгоришы распознавания частично упорядоченных о&ъекгов. Известия АН СССР. сер. Техническая кибернетика №5,1990

' Ополченов А В, Фротов А Б Синтез и верификация систем принятая решений функционального типе И Известия Российской Академии наук Теория и системы управления -2002-№5-С 101-110

4 Opolchenov А V, Trolov А В Synthesis and verificaron of fiinctional systems of a functional type // Journal of Computer and Systems Sciences International Proceedmgs ofRussian Academ> oí Science Journal of Control Syítetrs and Computéis 2002 ■ № í - С 101-110

5 Гасанов Э Э, Кудрявцев В Б Теория хранения и поиска информации. - М : ФИЗМАТЛИТ, 2002

-6- разработка алгоритмов и операций исчисления граней;

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

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

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

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

Методы исследования

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

Достоверность научных результатов

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

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

Новыми являются:

1) Алгоритмы и операции исчисления граней и их применение для верификации непротиворечивости и полноты функциональной модели СПР.

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

3) Алгоритмы вычисления значения функции £-значной логики, имеющие нетривиальные верхние оценки сложности.

-74) Методика создания экспертных систем с оцениваемым временем принятия решений.

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

На основе теоретических результатов работы разработан программный комплекс РСКЖЕХ 2002, поддерживающий методику создания экспертных систем принятия решений функционального типа в задаваемой предметной области.

Разработанный на языке высокого уровня С++ программный комплекс РООЯЕХ 2002 имеет модульную структуру, что делает доступным встраивание его функциональных компонент в другие проекты.

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

Программный комплекс внедрен в Федеральной Системе Учета и Контроля Ядерных Материалов.

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

Программный комплекс РОСЖЕХ 2002 использован в ЦНИИ Атомин-форм при разработке АРМ подготовки сводной отчетности для выявления несовместимых сочетаний ядерных материалов в отчетных партиях. А также в учебном процессе МЭИ в курсе новых информационных технологий для магистров. Работа выполнена в рамках НИР № 1022002 «Анализ и разработка принципов алгоритмизации и верификации интеллектуальных систем функционального типа» кафедры ММ.

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

Основные положения и результаты диссертации докладывались и обсуждались:

• на 5-й международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (г. Москва, 1999 г.)

• на международном форуме информатизации МФИ-99 Информационные средства и технологии (г. Москва, 1999 г.)

• на Ю-й международной конференции «Проблемы управления безопасностью сложных систем» (г. Москва, 2002 г.)

• на 9-й международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (г. Москва, 2003 г.)

Публикации.

По теме диссертации опубликовано 6 печатных работ

Структура и объём работы.

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

СОДЕРЖАНИЕ РАБОТЫ.

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

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

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

Гранью декартова произведения конечных множеств

С=СххС2х...хС„ (1)

называется множество наборов, образующих декартово произведение

а=ег1Х{72х...ха-„ (2)

где сг.с С/, 1=1,...,и, обозначаемое (аи ет2,..., ег„)

Предполагаем, что декартово произведение (1) является решеткой. Мы будем рассматривать только такие грани, где множества а, являются подре-шетками решеток С,-. Тогда каждое такое непустое множество как конечная решетка имеет как верхнюю Sup(o;) так и нижнюю Inf(er,) универсальные границы, и элементы а, векторов а можно представлять в виде пар (сДс,2) элементов множества С„ c/=Inf(o}), c(2=Sup(o;), это дает эффект упрощения описания модели. В этом случае наборы (с\,сг,...,сп) и (с2,с22,...,с2) - нижняя Inf(cr,) и верхняя Sup(rr,) универсальные границы грани а.

Всякое непустое подмножество AfeCiXC2X...xC„ можно представить как объединение некоторых его граней, составляющих в этом случае покрытие этого множества.

Отношение частичного порядка для k-значных наборов на множестве С\ х С2 X ... X С„ описывается следующим образом:

{с\, сг.....с„')<(с|2, с22,..., с„2), если с,'< с,2, Vz'=l,..,n.

Будем также использовать бинарное отношение ч такое, что

(с/, сг1,..., с„1) Ч (с2, Сг,..., с„2), если

а) (ci\c2,...,cn)=ici2,c22,...,cn2) или w((c,1 ,с2 ', • • • ,с„' ))<w((c 2,с2,... ,сп2))

или

б) (с\ ,сг,...,с п)Ф(с2,с2,... ,с„2), w((c i1 ,С21,..., с„1 ))=w((c 2,с2,...,с2)) и 3 hSn V i<k=> с,'= с2, ск1<с2, где w(c\,c2,...,cn) = - «вес» набора.

Примечание. В соответствии с определением наборы (с\,сг,..-,Сп), (с2,с2,...,с2) равного веса упорядочиваются по отношению ■< лексикографически.

В главе доказаны следующие утверждения:

Утверждение 1. Введенное отношение ■< является отношением частичного порядка.

Утверждение 2. Отношение ■< является отношением линейного порядка.

Утверждение 3. Отношения < частичного порядка и ■< линейного порядка согласованы, а именно

(с,\ с2\..„ с„1) < (с,2, С2\..., С„2) => (сЛ с21,..., С„'Ь(С12, с22,..., с„2).

Утверждение 4. Введенное на множестве граней отношение является отношением частичного порядка.

Утверждение 5. Отношение < на множестве граней является отношением линейного порядка.

Примечание. Отношения ч и с не согласованы.

Исчисление граней определяется как алгебраическая система

(£; П, *,с, (3)

где Ц - множество всех граней декартова произведения (1), являющихся его подрешетками,

П - операция пересечения граней,

/

* - операция сопряжения граней по /-й компоненте, г = 1

с - отношение вложенности граней,

ч - отношение топологического порядка на множестве граней.

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

С использованием исчисления граней реализован аналог алгоритма Блэка-Порецкого для построения сокращенного покрытия по имеющемуся произвольному покрытию.

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

Рассматриваются множества объектов или ситуаций, описываемых п-мерными векторами (с\,съ ■■■,с„), компоненты с, которых соответствуют тем или иным признакам объекта или ситуации и принимают значения из конечных упорядоченных множеств С„ / = 1,...,п возможных значений, предполагается, что они являются решетками, тогда на их декартовом произведении можно определить решетку.

Некоторым векторам (сьс2, • ■ ■, с„) е С|ХС2Х... хС„ приписываются значения Г), г2,..., гк, соответствующие тем или иным действиям или наборам (спискам) действий СПР. Тем самым определяется некоторая, вообще говоря, частичная функция/:СьСъ...,Сп-^Я, где Л={г1,г2,...,г*}, - решающая функция СПР с областью определения Гт'УсС^хСгХ...хС„.

«Близким» наборам значений признаков в реальных системах, как правило, соответствуют одинаковые значения. Это позволяет использовать обобщенное представление подмножеств рассматриваемых пар в виде одной пары

((стЬ02,---,а-я),г), (4)

где (сг],сг2,.. ,,ст„) - грань декартова произведения (1).

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

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

Р = {((т,,,^.....<0> г<)> ' = 0,1,(6)

и характеристической функции в виде множества

(7)

СПР, представляемые математическими моделями рассмотренного вида называются системами функционального типа и представляются парами вида (^ X), т.е. описаниями (6), (7).

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

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

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

Модифицированный алгоритм разделения, отличается от базового алгоритма тем, что применяется к обобщенному графику отображения и формирует решающее правило в виде подграфика отображения, совпадающего с подграфиком, который формируется базовым алгоритмом (при детальном задании полного отображения) и отличающегося от этого подграфика в случае неполноты исходного отображения. В последнем случае реализуется отображение во множество ЛЦКО}, Я - множество возможных решений, 0 - символ неопределенности. Модифицируемый алгоритм Ам:

1. Пары вида (о, у), где V = у(1п1 и) исходного описания (2.3) решающей функции размещаются в списке Ь, который линейно (-<) упорядочивается по элементам <т из образующих его пар, образуется пустой список ЬЛЦ) и список ЬМ = 1.

2. Пока список ЬМ не пуст, для его головного элемента (а, у) списка Ь по правилам базового алгоритма Ам вычисляется значение

7= Ц1А(ЬА(/), 1пДа)), где у/А - определенная для алгоритма А функция, и выполняется одно из следующих действий:

а) если V = х , то для каждого элемента (o",v")eL такого что се о" и v'Vv в список LJf) включается элемент (с, v"), в список LM включаются пары вида ((с, Supo"), v") (или ((с,с),0)), соответствующие тем элементам с из множества До) минимальных элементов дополнения грани в верхнем конусе ее инфинума, для которых найдется элемент (о*, v') списка L, такой что с erf, но с Ф Info* (или если для всех & с g cf).

б) если v*.xHv*0,To список L изменяется как описано в п. а). Если при этом v Ф v то в конец списка LÀ(f) включается пара (Info; <pA{LA(f), Info; v), здесь (рл - определенная для алгоритма А функция.

в) если v Ф х, v ф v и v = 0, то список LA{f) изменяется как описано в п. б) и в список LM включаются пары (0(с, cf), v')), соответствующие тем элементам с из множества 1(d), для которых найдется грань d, представленная в некотором элементе (d, v') исходного списка L, такая, что с < Supo1, но не выполняется условие (Info'<c)&(c<Info'), где О - операция ограничения граней.

После этого текущий элемент (<т, v) удаляется из списка LM и список упорядочивается, при этом из двух или нескольких одинаковых его элементов оставляется только единственный экземпляр.

3. Действия, аналогичные описанным в п.п. 1, 2 выполняются применительно к исходному описанию характеристической функции.

Для формирования решающего правила в виде списка LA(f) требуется лишь однократная обработка элементов исходных предварительно упорядоченных списков LfViLx.

Алгоритм Ra распознавания (принятия решений) использует в качестве решающего правила списки LÀ(J) и ЬА(х), сформированные модифицированным алгоритмом разделения А.

1. Номер класса элемента а определяется как значение v'e R U {0} последнее пары (a', v') списка LA(f) такой, что а' < а или как 0, если таких пар в списке La if) нет.

- 142. Если получено значение V = 0, то к списку Ьл{/) после удаления из него пар со значением 0, применяется базовый алгоритм, вырабатывающий решение V, и возвращается сообщение [у"], где квадратные скобки предупреждают о возможной неточности решения. 3. Если в п.1 получено значение V Ф 0 то аналогичным образом по списку ЬА(х) вычисляется значение характеристической функции. Если оно есть О, то возвращается сообщение [у'], где квадратные скобки предупреждают о возможной неточности решения, иначе возвращается решение V.

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

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

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

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

Структура леса образуется путем добавления в некоторые элементы (а, у) списка ссылок *(а, у) на один из предшествующих элементов (а', у') этого

списка, *(а, у) = (а', у')*- Соответствующая структура обозначается Список получается из структуры удалением таких ссылок.

Для леса определены операции построения леса, отношения частичного и линейного порядка, а также ряд операции поиска. На основе данных операций и отношений разработаны шесть алгоритмов распознавания, сокращающих перебор за счет локализации поиска, проведена оценка их сложности. Для оценки сложности используется модель информационного графа6. Множество запросов X представляет собой множество всех возможных наборов из области определения, т.е. X = {(с1( съ с„) е С, X С2 х ... х С„}.

Множество записей У представляет собой множество возможных решений системы, объединенное с нулем, означающим, что решение для данного набора признаков экспертами предусмотрено не было, т.е. У = Я и {0}

Задачу распознавания можно описать как задачу информационного поиска 1 = <Х, V, р5>, где Ус У,

х р$у О ((аи у)еи-, уеУ)&(ау<х)&ЫЗуШа>; /)е£л /еУ)&(ау<х) &(лу<яу))),

х рл'О О -.(Зу)((ау,>')б1ЛуеУ)&(ау<х)) или

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

В пятой главе приводится описание программного комплекса РОСЖЕХ 2002 и созданной на его основе методики создания СПР функционального типа для задаваемой предметной области.

Программно-инструментальный комплекс РОСЖЕХ 2002 предназначен для экспериментального исследования СПР функционального типа и создания таких систем для различных областей применения.

й Гасанов Э Э, Кудрявцев В Б Теория хранения и поиска информации. - М* ФИЗМАТЛИТ, 2002

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

В качестве языка представления описания функциональных систем в обменном формате может быть выбран, например, extensible Markup Language (XML).

Экспертные системы на основе POOREX 2002 могут создаваться экспертами предметной области в интерактивном режиме. При работе с программой, специалисты должны составить концептуальную модель предметной области, чётко представляя функцию F из множества возможных реальных

j г

ситуаций во множество решений, а также область определения этой модели, т.е. предикат Хна множества всех ситуаций. Для этого выбирается набор атрибутов и множества возможных значений для них. Эти множества упорядочиваются, что позволяет задавать их «отрезки», наборы таких «отрезков» по всем атрибутам задают «грани» области определения. Функция F описывается множеством пар (<грань>,<решение>), при этом каждая реальная ситуация должна присутствовать хотя бы в одной грани. Предикат X описывается как множество граней, включающих все реальные ситуации и не содержащих иных ситуаций. Программа проверяет свойства функциональности и полноты исходного описания и упрощает его. Для заданной ситуации она формирует решение как значение функции F, если- ситуация учитывалась при задании этой функции, иначе подсказывается прогнозируемое решение. Прогнозирование осуществляется на основе имеющейся реально частичной упорядоченности описаний ситуаций как наборов значений признаков и алгоритмов распознавания частично упорядоченных объектов. Программа указывает дескрипторы, которые соответствуют анализируемой ситуации, и которые определяют решение для нее, что в определенном смысле позволяет объяснить принимаемое решение.

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

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

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

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

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

Использование результатов диссертации подтверждено документально.

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

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

Эта цель достигнута на основе следующих теоретических результатов.

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

-182. Обобщенные описания функционального соответствия (обобщенные ¡рафики отображения), составляемые экспертами с использованием интервалов (граней) пространства ситуаций.

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

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

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

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

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

Поддерживаемая комплексом РООЯЕХ 2002 предложенная в диссертации методика синтеза и верификации систем принятия решений функционального типа применена для синтеза реальных систем.

Результаты компьютерных экспериментов, подтверждают экспериментальные теоретические оценки сложности алгоритмов поиска в синтезируемых информационных средах.

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

Также в заключении сформулированы направления дальнейших исследований.

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

[1] Ополченов A.B., Фролов А.Б. Синтез и верификация систем принятия решений функционального типа // Известия Российской Академии наук. Теория и системы управления. - 2002 - № 5 - С. 101-110.

[2] Opolchenov A.V., Frolov A.B. Synthesis and verification of functional systems of a functional type // Journal of Computer and Systems Sciences International. Proceedings of Russian Academy of Science. Journal of Control Systems and Computers. - 2002 - № 5 - C. 101-110.

[3] Ополченов A.B., Фролов А.Б. Интервальный подход к построению систем принятия решений функционального типа // V Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. докл. - М., 1999. - С. 250.

[4] Гришина Е.А. Ополченов A.B. Алгоритм компрессии данных на основе их функциональной интерпретации // Международный форум информатизации МФИ-99. Информационные средства и технологии: Тез. докл. - М., 1999 -Т.2.-С.81-84.

* 17 6 8 0

[5] Ополченов A.B. Сергеев С. А. Программный инструментальный комплекс для синтеза и верификации экспертных систем и его применение в-атомной промышленности // Проблемы управления безопасностью сложных систем: Труды X международной конференции: Тез. докл.- М., 2002 -С. 217-219.

[6] Ополченов A.B. Синтез и верификация систем принятия решений функционального типа // IX Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. докл. - М., 2003. - С. 266 - 267.

Печ л .Л Тираж ЮО Подп. в Заказ 34/

Типография МЭИ, Красноказарменная, 13

ВВЕДЕНИЕ.

1. О задаче создания СПР функционального типа.

1.1 СПР функционального типа и задачи их синтеза и верификации.

1.2 СПР функционального типа и распознавание образов

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

1.4 СПР функционального типа и теория поиска и хранения информации.

1.5 Уточнение постановки задачи.40

Выводы по первой главе.

2. Исчисление граней.

2.1 Исчисление граней. Математическая модель.

2.2 Особенности программной реализации исчисления граней.

2.3 Некоторые алгоритмы исчисления граней.

2.4 Минимизация покрытий подмножеств декартова произведения граней.

Выводы по второй главе.

3. Обобщенные графики отображений и алгоритмы верификации их непротиворечивости и полноты.

3.1 Математическая модель СПР.*.

3.2 Верификация непротиворечивости моделей СПР.:.

3.3 Верификация полноты моделей СПР

Выводы по третьей главе.

4. Синтез информационных сред, реализующих функциональные отображения.

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

4.2 Модифицированные алгоритмы распознавания.

-34.3 Алгоритм верификации полноты на основе модифицированного алгоритма.

4.4 Использование структурных свойств решающего правила для ускорения принятия решений.

• 4.5 Сложность алгоритмов распознавания.

Выводы по четвертой главе.

ГЛАВА 5. Программный комплекс POOREX 2002 и методика создания экспертных систем на его основе.

5.1 Краткое описание программного комплекса POOREX 2002.

5.2. Обменный формат для представления исходных данных и информационных сред.

5.2.1 Схемы формата XSD.

• 5.2.2 Схемы формата DTD.

5.3 Методика создания и применения СПР с использованием программного комплекса POOREX 2002.

Выводы по пятой главе.

ГЛАВА 6. Экспериментальное исследование методики синтеза и верификации СПР.

6.1 Примеры синтеза и верификации СПР.

6.1.1 Предметная область «Genetics».

• 6.1.2 Предметная область «SubstanceState».

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

6.2.1 Подготовка исходных данных на POOREX 2002.

6.2.2 Модификация АРМ.

6.2.3 Исследование временных характеристик алгоритмов i распознавания предметной области «Restrictedcombinations».

6.3 Исследование времени работы алгоритмов распознавания на случайных наборах данных.

6.3.1 Исследование зависимости времени работы алгоритмов разделения от размерности области.

6.3.2 Исследование зависимости времени работы алгоритмов распознавания от размерности области.

6.3.3 Исследование зависимости времени работы алгоритмов разделения от числа граней решающей функции.

6.3.4 Исследование зависимости времени распознавания от числа граней решающей функции.

Выводы по шестой главе.

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

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

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

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

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

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

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

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

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

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

В этом проявляется отличие от реализации экспертной системы как системы продукционного типа, которая основана на аксиоматическом подходе к описанию состояний реальной системы и отношений на их основе и использовании правил индуктивного и дедуктивного вывода при извлечении решений [8, 12].

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

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

Этот подход реализован в настоящей работе на основе развиваемой с участием автора теории распознавания частично - упорядоченных объектов [57, 76, 78, 100], методами которой синтезируются информационные среды для вычисления значений k-значной функции, и теории хранения и поиска информации [14], дающей метод получения нетривиальных верхних оценок времени поиска решения в таких средах.

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

Цель работы

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

Основные направления работы сводятся к решению следующих задач:

- разработка алгоритмов и операций исчисления граней;

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

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

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

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

Методы исследования

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

Достоверность научных результатов

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

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

Новыми являются:

1) Алгоритмы и операции исчисления граней и ее применение для верификации непротиворечивости и полноты функциональной модели СПР.

2) Общий алгоритм разделения и распознавания частично упорядоченных объектов на k-значной решетке по обобщенному описанию обучающей выборки, и его частные варианты.

3) Алгоритмы вычисления значения функции к-значной логики, имеющие нетривиальные верхние оценки сложности.

- 104) Методика создания экспертных систем с оцениваемым временем принятия решений

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

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

Разработанный на языке высокого уровня С++[70] программный комплекс POOREX 2002 имеет модульную структуру, что делает доступным встраивание его функциональных компонент в другие проекты.

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

Программный комплекс внедрен в Федеральной Системе Учета и Контроля Ядерных Материалов.

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

Программный комплекс POOREX 2002 использован в ЦНИИ Атомин-форм при разработке АРМ подготовки сводной отчетности для выявления несовместимых сочетаний ядерных материалов в отчетных партиях. А также в учебном процессе МЭИ в курсе новых информационных технологий для магистров. Работа выполнена в рамках НИР № 1022002 «Анализ и разработка принципов алгоритмизации и верификации интеллектуальных систем функционального типа» кафедры ММ.

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

Основные положения и результаты диссертации докладывались и обсуждались:

• на 5-й международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (г. Москва, 1999 г.)

• на международном форуме информатизации МФИ-99 Информационные средства и технологии (г. Москва, 1999 г.)

• на 10-й международной конференции «Проблемы управления безопасностью сложных систем» (г. Москва, 2002 г.)

• на 9-й международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (г. Москва, 2003 г.)

Публикации,

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

1] Ополченов А.В., Фролов А.Б. Синтез и верификация систем принятия решений функционального типа. Известия Российской Академии наук. Теория и системы управления, № 5. 2002.

2] Opolchenov A.V., Frolov А.В. Synthesis and verification of functional systems of a functional type. Journal of Computer and Systems Sciences International. Proceedings of Russian Academy of Science. Journal of Control Systems and Computers. N 5. 2002.

3] Ополченов A.B., Фролов А.Б. Интервальный подход к построению систем принятия решений функционального типа // V Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. докл. — М. 1999. - С. 250

4] Гришина Е.А. Ополченов А.В. Алгоритм компрессии данных на основе их функциональной интерпретации // Международный форум информатизации МФИ-99. Информационные средства и технологии: Докл. - Моск. энерг. инст. — 1999-Т.2.-С.81-84

5] Ополченов А.В. Сергеев С.А. Программный инструментальный комплекс для синтеза и верификации экспертных систем и его применение в атомной промышленности // Проблемы управления безопасностью сложных систем: Труды X международной конференции. Москва, декабрь 2002 г. / Под ред. Н.И. Архиповой и В.В. Кульбы. Часть 2. - М.: РГГУ — Издательский дом МПА-Пресс. С. 217-219

6] Ополченов А.В. Синтез и верификация систем принятия решений функционального типа // IX Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. докл. - М. 2003. - С. 266 - 267.

Личный вклад автора:

1,2] Автору принадлежит обоснование полноты системы операций исчисления граней, способы их имплементации, а также описание алгоритмов синтеза и верификации систем принятия решений, в частности существенное уточнение алгоритма синтеза в [2].

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

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

5] Автору принадлежит описание программного инструментального комплекса и изложение его применения в федеральной системе учета и контроля ядерных материалов.

Структура и объём работы.

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

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

Направления дальнейших исследований:

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

2) Распространение области применимости разработанной методики построения экспертных систем принятия решений для распознавания континуальных объектов, классифицируемых по топологическим характеристикам. Исследование СПР функционального типа с учетом нечеткости описания знаний экспертов;

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

4) Модернизация ПО применительно к описаниям объектов не фиксированной длины.

Заключение

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

Эта цель достигнута на основе следующих теоретических результатов.

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

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

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

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

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

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

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

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

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

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

1. Абчук В.А., Суздаль В.Г. Поиск объектов. — М.: Советское радио, 1977.

2. Агасова С.М. Вычисления на нейронных сетях (Обзор) // Программирование. — 1991 — №2 — С. 12 — 19.

3. Аграев В.А., Бородин В.В., Кобрин Р.Ю., Майорова В.А., Шульц М.М. Дескрипторная информационно-поисковая система с позиционным кодированием «Компас-2» // Научно-техническая информация. Сер. 2. Информационные процессы и системы. — М.: ВИНИТИ, (1971), №2.

4. Айзерман М.А. Браверман Э.М. Розеноэр Э.И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970.

5. Алексеева Е.Ф. Стефанюк В.Л. Экспертные системы — состояние и перспективы // Изв. АН СССР. Техн. Кибернетика. 1984. - №5. - С. 153167.

6. Альсведе Р., Вегенер И. Задачи поиска. — М.: Мир, 1982

7. Ахо А., Хопкрофт. Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.

8. Башлыков А.А., Еремеев А.П. Экспертные системы поддержки принятия решений в энергетике. М.: Издательство МЭИ, 1994.

9. Биркгоф Г. Теория решеток. М.:Наука, 1984.

10. Ю.Болотоё А.А., Фролов А.Б. Классификация и распознавание в дискретных системах. Издательство МЭИ, 1997.11 .Братко И. Программирование на языке Пролог для искусственного интеллекта. М.: Мир, 1990

11. Вагин В.Н. Дедукция и обобщение в системах принятия решений. — М.: Наука. Гл. ред. Физ.-мат. Лит. 1988.

12. Вапник В.Н., Червоненкис А .Я. Теория распознавания образов. — М.: Наука, 1974.

13. Гасанов Э.Э., Кудрявцев В.Б. Теория хранения и поиска информации. -М.: ФИЗМАТЛИТ, 2002.

14. Гасанов Э.Э. Оптимальные информационные сети для отношений поиска, являющихся отношениями линейного квазипорядка // Конструкции в алгебре и логике. Тверь: Изд-во Тверского гос. Ун-та, 1990. - С.11-17.

15. Горбань А.Н. Обучение нейронных сетей. — М.: СпараГраф., 1990.

16. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. Некоторые аспекты. — М.: Радио и связь, 1985.

17. Городецкий В.М. Формирование понятийной структуры знаний на основе экспертной и экспериментальной информации // Всесоюз. конф. По ИИ: Докл. 1988 - T.l - С.385 - 390.

18. Гришина Е.А. Ополченов А.В. Алгоритм компрессии данных на основе их функциональной интерпретации // Международный форум информатизации МФИ-99. Информационные средства и технологии: Тез. докл. — М., 1999 — Т.2. С.81-84.

19. Гуревич Ю.Б. Журавлев Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика. — 1974- №1 — С.12-19

20. Джексон П. Введение в экспертные системы. — М.: Издательский дом «Вильяме», 2001.

21. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений. // Дискретный анализ = Новосибирск, Институт математики СО АН СССР 1966 - Вып. 7 - С.З -15.т

22. Еремеев А.П. Некоторые формальные построения на таблицах решений // Программирование, — 1978 №4 - С.16 - 22.

23. Еремеев А.П. О корректности таблиц решений // Программирование, — 1984 — №4 С.32 — 36.

24. Еремеев А.П. О трансляции таблиц решений // Программирование, — 1981 -№1 -С.48-57.

25. Еремеев А.П. Продукционная модель представления знаний на базе языка таблиц решений // Изв. АН СССР, Техн. кибернет., — 1987 — №2 — С.196 — 207.

26. Еремин И.И. Мазуров В.Д. Нестационарные процессы математического программирования. М.: Наука, 1979.

27. Жожикашвили А.В. Стефанюк B.JI. О понятии продукции в искусственном интеллекте. // М. Известия Академии Наук. Теория и системы управления, № 4. 2002

28. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. III // Кибернетика 1978 - №2 - С.35 - 43.

29. Журавлев Ю.И. Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика 1971 - №3 — С. 1 — 11

30. Журавлев Ю.И. Непараметрические задачи распознавания образов // Кибернетика 1976 - №6 - С.93 - 103.

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

32. Журавлев Ю.И. Об алгоритмических методах в задачах распознавания и классификации // Распознавание, классификация, прогнозирование. Математические методы и их применение. — 1989 — Вып.1 — С. 9 — 16.

33. Журавлев Ю.И. Экстремальные задачи, возникающие при обосновании эвристических процедур // Проблемы прикладной математики и механики -М. Наука, 1971.

34. Искусственный интеллект: В Зкн. Кн.2. Модели и методы : Справочник / Под ред. Д.А. Поспелова М.: Радио и связь, 1990.

35. Ким Д.П. Методы поиска и преследования подвижных объектов. — М.:Наука, 1989.

36. Классификация и распознавание в дискретных системах. А.А. Болотов, А.Б. Фролов / Под ред. В.Н. Вагина. М.: Изд-во МЭИ, 1997.

37. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978.

38. Кондратьев А.И. Теоретико-игровые распознающие алгоритмы./Отв. ред. Е.В. Золотов. АН СССР, Дальневосточное отделение ВЦ — М.: Наука, 1990.

39. Коробейников А.П. Методы распознавания образов: Учебное пособие/ Коробейников А.П. — Ростов-На-Дону: Издат.ЦентрДТТУ, 1999.

40. Кудрявцев В.Б., Алешин С.В. Комбинаторно логический подход к распознаванию образов. Интеллектуальные системы. Том 1, вып. 1—4, 1996.

41. Кудрявцев В.Б., Алешин С.А., Подколизин А.С. Введение в теорию автоматов. М.: Наука, 1985.

42. Ледли Р.С. программирование и использование цифровых вычислительных машин: Пер. с англ. — М.: Мир, 1966.

43. Ли Д., Препарата Ф. Вычислительная геометрия. Обзор // Кибернетический сб. 1987. - Т.24 - С. 5-96.

44. Марков А. Теория алгоритмов // Тр. Математического института им. Стеклова АН СССР. 1954.

45. Мейерс С. Эффективное использование STL. Библиотека программиста. СПб.: Питер, 2002.

46. Микулич Л.И. Проблемы создания экспертных систем // Ученые записки Тартуского ГУ. — Тарту, 1985. — Вып. 714. Теория и модели знаний (теория и практика создания систем искусственного интеллекта). — С. 87114.

47. Минский М., Пейперт С. Персептроны. М.: Мир, 1971.

48. Мошков М.Ю. Деревья решений. Теория и приложения. — Нижний Новгород: Изд-во Нижегородского ун-та, 1994.

49. Мошков М.Ю. Нижние оценки временной сложности детерминированных условных тестов // Дискретная математика. — 1996. — Т.8, №3. — С.98-110.

50. Нариньяни А.С., Яхно Т.Г. Продукционные системы // Представление знаний в человеко-машинных и робототехнических системах. — М.: ВЦ АН СССР, ВИНИТИ, 1984. С.136 - 177.

51. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь, 1985.

52. Патрик Э. Основы теории распознавания образов. — Пер с англ./ Под ред. Б.Р. Левина. М.: Сов. Радио, 1980.

53. Питц-Моултис Н., Кирк Ч. XML: Пер. с англ. Спб.: BHV - Санкт-Петербург, 2000.

54. Поспелов Д.А. Продукционные модели // Искусственный интеллект. Кн. 2 Модели и методы. М.: Радио и связь, 1990.

55. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989.

56. Приобретение знаний: Пер. с япон. / Под ред. С. Осуги, Ю. Саэкш М.: Мир, 1990.

57. Распознавание. Нейросети. Виртуальная реальность. / Под ред. В.Б. Бетелина (Вопросы кибернетики) М., 1997.

58. Распознавание образов: Состояние и перспективы: Пер с англ.: К.Верхаген, Р.Дейн, Ф.Грун М.: Радио и связь 1985.

59. Растригин JI.A., Эренштейн Р.Х. Метод коллективного распознавания — М.:Энергоиздат, 1981.

60. Решетников В.Н. Алгебраическая теория информационного поиска // Программирование. 1979, №3. - С.68-74.

61. Розенблат Ф. Принципы нейродинамики (персептрон и теория механизмов мозга). — М.: Мир, 1965.

62. Селтон Г. Автоматическая обработка, хранение и поиск информации. — М.: Советское радио, 1973.

63. Солтон Дж. Динамичные библиотено-информационные системы. — М.: Мир, 1979.

64. Страуструп Б. Язык программирования С++, 3-е изд. / Пер. с англ. — Спб.; М.: «Невский диалект» «Издательство БИНОМ», 1999.

65. Ту Дж., Гонсалес Р. Принципы распознавания образов. — М.: Мир, 1978.

66. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. — М.: Мир, 1982.

67. Фролов А.Б. Модели и методы технической диагностики — М.: Знание, 1990.

68. Фролов А.Б. Фролов Д.А. Алгоритмы распознавания упорядоченных объектов в системах принятия решений функционального типа. Вестник МЭИ, 1996, N6.

69. Фролов А.Б., Фролов Д.А., . Четрафилов И.Д. Распознавание в интеллектуальных системах функционального типа. Интеллектуальные системы, 1997, том. 2, вып. 1-4.

70. Фролов А.Б., Фролов Д.А., Яко Э. Программируемые функциональные схемы для распознавания частично упорядоченных объектов. Известия' АН СССР, сер. Техническая кибернетика. №5,1997.

71. Фролов А.Б., Четрафилов И.Д. О некоторых подходах к распознаванию оптических образов текстов. Интеллектуальные системы, 1997, том. 2, вып. 1-4.

72. Фролов А.Б., Яко Э. Алгоритмы распознавания частично упорядоченных объектов. Известия АН СССР, сер. Техническая кибернетика. №5, 1990.

73. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977.

74. Хеллман О. Введение в теорию оптимального поиска. — М.:Наука, 1985.

75. Черный А.И. Введение в теорию информационного поиска. — М.: Наука,1975.

76. Энциклопедия кибернетики. — Киев, 1975, т.1. Статьи: «Информационно-поисковая система» (с.359), «Информационно-поисковая система документальная» (с.359-400).

77. Яблонский С.В. Введение в дискретную математику. — М.: Наука, 1979.

78. Яко Е. Разработка и анализ методов канонической логической декомпозиции булевых функций: приложение в системах логического проектирования М.:МЭИ, 1983.

79. Baldwin J.E., eds. Fuzzy Logic. New York: Wiley, 1996.

80. Ben-Or M. Lower bounds for algebraic computation trees. Proc. 15th ACM Annu. Symp. Theory. Comput. (Apr. 1983) 80 86.

81. Bentley J.L., Saxe J.B. Decomposable searching problems. I. Static-to-dynamic transformation. J. Algorithms (1980), 1, 301-358.

82. Borodin A.B. Computational complexity — Theory and practice. Currents in Theory of Computings. Englewood Cliffs, NJ: Printice-Hall, 1973, 35-89.

83. Carpenter G.A., Grossberg S. A massively parallel Architecture for a Selforganizing Neural Patteny Recognition Machine // Сотр. Vision, Graphics and Image Process 1987. - V.37. - P.54 - 115.

84. Chomsky N. Formal Properties of grammars // Handbook of Mathematical Psychology. V. II / Eds R. Luce, R. Bush, E. Galanter. N.Y., 1963.

85. Dobkin D.P., Lipton R.J. On the complexity of computations under varying sets of primitives. J. Comput. Syst. Sci. (1979) 18, 86 91.

86. Frolov A.B., Jako E., Algorithms of Partially Ordered Objects Recognition and their Application. Soviet Journal of Computer and Systems Sciences. V.29. N3, May-June, 1991.

87. Frolov A., Jako E., Mezey P. Logical models of molecular shapes and their families. Mathematical Chemistry, 30(4), 2001, nov., pp. 389-409.

88. Frolov A., Jako E., Mezey P. Metric properties of factor space of molecular shapes. Mathematical Chemistry, 30(4), 2001, nov., pp. 411—428.

89. Fukushima K.A. Neural Network Models for Selective Attention in Visual Pattern Recognition // Biol. Cybernetics. 1986. - V.45. - P.5 - 45.

90. Lauter U. 4-dimentional binary search trees as a means to speed us associative searches in design verification of integrated circuits. Jour, of Design Automation and fault Tolerant Computing, 2, no. 3, 1978, july, pp. 241-247.

91. Mamdani E.H., Gaines B.R. Fuzzy Reasoning and its Applications. London: Academic Press, —1981.

92. Newell A., Simon H.A. Human Problem Solving. Englewood Cliffs. N.Y.: Prentice-Hall, 1972.

93. Pavlidis T. Algorithms for Graphics and Image Processing. Springer-Verlag, Berlin, 1982.

94. Post E. Formal reduction of the general combinatorial // American J. Math. 1943.

95. Proceedings IEE Int. Conf. Artif. Newral Networks. London. — 1989.

96. Rabin M.O. Proving simultaneous positivity о linear forms. J. Comput. Syst. Sci. (1972)6,639-650.

97. Reingold E.M. On the optimality of some set algorithms. J. ACM (Oct. 1972) 19, no. 4, 649-659. •

98. Roth J.P., Karp R.M. Minimization over Boolean graphs. IBM Journal of Research and Develovment, 1962, v. 6, N 2.

99. Saxe J.B., Bentley J.L. Transforming static data structures into dynamic structures. Proc 20th IEEE Annu. Symp. Found. Comput. Sci. (Oct. 1979), 148168.

100. Steely J.M., Yao A.C. Lower bounds for algebraic decision trees. J. Alrorith. (1982) 3, 1-8.

101. Zadeh L.A. Information and Control 1965 -P.338 - 353.

102. МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

103. На правах рукописи Ополченов Алексей Викторович

104. МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА СОЗДАНИЯ ЭКСПЕРТНЫХ СИСТЕМ ПРИНЯТИЯ РЕШЕНИЙ