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

«6 ол

..) га '

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

Суров Вадим Валерьевич

ИССЛЕДОВАНИЕ ЗАДАЧ И МЕТОДОВ ИХ РЕШЕНИЯ ДЛЯ ОДНОГО КЛАССА СИСТЕМ ЛОГИЧЕСКИХ СООТНОШЕНИЙ

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Владивосток 2000

Работа выполнена в Институте автоматики и процессов управления Дальневосточного отделения РАН.

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

старший научный сотрудник И. Л. Артемьева

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

доктор технических наук В. А. Бобков

кандидат физико-математических наук О. С. Молокова

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

Институт систем информатики Сибирского отделения РАН (г. Новосибирск)

Защита состоится

2000г. в

10

часов на

заседании диссертационного совета К 064.58.08 в Дальневосточном государственном университете по адресу: 690041, г. Владивосток, ул. Октябрьская, 27.

С диссертацией можно ознакомиться Дальневосточного государственного университета.

в библиотеке

Автореферат разослан

■7

а "

(х^ехя 2000г.

Ученый секретарь диссертационного совета к.т.н., доцент Е.И.Антонова

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

Актуальность проблемы. В настоящее время в области инженерии знаний, целью которой является исследование и разработка прикладных программных систем, основанных на знаниях и моделирующих работу экспертов в трудно формализуемых предметных областях, существует множество методологий и инструментальных средств, ориентированных, в первую очередь, на повторное использование методов решения задач, где под повторным использованием методов понимается использование ранее разработанных методов при создании новых систем, основанных на знаниях. Известными примерами таких методологий являются Task Structures, Role-Limiting Methods, Method-to-Task и Components of Expertise. На основе этих методологий разработаны такие инструментальные средства, как CommonKADS, PROTÉGÉ-II, Spark/Burn/Firefighter, MIKE и другие. Характерной особенностью этих инструментальных средств является наличие библиотеки различных методов решения задач. Практика разработки таких библиотек основана на повторном использовании так называемых "парадигм" решения задач, например, таких, как Heuristic Classification и Propose-and-Revise. Эти методы представляют собой описание общей схемы решения задачи на некотором неформальном языке с использованием предметно независимой терминологии. В процессе разработки системы, основанной на знаниях, эксперту предметной области на основе общей методологии предстоит определить соответствие между терминами, в которых описан метод, и терминами предметной области, для которой создается система. Использование библиотек методов позволяет сделать из инженерии знаний обычную инженерную дисциплину. Но, несмотря на достигнутый прогресс в это области, существует ряд проблем:

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

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

проблема адаптации метода или, другими словами, проблема установления соответствия между терминологией, в которой описан метод, и терминологией предметной области;

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

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

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

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

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

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

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

2. Разработать и исследовать математические методы решения поставленных задач и выделить общие для них подзадачи.

3. Разработать и исследовать методы решения общих подзадач.

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

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

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

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

- разработаны и исследованы математические методы решения поставленных задач;

- выделены подзадачи, общие для указанных математических задач;

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

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

Практическая ценность работы состоит в следующем:

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

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

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

Апробация работы. Основные научные и практические результаты работы докладывались и обсуждались на следующих международных и отечественных конференциях и семинарах: П-ой Международной научно-технической конференции "Интерактивные системы: проблемы человеко-

машинного взаимодействия" (Ульяновск, 1997), У1-ой Международной конференции "Знание-Диалог-Решение" (Ялта, 1997), Дальневосточной математической школе-семинаре имени академика Е.В. Золотова (Владивосток, 1997, 1999), Дальневосточном региональном конкурсе компьютерных программ студентов, аспирантов и молодых ученых "Программист-98" (Владивосток, 1998), 1-ой Дальневосточной конференции студентов и аспирантов по математическому моделированию (Владивосток 1997), ГУ-ом Международном конгрессе по экспертным системам (Мехико, 1998), Региональной естественнонаучной конференции студентов, аспирантов и молодых ученых (Владивосток, 1997), Третьем сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98) (Новосибирск, 1998), совместных семинарах отдела экспертных систем ИАПУ ДВО РАН и базовой кафедры программного обеспечения ЭВМ ДВГУ в ИАПУ ДВО РАН (1995-1999).

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

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

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

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

Во второй главе определены три математические модели £2\ С12 и О3 в виде систем логических соотношений второго порядка. Основным объектом модели О1 является сложная система со статическими параметрами и параметрами, динамически изменяемыми во времени. Внутри системы протекают различные процессы, вследствие чего изменяются значения параметров системы. Известны статические и динамические свойства изменения параметров каждого процесса. Модель О2 является упрощенной версией модели £2\ в которой удалены некоторые неизвестные и параметры. В работе показано, как результаты исследования задач и методов их решения, полученные для модели О1, могут быть применимы для модели £2*. Отличием модели £23 от модели О2 состоит в том, что признаки являются не динамическими, а статическими

величинами. Модель О3 является наиболее распространенной моделью, используемой при создании систем, основанных на знаних.

В определении схем символов сигнатур Е) и Ег модели О2 используются следующие сорта: сорта ТиЬ целых чисел; сорт <3 = Яг, ..., Ям}сТ; сорта Ъ, Р, Р и 5 скалярных элементов; сорта 8ЕТ_У и БЕТ_Р множеств скалярных элементов; специализированный сорт Я разбиений (г0, г1; ..., г„), где г0, гь ..., г„ - целые числа такие, что г0 < п < ... < гп. Сигнатура Е1 модели О2 включает объектную неизвестную х сорта X, функциональные неизвестные г{ со схемой (Б, ЯЕТ_У), гр со схемой (Р, О, 8ЕТ_У), рс1 со схемой (Р, Я). Сигнатура Е2 модели & включает объектный параметр N сорта Ь и функциональные параметры gdmin со схемой {X, Р, Ь, Т), gdmax со схемой {X, Р, Ь, Т), пг со схемой (Р, 5ЕТ_У)> уг со схемой (Б, 8ЕТ_У), пи со схемой (X, Р, БЕТ.У), кк со схемой (X, БЕТ.Р) и кр со схемой (X, Р, Ь, 8ЕТ_У). Если определить переменные гиг' сорта Х,рир' сорта Р, f сорта Р, ц сорта Q, п сорта Ь и константу е0 сорта X, то модель О2 включает следующие логические соотношения:

1) г^О с & гр(р, q) с уг(р);

