Создание математических моделей задач на основе баз знаний, представленных в виде алгоритмических моделей

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

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

— Object соответствует объектам концептуальной модели и содержит перечень объектов ПО.

— StrType определяет типы объектов, представленных в Object.

— Parameters определяет параметры объектов ПО, не являющихся объектами. Параметры могут быть любого из типов данных, поддерживаемых СУБД.

— Ratio_Type определяет типы (семантику) отношений в ПО.

— Ratioes соответствует отношениям концептуальной модели и содержит их полный перечень.

— Obj_Ratio реализует логическую связь Ratioes-Object типа М:М.

— Events обеспечивает организацию обслуживания событий в порядке очередности поступления.

— Correlations соответствует методам концептуальной модели.

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

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

InterBase Server (STORED PROCEDURE, UDF, EVENT), и специально разработанного сервисного модуля, обеспечивающего реализацию фиксации генерируемых БД событий и вызов соответствующей хранимой процедуры для означивания нужных параметров объектов. Эти хранимые процедуры служат средством использования той или иной функции из библиотеки, предоставляющей набор разработанных UDF, состав которых может быть изменен или дополнен при необходимости введения других правил означивания параметров объектов. Механизм такого моделирования динамики функционирования модели ПО представлен на рисунке 3.

Для реального наполнения БД объектами ПО, установления требуемых семантических связей между ними разработан блок администрирования БД в виде компонента ActiveX «Управления иерархической базой данных» для ОС Windows, реализующего соответствующие интерфейсы ввода и корректировки информации с помощью оконных форм. Первоначальная структура создается на этапе подготовки системы к применению и открыта для пополнения и изменения по мере создания новых структур данных, требующих данные о других объектах ПО.

Компонент «Управления иерархической базой данных» был использован в системе мониторинга состояния учебного процесса Ростовского военного института ракетных войск. В виде объектно-иерархической модели ПО была представлена информация о структуре показателей качества функционирования вуза, характеризующих все виды обеспечения с необходимой детализацией, о причинно-следственных связях между ними, необходимых ресурсах и их потребностях для изменения состояния учебного процесса.

Список литературы

1. Цаленко М.Ш. Моделирование семантики в базах данных. - М.: Наука, 1989. - 288 с.

2. Полякова Л.Н. Создание иерархической структуры данных в среде MS SQL Server// Программные продукты и системы. - 2001. -№2. - с. 5-9.

3. Виноградов С.А Моделирование иерархических объектов. - http://www.citforum.ru/database/articles/tree.shtml, 2001.

4. Поляков А.О., Семенов И.А. Представление знаний и объектно-ориентированная СУБД Cache.- http:// www.inf-tech.webservis.ru/it/ii/ar4.html

5. InterBase SQL Server 5.5: Language Reference. - InterBase Software Corp. Tech Pubs, 1999. - 304c.

СОЗДАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ЗАДАЧ НА ОСНОВЕ БАЗ ЗНАНИЙ, ПРЕДСТАВЛЕННЫХ В ВИДЕ АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ

В.П. Морозов

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

является привлечение компьютерных систем, основанных на знании. В качестве примера можно назвать систему САПФИР-АСС, которая создается в рамках методологии автоматизации моделирования,

разрабатываемой в Санкт-Петербургском институте информатики и автоматизации РАН [1,2], и является дальнейшим развитием предшествующего ряда систем САПФИР-КОГНИТРОН [3,4].

В подходе, ориентированном на поддержку принятия решений в областях математической и компьютерной некомпетентности пользователей [5,6], формирование математической модели в системе САП-ФИР-АСС сводится к следующему.

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

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

Заключительный этап - распознавание математической модели, заданной пользователем. Этот этап - компетенция исключительно системы САПФИР-АСС, и пользователь о нем может даже не догадываться. Далее система самостоятельно либо совместно с пользователем выбирает метод решения и использует его для получения возможных вариантов решения [6].

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

х8=х1+х2+х3,

х9=х2 - х8*х4,

х10=х9+х5+х6+х7.

Будем считать, что имена переменных в (1)-(3) полностью соответствуют именам переменных в предметной области. Рассмотрим, как будет происходить создание математической модели задачи в этом случае.

Первый этап. Пользователь формирует множество предметных переменных, определяющих, по его мнению, суть решаемой задачи. Пусть предметные переменные носят имена х8, х1, х2, х3. Пользователь вводит имена в систему. Система проверяет наличие введенных переменных в БФО, находит выражение (1), их содержащее.

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

ременной х1 больше 1, но меньше 3; значение переменной х2 равно 5; значение переменной х3 больше 1, но меньше либо равно 2, а значение переменной х8 равно 9.

Третий этап. Система анализирует полученную информацию и по характеру заданных областей определения переменных приходит к выводу, что математической моделью задачи, которую пользователь только что сформулировал, является уравнение х8=х1+х2+х3 с областью допустимых значений переменных х1е (1,3), х2е [5,5], х3е (1,2], х8е [9, 9].

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

При наличии в БФО системы САПФИР-АСС множества предметных переменных формируемой задачи проблем с построением ее математической модели не возникает. Однако, если часть, а то и все множество переменных, определенных пользователем, отсутствует в базе функциональных отношений, процесс построения модели задачи прекращается, о чем пользователю выдается соответствующее сообщение. Так произойдет, например, в случае, когда пользователь считает, что смыл решаемой им задачи определяют переменные х1, х2, х3, х13 и вводит их в систему (переменная х13 в БФО системы отсутствует).

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