2) пи(г, 0 с & пг(р) с уг(р) & кр(г', р', п) с уг(р');

3) 0 < gdmin(z, р, п) & £с1ГГцП(г, р, п) < gdmax(z, р, п);

4) х = е0 гр(р, я) с пг(р);

5) х * е0 & пи(х, -> гОД с пи(х, 0;

6) х * е0 & р ё кк(х) гр(р, ч) с пг(р);

7) х * е0 & р е кк(х) & 2 < п< N & 5е1(рс1(р), п-1) < я < 5е1(рс1(р), п)

гр(р, я) с кр(х, р, п);

8) х * е0 & р е кк(х) & 2 < п< N

gdm¡n(x, р, п) < Бе1(рс1(р), п)-5е1^(р), п-1) < gdmax(x, р, п).

На модели О2 поставлены различные задачи, которые, в зависимости от того, что требуется найти, разделены на четыре группы. К первой группе отнесены задачи нахождения значения х. При этом в задаче Г/.у дано такое, что \/ГеР*сР (гГ(Г)^0); в задаче ¡¡ 2 дано гр такое, что \/реР*сР, \ZqeQ (гр(р, в задаче ^ дано pd такое, что УреР*сР в

задаче //.4 даны гГ, гр такие, что УГе Р*сгР (гОД^0), \/реР*сР, \ZqeQ (гр(р, я)*0); в задаче даны pd такие, что \ЯеР*сР (гЩ);£0), УреР*сР ^(р)*0); в задаче гАб даны гр, pd такие, что УреР*^, (гр(р, q)*0), УреР* (рс1(р)^0); в задаче 7 даны тХ, гр, pd такие, что у^р*сР (/1(0^0), УреР*сР, \ZqeQ (гр(р, Ч)^0), УреР* ^(р)*0). Ко

второй группе отнесены задачи нахождения значения pd(p), где ре Р. При этом в задаче t2j дано х; в задаче t2,2 дано zf такое, что Vfe F*cF (zf(f)/0); в задаче t2J дано zp такое, что VpeP*cP, VqeQ (zp(p, q)*0); в задаче t2.4 даны х и zf такое, что VfeF*cF (zf(f)*0); в задаче t2.s даны х и zp такое, что VpeP*cP, VqeQ (zp(p, ц)Ф0); в задаче t2,6 даны zf, zp такие, что VfeF*cF (zf(f)*0), VpeP*cP, VqeQ (zp(p, q)*0); в задаче t2J даны x, zf, zp такие, что VfeF* (zf(f)*0), VpeP*cP, VqeQ (zp(p, q)^0). К третьей группе отнесены задачи нахождения значения zf(f), где feF. При этом в задаче tu дано х; в задаче t32 дано zp такое, что VpeP*cP, VqeQ (zp(p, q)^0); в задаче t33 дано pd такое, что VpeP*cP (pd(p)*0); в задаче t3A даны х и zp такое, что VpeP*, VqeQ (zp(p, q)/0); в задаче t3.5 даны х и pd такое, что VpeP*cP (pd(p)*0); в задаче t3.6 даны zp, pd такие, что VpeP*cP, VqeQ (zp(p, q)£0), VpeP* (pd(p)^0); в задаче t3,7 даны x, zp, pd такие, что VpeP*cP, VqeQ (zp(p, q)*0), VpeP* (pd(p)*0). К четвертой группе отнесены задачи нахождения значения zp(p, q), где ре Р и qeQ. При этом в задаче t4j дано х; в задаче t42 дано zf такое, что VfeF*eF (zf(f)*0); в задаче t4j дано pd такое, что VpeP*cP (pd(p)*0); в задаче t4A даны х и zf такое, что VfeF*cF (zf(f)^0); в задаче t4S даны х и pd такое, что VpeP*cP (pd(p)#0); в задаче t46 даны zf, pd такие, что VfeF*cF (zf(f)*0), VpeP*cP (pd(p)*0); в задаче t4.7 даны х, zf, pd такие, что VfeF*cF (zf(f)*0), VpeP*cP (pd(p)*0).

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

Теорема 1.1.1. Для того чтобы элемент zeZ\{eo} был решением задачи tu, необходимо и достаточно, чтобы было выполнено условие VfeF (nu(z, zf(f) с nu(z, f)).

Теорема 1.1.2. Предположим, что для произвольных zeZ\{eo} и feF имеют место неравенства nu(z, f)*0 и zf(f)*0, тогда если задача имеет решение zeZ\{e0} и выполнено условие VzieZ\{e0}, Vz2eZ\{zb е0}, VfeF (nu(zb f) n nu(z2, f) = 0), то это решение единственно.

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

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

Теорема 2.0. Если существует единственная xeZ\{eo} такая, что pekk(x) и выполняются условия

2.1) VfeF (nu(x, f)*0 zf(f) с nu(x, f)),

2.2) Vp'eP*\kk(x), VqeQ (zp(p', q) £ nz(p'))

и при этом выполнено хотя бы одно из следующих условий N

2.3)Q={qeTI0<q< I gdmax(x, p, i)} и i = 1

Vke [1, N-l] (kp(x, p, к) n kp(x, p, k+1) = 0),

2.4) Vke [1, N] (gd^x, p, k) = gdmax(x, p, k)),

то задача второй группы имеет единственное решение.

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

Теорема 3.0. Если ¡i(vz(f))-l или ¡л(пи(х, f)) = 1, где xeZ\{eo} задано или является единственным решением соответствующей задачи первой группы, то задача имеет единственное решение.

Теорема 4.0. При выполнении хотя бы одного из приведенных далее условий задача четвертой группы имеет единственное решение:

H(vz(p))=l,

х = е0 и |x(nz(p)) = 1,

х * е0, p £ kk(x) и ц,(пг(р)) = 1,

х е Z\{e0} является единственным решением соответствующей задачи первой группы, p g kk(x) и |i(nz(p))=l,

xeZ\{eo} является единственным решением соответствующей задачи первой группы, p g kk(x), существует ke[l, N] такой, что выполнено неравенство sel(pd(p), k-1) < t < sel(pd(p), k) и |a(kp(x, p, k)) = 1.

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

Методы решения задач первой группы сводятся к формированию различных гипотез о возможном решении задачи и их проверке. Метод решения задачи ti.i представлен алгоритмом au, при этом задача проверки необходимого и достаточного условия VfeF* (nu(z, f)*0 —> zf(f) çr nu(z, f)) для заданного элемента zeZ\{e0}, которое было определено в теореме 1.1.1, выделена в отдельную подзадачу subi.