Согласно определению [1], алгоритмическая модель (АМ) есть алгоритм, структуризация вычислительных процедур которого произведена в соответствии с представлениями разработчика о причинно-следственных или временных связях явлений, характеризующих моделируемый объект. Итак, представление БФО системы в виде выражений (1)-(3) в нашем примере отражает представление разработчиков системы о предметной области, для решения задач которой система и предназначена.

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

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

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

Сформулируем условие, являющееся необходимым для выполнения нашего предположения.

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

х10 =

Любая модель, описанная в рассматриваемом подмножестве языка алгоритмических сетей, относится к классу рациональных (дробно-рациональных) алгебраических функций [7], и может быть представлена суперпозицией функций х+у, х-у, х*у, х/у.

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

Отсюда необходимым условием возможности решения задачи при отсутствии предметной переменной в БФО системы является выполнение соотношения п < N где п - степень детализации модели; N - максимальная степень детализации модели.

Вернемся к нашему примеру. Для выражения (4) п=2, N=6. Соотношение п < N выполняется, следовательно, возможно решение поставленной задачи за счет детализации модели, хранящейся в БФО. Ниже приведен пример соответствующей детализации: х12=х1+х3, х13=х12+х2, х11=х13*х4, х9=х2 - х11, х14=х6+х7, х15=х14+х5, х16=х9+х15. Заметим, что данный вариант разбиения не является единственным. В силу коммутативности операции сложения, связывающей переменные х5, х6 и х7, можно предложить другую последовательность суперпозиций и соответствующее ей множество функций, например:

х12=х1+х3, х13=х12+х2, х11=х13*х4, х9=х2 - х11, х14'=х5+х7, х15'=х14'+х6, х16=х9+х15'.

Вернемся к постановке задачи, которая не могла быть реализована в рамках технологии САПФИР-АСС по причине отсутствия в БФО предметной переменной х13. В результате детализации АМ, хранимой в БФО, она появилась. Поставленная пользователем задача может быть решена.

Рассмотрим еще несколько примеров возможной реструктуризации выражения (4):

х8=х1+х2+х3,

х11=х8*х4,

х9=х2 - х11,

х10=х9+х5+х6+х7.

Как видно из примера, в результате суперпозиции функций (5)-(8) появилась новая, по сравнению с исходным представлением модели, предметная пе-

ременная х11.

Другой пример:

х12=х1+х3,

х13=х12+х2,

х11=х13*х4,

х9=х2 - х11,

х10=х9+х5+х6+х7.

В результате суперпозиции функций (9)-(13) появились три новые переменные х11, х12 и х13, а переменная х8 исчезла.

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

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

1. Система осуществляет проверку степени детализации имеющейся у нее модели предметной области. Если степень детализации БФО не является максимальной, переход к пункту 2. Если степень детализации максимальна, с помощью данной БФО решить поставленную задачу нельзя, пользователю выдается соответствующее диагностическое сообщение. Конец работы процедуры.

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

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

4. Система определяет наличие еще не просмотренных пользователем фрагментов БФО, которые можно детализировать. Если такие фрагменты есть,

переход к 2. Иначе пользователю выдается соответствующее сообщение. Конец работы процедуры.

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

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

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

Следует отметить, что вышеизложенное может послужить основой для изменения подхода к хранению информации об АМ, принятого на сегодняшний день в системах автоматизации моделирования САПФИР-КОГНИТРОН [3,6]. Речь, прежде всего, идет о возможности сжатия базы АМ. Сжатие осуществляется за счет того, что в базе системы хранит-

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

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

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

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

2) резко сократить количество промежуточных переменных, участвующих в проведении расчетов (по предварительным данным сокращение может составить до 30% от общего количества ныне участвующих в расчетах переменных), что обеспечивает экономию памяти и сокращает время решения задач.

Список литературы

1. Иванищев В.В., Марлей В.Е. Введение в теорию алгоритмических сетей. - СПб.: Изд-во СПбГТУ, 2000. - 179 с.

2. Иванищев В.В., Марлей В.Е., Морозов В.П. Система автоматизации моделирования САПФИР-Искра. Основы построения системы. - Л.,1989.- 63с. - (Препр. /ЛИИАН; №99).

3. Иванищев В.В., Морозов В.П., Михайлов В.В., Быков Я.А., Костельцев А.В. Система искусственного интеллекта для моделирования. - Проблемы информатизации: теоретич. и науч.-практич. журнал / РАН, Мин. науки и техн. политики РФ. - М., 1996.- Вып. 1. - С.51-55.

4. Морозов В.П. Технология построения моделей и решения задач в системе автоматизации моделирования САПФИР-Искра87 // Вопросы алгоритмического моделирования сложных систем. - Л.:ЛИИАН,1989.- С.32-49.

5. Морозов В.П. Программные системы, ориентированные на привлечение знаний экспертов в процессе решения задач. // Программные продукты и системы. - №1. - 2001. - С.33-35.

6. Морозов В.П. Система интегрированного управления проектами САПФИР АСС // VII Междунар. конф.: Региональная информатика-2000 ("РИ-2000", Санкт-Петербург, 5-8 декабря 2000 г.)/ Тр. конф. - СПб., 2001. - С.283-285.

7. Морозов В.П. Задачи на вычисление при наличии ограничений. Метод обращения // Алгоритмическое моделирование, инструментальные средства и модели. - СПб.: СПИИРАН,1992. - С.112-137.