Алгоритмам. Решение задачи tu

Дано: zf.

Результат: множество возможных значений х. Метод:

1 будем считать, что Результат содержит единственный элемент ео;

2 в цикле по всем элементам множества Z\{eo), пусть z - текущий элемент, выполнить следующие шаги:

3 решаем подзадачу subi для текущего значения z;

4 если условие подзадачи subi выполняется, то z добавляем в Результат;

5 конец цикла 2; конец алгоритма au-

Доказана следующая теорема о корректности алгоритма аи.

Теорема 1.1.4. Пусть множество Xu - результат выполнения алгоритма а и для заданного значения zf, тогда произвольный элемент, принадлежащий множеству Xu, являются решением задачи tu, других элементов нет.

Для задачи ti.2 рассматриваются два различных подхода к реализации метода решения: первый подход реализует метод в форме алгоритма, второй - в форме исчисления. В первом методе выделяются три подзадачи:

подзадача sub2 - проверка условия Vqe Q (zp(p, q) ç nz(p)) для заданного элемента реР* и функционального отношения zp;

подзадача sub3 - проверка условия VqeQ (zp(p, q) с nz(p)) для заданного элемента ре P*\kk(z) и функционального отношения zp;

подзадача subj - доказательство существования значения функциональной неизвестной pd для аргумента р, удовлетворяющего условиям

Vke[l, N], VqeQ (sel(pd(p), k-l)< q < sel(pd(p), k) zp(p, q)çkp(z, p, k)), Vke [1, N] (gdmin(z, p, k) < sel(pd(p), k) - sel(pd(p), k-1) < gdmax(z, p, k)) и 0 < sel(pd(p), 1)< ... < sel(pd(p), N),

для заданных элементов zeZ\{eo}, peP*nkk(z) и функционального отношения zp.

При исследовании метода решения задачи tu было доказано, что для проверки гипотезы о том, что некоторый элемент zeZ\{eo} есть решение задачи ti.3, необходимо и достаточно показать, что для всех peP*nkk(z) и произвольного целого числа ke[l, N] выполняется условие gdmjn(z, р, к) < sel(pd(p), к) - sel(pd(p), к-1) < gd^z, р, к). Задача проверки этого условия

для заданных z, р, к и pd выделена в отдельную подзадачу sub¡. Для задачи ti.4 была доказана следующая теорема.

Теорема 1.4.3. Решение задачи ti.4 для заданных zf и zp принадлежит пересечению множеств возможных решений задачи tu для заданного значения zf и возможных решений задачи ti.2 для заданного значения zp, других решений нет.

Исходя из этой теоремы для задачи ti.4 предложен метод сведения задачи к задачам tu и tu, представленный далее алгоритмом a¡A. Исследована возможность оптимизации предложенного метода.

Алгоритм a¡ 4. Сведение задачи t¡ 4K задачам t¡ ¡ и t¡.2

Дано: zf, zp.

Результат: множество возможных значений х. Метод:

1 решаем задачу tu для заданного значения zf;

2 решаем задачу ti.2 для заданного значения zp;

3 Результат определим как пересечение множеств возможных результатов решения задач tu и tu;

конец алгоритма a¡A.

Аналогичный подход сведения задачи к рассмотренным ранее задачам используется для задач tu, ti .в и ti.7. Для задачи ti.6, кроме метода сведения к задачам tu и ti.3, предложен другой, более эффективный метод, исключающий лишние вычисления при решении задачи tu. При этом выделяются следующие подзадачи:

подзадача sub6 - проверка условия Vqe Q (zp(p, q) с nz(p)) для заданных реР* и функционального отношения zp;

подзадача sub7 - проверка условия Vqe Q (zp(p, q) с nz(p)) для заданных элемента pe P*\kk(z) и функционального отношения zp;

подзадача sub$ - проверка условия Vqe Q (sel(pd(p), k-1) < q < sel(pd(p), k) —> zp(p, q) с kp(z, p, k)) для заданных элементов zeZ\{e0}, peP*nkk(z), целого числа ke [1, N] и функциональных отношений zp, pd; подзадача subg - проверка условия gdm¡n(z, р, k) < sel(pd(p), k) - sel(pd(p), k-1) < gdmax(z, p, k) для заданных элементов zeZ\{e0}, peP*nkk(z), целого числа ke [1, N] и функциональных отношений zp, pd.

Исследование методов решения задач второй группы показало, что если pe£kk(x), то любое значение неизвестной pd от аргумента р, удовлетворяющее условию 0 < sel(pd(p), 1) < ... < sel(pd(p), N), является решением задачи второй группы. В работе рассматриваются методы

решения задач второй группы при условии, что рекк(х). Метод решения задачи t2.i очевиден. Решение задачи 1г.2 состоит из двух этапов и сводится к решению задач tu и t2.i- Для решения задачи t2.3 необходимо определить значение неизвестной х, что можно сделать двумя способами: либо решить задачу ti.2 первой группы, либо применить уже использованный ранее метод опровержения гипотез о возможном значении неизвестной х. После того, как значение х будет найдено, решение данной задачи можно свести к решению задачи t2.s- Метод решение задачи t2.4 аналогичен методу решения задачи t2.i для заданного значения х, если pekk(x) и выполнено условие Vfe F (nu(x, f)^0 —> zf(f) с nu(x, f)). В других случаях задача не имеет решение. Для решения задачи t2.5 необходимо найти значение неизвестной pd(p), удовлетворяющее условиям

О < sel(pd(p), 1)< ... < sel(pd(p), N),

Vke [1, N] (gcWx, p, k) < sel(pd(p), k) - sel(pd(p), k-l)< gd^x, p, k)) и

Vke [1, N], VqeQ (sel(pd(p), k-1) < q < sel(pd(p), k) zp(p, q) с kp(x, p, k)).

Задача нахождения значения функциональной неизвестной pd для заданного аргумента р, удовлетворяющего этим условиям, рассматривается далее как подзадача subw. Решение задачи t2.6 и t2.7 сведено к задачам tu, t12, t2.s

Если значение х не равно ео и выполнено неравенство nu(x, f) Ф 0, то решением задачи t3.i, т.е. значением неизвестной zf для произвольного аргумента fe F является любое подмножество значения nu(x, f). В случае невыполнения этого условия результатом задачи будет любое подмножество значения vz(f). Решение других задач третьей группы сводится к решению рассмотренных ранее задач. Если значение неизвестной х равно ео или оно не равно ео, но при этом р не принадлежит множеству kk(x), то результатом задачи tu, т.е. искомым значением zp(p, t) является любое подмножество значения nz(p). Если же х не равно е0, р не принадлежит kk(x) и существует ke[l, N] такой, что sel(pd(p), k-1) < t < sel(pd(p), k), то искомым значением zp(p, t) является любое подмножество значения kk(x, р, к). Решение других задач четвертой группы сводится к решению рассмотренных задач.

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

В четвертой главе представлены результаты исследования подзадач, разработки и исследования методов их решения. Четыре подзадачи sub2, виЬз, sub6, sub7 и две подзадачи subs, subi» имеют

одинаковые формальные постановками. Для таких подзадач рассматривается общий метод решения. Подзадач subi, sub2, sub3, sub5, sub6, sub7, subg и sub9 имеют очевидные методы решения и не требуют дополнительных исследований, тогда как для разработки метода решения подзадачи sub4 необходимы дополнительные исследования, результаты которого приводятся далее.

Пусть для произвольного ke[l, N] некоторое Yk равно значению функции sel(pd(p), к). Если использовать введенные обозначения, то для решения подзадачи sub4 требуется найти последовательность Ть ..., TN, удовлетворяющую условиям

3.1) Yo<Ti<... <Yn,

3.2) Vke [1, N], Vqe Q (Yk_,< q < Yk zp(p, q) ç kp(z, p, k)),

3.3) Vke [1, N] (gd^z, p, k) < Yk - Yk_! < gdmax(z, p, k)),

где Yo = 0. Определим необходимых и достаточных условий существования такой последовательности. Пусть для произвольного ке[1, N] множество Qk есть подмножество из таких элементов множества Q, что для всех qeQ выполняется неравенство Yk_i < q < Yk. На множестве Qk введем функции min и шах, указывающие на минимальный и, соответственно, максимальный элемент этого множества. Будем считать, что множество Q0 содержит единственный элемент 0 и, следовательно, max(Q0) = 0.

Соглашение 7.3. Если для произвольного ke[l, N] имеет место равенство Qk = 0, то для функций min(Qk) и max(Qk) должно выполняться неравенство Yk_! < min(Qk) < max(Qk) < Yk.

Теорема 7.4 {необходимые и достаточные условия выполнения 3.3 при наличии пустых множеств Q¡, ..., Qu). Если имеет место соглашение 7.3, то для выполнения условия 3.3, необходимо и достаточно, чтобы были выполнены условия

3.3.1') Vke [1, N] (Qk * 0 max(Qk) - min(Qk) < gdmax(z, p, k)),

3.3.2') VM [0, N—2], Vk2e [2, N] (Q^ * 0 & Qk2 Ф 0 & k,+l < k2

k2-l

mm(Qk ) - max(Qk ) > i gdmin(z, p, i)), i=k|+l

3.3.3') Vke [1, N] (Qk / 0 max(Qk) < \ gdmax(z, p, i)).

i = 1

Пусть М-ка (пь ...., nM), где M = |J.(Q), представляет собой последовательность нестрого монотонно возрастающих целых чисел от 1 до N, т.е. выполнено следующее условие

3.4) Vie [1, M-l] (1< ill < ni+, < N).

Обозначим Ynm - множество всевозможных М-ок, для которых выполняется условие 3.4. На множестве М-ок Yn'm\{(N, ..., N)}, определим операцию "+" увеличения произвольной М-ки (пь ..., пм) на 1, следующим образом: если М=1 и ni<N, то (ni) + 1 = (П[+1); если М>1, то

{(г>1, п2,..., пм+1), если nM<N;

((п'ь п'г,..., п'м-i), п'м-i), если nM=N; где (п'ь п'2>..., п'м-i) = (пь П2, •••>nM-i) + 1.

Теорема 3.8 (о множестве YN'M = (V, •■•> Г|е}, где V = (1, ..., 1),

N i, iM-i

Vie [2, е] (Т)1 = Т|1-1 + 1), е = . S II.

ij-i^-i iM-1

М-ку (п1;..., nM)e Yn'm будем называть распределением, если для множеств Qi, ..., Qn, построенных по этой М-ке, выполняются условие Vke[l, N], VqeQk (zp(p, q) с kp(z, p, k)) и условия 3.3.1' - 3.3.3'. Если выполнено соглашение 7.3, то для доказательства существования решения подзадачи sub4 необходимо и достаточно доказать существование распределения. Поиск такого распределения составляет суть метода решения подзадачи sub4.

В методе решения подзадачи subio используется метод решения подзадачи, рассмотренные при разработке метода решения подзадачи sub4.

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты работы заключаются в следующем:

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

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

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

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

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

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

Кроме этого, решаются основные проблемы существующих средств разработки систем, основанных на знаниях:

- проблема доверия, поскольку представленные методы формально исследованы и можно по формальным признакам проверить, удовлетворяет ли они требованиям правильности и приемлемости;

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

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

- а также проблема создания многозадачных систем, основанных на знаниях.

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Артемьева И. JL, Суров В. В. Принципы организации библиотеки методов решения задач в экспертных системах // VI-я Международная конференция "Знания-Диалог-Решения": Труды конференции. Ялта, 1997. С. 116-122.

2. Артемьева И. Л., Суров В. В. Организация взаимодействия с инструментальным средством для разработки экспертных систем // П-я Международная научно-техническая конференции. "Интерактивные системы: проблемы человеко-компьютерного взаимодействия": Тезисы докладов. Ульяновск, 1997. С. 98.

3. Суров В. В. Метод решения задачи диагностики // Дальневосточная математическая школа-семинар им. академика Е. В. Золотова: Тезисы докладов. Владивосток: ИАПУ ДВО РАН, 1997. С. 12.

4. Суров В. В. Модель ядра экспертной системы // Региональная естественнонаучная конференция студентов, аспирантов и молодых ученых: Тезисы докладов. Владивосток: ДВГУ, 1997. С. 120.

5. Суров В. В. Технология разработки модели ядра экспертной системы // 1-я Дальневосточная конференция студентов и аспирантов по математическому моделированию: Тезисы докладов. Владивосток: ИПМ ДВО РАН, 1997. С. 52.

6. Kleshchev А. S., Artemjeva I. L., Gavrilova Т. L., Surov V. V. Application of logical relationship systems for expert system development. In Appl. of Advanced Information Technologies: Proceedings of the 4th World Congress on Expert Systems, 16-20 March 1998. Mexico City Cognizant Communication Corporation, 1998. Vol.l. P. 500-511.

7. Суров В. В. Метод решение задачи диагностики и его использование // Дальневосточный региональный конкурс компьютерных программ студентов, аспирантов и молодых ученых "Программист-98": Тезисы докладов. Владивосток: ИАПУ ДВО РАН, 1998. С. 44-45.

8. Артемьева И. Л., Суров В. В. Разработка ядра экспертной системы с использованием пакета прикладных программ // 3-й Сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-98), Ч. V: Тезисы докладов. Новосибирск: Изд-во Института математики СО РАН, 1998. С. 37.

9. Суров В. В. Экспериментальное сравнение методов решения задачи диагностики // Дальневосточная математическая школа-семинар им. академика Е. В. Золотова: Тезисы докладов. Владивосток: "Дальнаука" ДВО РАН, 1998. С. 79.

10. Суров В. В. Задачи на логической модели предметной области "Медицина" // Дальневосточная математическая школа-семинар им. академика Е. В. Золотова: Тезисы докладов. Владивосток: "Дальнаука" ДВО РАН, 1998. С. 80.

11. Суров В. В. Экспериментальное сравнение методов решения задачи диагностики // Сборник научных трудов, Ч. III. Дальневосточная математическая школа-семинар им. академика Е. В. Золотова, Владивосток: ИАПУ ДВО РАН, 1999. С. 3-9.

12. Суров В. В. Задачи на логической модели предметной области "Медицина" и их исследование // Сборник научных трудов, Ч. II. Дальневосточная математическая школа-семинар им. академика Е. В. Золотова. Владивосток: ИАПУ ДВО РАН, 1999. С. 3-11.

13. Артемьева И. Л., Суров В. В. Исследование задач для одного класса систем логических соотношений: Препринт. Владивосток: ИАПУ ДВО РАН, 1999. 36 с.

14. Артемьева И. Л., Суров В. В. Разработка методов решения задач для одного класса систем логических соотношений: Препринт. Владивосток: ИАПУ ДВО РАН, 1999. 52 с.

15. Артемьева И. Л., Суров В. В. Разработка методов решения подзадач для одного класса систем логических соотношений: Препринт. Владивосток: ИАПУ ДВО РАН, 1999. 29 с.

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