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

АКАДЕМИЯ НАУК СССР

ВСЕСОЮЗНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ СИСТЕМНЫХ ИССЛЕДОВАНИЙ

Специализированный совет Д 003.63.02

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

УДК 519.68

ЮРЧЕНКО Валентин Владимирович

РАЗРАБОТКА АППАРАТА ФУНКЦИОНАЛЬНЫХ СЕТЕЙ ДЛЯ ПОСТРОЕНИЯ ИНТЕГРИРОВАННЫХ ЧЕЛОВЕКО-МАШИННЫХ СИСТЕМ

Специальности:

01.01.11 — Системный анализ и автоматическое управление,

05.13.16— Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

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

МОСКВА 1991

Работа выполнена во Всесоюзном научно-исследовательском институте системных исследований АН СССР.

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

член-корреспондент АН СССР 10. И. ЖУРАВЛЕВ доктор физико-математических наук Б. Н. ЧЕТВЕРУШКИН доктор технических наук В. Л. АРЛАЗАРОВ

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

Институт проблем передачи информации АН СССР

Защита состоится <?. » МОЙ_1991 г. на заседании

специализированного совета Д 003.63.02 при Всесоюзном научно-исследовательском институте системных исследований АН СССР по адресу: 117312, Москва, проспект 60-летия Октября, д. 9.

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

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

Ученый секретарь Специализированного Совета доктор физ.-мат. наук

В. С. ЛЕВЧЕНКОВ

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

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

История спецификации вычислений началась задолго до появления первых ЭВМ с теоретических работ по вычислительным моделям и теории алгоритмов - машина А.Тьюринга, система продукций А.Поста, лямбда-исчисление А.Черча, нормальные алгоритмы А.А.Маркова, машины А.Н.Колмогорова. Эти и другие работы заложили основы современной теории программирования, но не смогли выполнить роль спецификации вычислений в практине программирования. Эту функцию выполняют универсальные языки программирования высокого уровня такие как ПЛ/1, АДА, СМОЛТОК и др. Однако, как показала практика, эти языки плохо приспособлены для роли базовой математической модели вычислений, поскольку они перегружены деталями описания конкретных алгоритмов и сильно привязаны к традиционной фон-неймановской архитектуре ЭВМ.

Примером удачного компромисса между классическими моделями вычислений и алгоритмическими языками программирования являются функциональное и логическое программирование. Языки функционального программирования (ЛИСП Дж.Маккарти, РЕФАЛ В.Ф.Турчина) реализуют идеи А.Черча и Э.Поста. Логическое программирование реализует спецификацию задач на базе математической логики.

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

I-I

зования графов для спецификации вычислений доказана при разработке операторных схем Ю.И.Янова, графов потока данных, вычислительной модели Э.Х.Тыугу. В настоящее время наблюдается значительное расширение области применения графовых моделей в информатике: визуальное программирование, описание структуры данных (сетевая модель данных, ЕН-модель П.Чена), описание диалога графами переходов, представление знаний семантическими сетями.

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

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

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

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

Связь с плановыми работами. Диссертационная работа випол-нена п СООТЕ9ТСТВШ1 с планом научно-исследовательских работ ВНШОИ АН СССР в рамке* теми "Ко!шыотврноэ моделирование" (N гос. регистрации 01890023505).

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

Исследованы особенности управляемой запросами и дашшми прямой интерпретации ФС. Разработан алгоритм управляемой запроса,1,Gf интерпретации рекурсивных ФС, реализаций управление взаимодействием сопрограмм.

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

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

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

На ФС-модели сформулирована задача оптимизации диалога для интерактивных задач. Разработаны методы решения этой задачи. Разработан алгоритм синтеза интерактивного решения на И/ИЛИ ги-порграфе поиска решений со взаимно зависимыми гипотезами. Установлено соответствие мекду ФС-моделью и этим гиперграфом. Полученные решения использованы для интеллектуализации человеко-машинного интерфейса.

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

ПОМОЩЬЮ ФС-МОД9Л9Й.

1-2

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

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

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

Апробация работы. Результаты диссертации докладывались на семинаре Национального исследовательского института информации и автоматики (1980 г., Франция); на заседании комиссии по применению ЭВМ в процессах управления координационного комитета АН СССР по вычислительной технике (1980 г, Цахкадзор, Армянская ССР); на международном совещании по проблемам системного обеспечения принятия решений (1980, НАБА, Лаксенбург, Австрия); на 2-й Всесоюзной конференции по проблемам управления развитием систем (Курс-2, Таллинн, 1982); на Всесоюзной конференции "Методы трансляции и конструирования программ" (Новосибирск, 1988); на Всесоюзной конференции "Теория, методология и практика системных исследований (Москва, 1984); на 10-м Всесоюзном совещании по проблемам управления (Алма-Ата, 1986); на Международной рабочей конференции "Реализм моделей" (Бад Хоннеф, ФРГ, 1982); на Всесоюзной конференции "Математическое моделирование. Нелинейные проблемы и вычислительная математика" (Звенигород, 1988); на 2-м советско-американском симпозиуме по общей теории

- б -

систем, кибернетике и управлению (Таллинн, 1988); на постоянно действующем научно-техническом семинаре ВНТО приборостроителей им. 0.И,Вавилова "Современная технология производства приборов, средств автоматизации и систем управления" (Ленинград, 1990).

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

Структура диссертации. Диссертация состоит из введения, 7 глав, заключения, списка литературы из 106 наименований, 3-х приложений. Объем основного текста диссертации 286 страниц.

СОДЕРЖАНИЕ РАБОТЫ В первой главе обсуждаются особенности интегрированных ЧМО а их спецификации, а также дается определение функциональных сетей, их классификация и семантика.

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

К базовой спецификации предъявляются следующие зачастую противоречивые требования: универсальность, полноте, "понятность" для человека и ЭВМ, полная формализованность, пригодность для поддержки жизненного цикла ЧМО. Анализ работ по теории алгоритмов, вычислительным моделям, языкам программирования, средствам представления диалога и знаний, а также по общей теории систем дает основание в качестве исходной идеи для построения базовой спецификации интегрированных ЧМО выбрать идею функциональной сети и привлечь к ее разработке аппарат функционального программирования и теории графов.

Определение 1.1. Двудольный ориентированный 'Граф

С - (Х,Е,й) называется графом функциональной сети, если выполняются следующие условия:

1) (*ев Е)(эх « Х){(е,х) « ),

2) гР) (е,,х)) Л (ег,х))) -»

((е,- вг) Л <£>))\, где X - непустое конечное множество объектов, Е - непустое конечное множество элементов, V - непустое конечное множество дуг такое, что й - Л 0°, Л С0- о, ХхЕ,

О1- конечное множество входных дуг, 1Р- непустое конечное множество выходных дуг.

Введем ряд вспомогательных определений. Множество X называется множеством вависимых объектов графа С, если С*х т Хг)(вв « Е)((в,х) « ТР). Множество Xх- X - Хг называется множеством входных объектов графа С. Множество X1* X2 навивается множеством выходных объектов графа С, если Сух « Х1)(Ув в ЕЯСлг.е; * о1). Множество X называется множеством входов элемента в в Е графа С, если С^х « Хе)((х,е) л Т?-). Множество У®<= X называется множеством выходных объектов элемента в « Е графа С, если (*У • Уе){(е,у) е I/5).

Пусть С = (с) - множество значений, Е = (/) - множество

функций таких, что /: п * п где .4*« 2°, В^« 2°. Мно-

к-1 * 3 К 3

жества Лг= (Аи В*= будем называть соответственно множествами входов и выходов функции /.

Пусть с ~ (С) - непустое множество графов функци-

ональных сетей, а С = (Х,Е,П) - некоторый граф такой, что С « с и задано разбиение Е на два непересекающихся подмножества и Ем. Будем в дальнейшем элементы Е5" называть элементами-функциями, а Е1*- элементами-сетями.

Определение 1,6. Тройку Я - (й,!*), где С « с, С - (Х.Е.Ъ), Е - Ери а Гфр.ф и Iй- (ф^ф - соответственно спецификации элементов-функций и элементов-сетей такие, что фу.- Е*1- Р, Б*1-» 1(Х 2°)}, ц^: ш,

е"-» ((X -» 2х )), N - непустое множество функ-

циональных сетей, Xе- объединение объектов X всех графов из с, будем называть функциональной сетью, если справедливо следующее:

I) (Уе « £рл(фр(е; =/)*-* ; Xе* АТ) Л

гфв; : Ув- в1))], где - биективное отображение Хеи Уе па /ги в*;

2) (Уе « ^ЖГ^Ге; -/(V -»

: Xе- Х*х) ~ : У*- х'*))),

где ф^Ге; - инъективное отображение У® в X .

В приведенном выше рекурсивном определении ФС функции фр и фд ставят в соответствие каждому элементу из Е, либо функциональную сеть из т. Функции ф£(е) для каждого элемента е « Е ухазивают связь его входов Xе и выходов Уе с аргументами и выходами соответствующей / - фр(е). Функции же описывают соответствие входов и выходов (Xе и У6) элемента в с объектами некоторой сети Н*, представляющей этот элемент.

Пусть Г = (У,Ц) - корневое ориентированное дерево, на котором заданы функции аннотирования о/1 и ш*, где V - (и) - множество вершин дерева Т, и0<е V - корень дерева Т, и - Iи) - множество дуг дерева Т, и с V х Ч, от: V -» и, и - (И) - множество

®С, V -» 1(2^-* V)}, - объединение всех элементов всех сетей из и.

Определение 1.6. Аннотиропанное дерево Т (Т,^,^) нам

аываотся деревом ФС //*, если выполняются следующие условия:

1) ьР(и0) - Н*;

2) (VI) « « Е)1(е в

(зЪ « 7)(((и,Ь) - и) Л (ы7(о)(в) - ~ Гф^Ге; - чР(Ъ)))), где ¡Рс Е, Е - множество элементов функциональной сети

и - ш"ги;.

Аннотированное дерево можно расматривать в качестве альтернативного определения ФС N. Выделяются следующие типы ФС.

Сеть N называется простой, если 2м- о (что эквивалентно 171 - I).

Функциональная сеть, представленная деревом Тд" ((V.и) ), называется сетью о переменной структурой, если существует v • V такая, что в сети аг(и) существует элемент-функция в, для которой имеет место « Б, где Б - (в^) такие, что ак(г0,х1,...,х1с) - хх , г0« {I.....к). В дальнейшем

ак будут называться селекторами, х0- их управлениями, а х^ (й «• 0) - альтернативами.

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

Сеть N называется иерархической, если множество V вершин его дерева конечно и |У| > I.

Сеть Я называется рекурсивной, если ее дерево неограни-

чено.

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

F(x) ' Щр(х),f(x),F(g(x))), где р, /, g - функции, определения которых не содержат функцию F. Несмотря на простоту, этот класс функций соответствует часто встречающимся на практике итеративным программам, описывающимся выражением

WHILE лр(х) DO x:-g(x); x:-f(x), где ч - знак логического отрицания.

Рис. I. Стандартная структура простой рекурсивной функциональной сети.

Перейдем к определению семантики ФС. Частичную функцию б: I -» С будем называть памятью ФС, а множество X, на котором определена 0, - множеством заданных объектов.

Память 9 называется согласованной, если выполняются следующие условия:

1) (ух* • х+)(зе в Е^ЩфрГе; л. (х** уе)) _»

(ух в Xе- (^.....х^жх « ~

Г0(х*; » дегх^.....в(хп^л);

2) ГУХ* - в в'^КСФрГв; « Б) л (х*« Уе; ^

(Xе* 1х0,х,,...хп)))

3) (ух* « х+)(эд « Vе; (9(х*) -

где 6*- согласованная память ФС Л*- ф^е; такая, что

(Ух - Х**)(в*('х) -где X**- множество входных объектов сети значения которых необходимы для согласованности памяти 0*, определенной на <^(е)(х*). Эти условия требуют определенной согласованности между значениями выходных и входных объектов элементов ФС.

Легко видеть, что описание функциональной сети N эквивалентно определению некоторого отображения Ф^ С {X —* С)} —* С(X -* С)}, которое каждой функции 9 (т.е. памяти сети) ставит в соответствие другую функцию (память). В этом случае неподвижная точка этого отображения является согласованной памятью сети.

Пусть на входах Xх сети N заданы частичные функции Ир* (IX), ц: Xх-* С (входные данные сети и). Тогда сеть N можно интерпретировать как некоторое отображение

—» С(I —♦ С)}, которое описывает, как по входам (1 строить согласованную память 8 - Ф^(ц).

Тройку Я - (Я,^,г) будем называть элементарной задачей на ФС, где г « X - элементарный запрос к сети. Задача Н формулируется следующим образом: для заданной ФС И и заданных входных данных ц найти значение запроса г.

Согласованная память тСд функциональной сети Я будет называться решением вычислительной задачи Н, если Хд определена на г а (ух в х+п Хх)(хк(х; - \\(х)).

Согласованная память Хд функциональной сети Н называется решением интерактивной задачи Я = (Н.ц.г), где ц задана на х'оГ1, если Яд определена на г, (ух « Х+г> X*)(кп(х) » \1(х)) и (УХ « (Xх- X*))(1С^(х) = 0(х)), где функция 0(х) отражает формирование значения входного объекта х либо человеком в процессе диалога, либо некоторым внешней по отношению к данной ФС

объектом (например, интеллектуальным интерфейсом). Очевидно, что при фиксированных Н,р.,г решение интерактивной задачи оудет зависеть от С. Следовательно постановка интерактивной вадачи Я = (И,\х,г) в отличие от вычислительной подразумевает неоднозначность ее решения.

В простейшем случае описание функциональной сети И мокно рассматривать как спецификацию некоторой вычислительной процедуры, соответствующей отображению П Сх - п Сх, х«=Хх хеХ2

где Схс С - допустимые значения в(х) всех допустимых состояний памяти в. Поскольку сеть К допускает Ы = \XZ\ различных элементарных запросов гк, к = Iто N можно рассматривать также в качестве спецификации и вычислительных процедур С1г: П » С .Эти процедуры могут Оыть реализованы либо с по-х.Х* к

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

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

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

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

(Гн.ше), где Т}; - дерево ФС N. ш8: V -» в, Ь - множество памятей подсетей. Особенность алгоритма заключается в том, что в процессе интерпретации запоминается история обхода дерева

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

Теорема 2.2. Решением интерактивной задачи Я - (11,\1,г) на иерархической ФС JN,шv/) является па-

мять тс^ такая, что для любого х*« Л* - объекта сети ^(у*/! - тс^х ) - 0 (х*,), где V, 6*= (^(и*; - согласованная память, построенная при обходе дерева сред.

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

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

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

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

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

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

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

Процедурной моделью диалоговой системы будем называть четверку (СР.Ид.ф.С};, где (Р- (VР,!Р) - ориентированный граф, Ур- его вершины, ¡Рс Урх Ур - ориентированные ребра, и0« Ур, О - множество операторов - составных частей ЧМО, ф : Ур-» д - функция, которая каждой вершине графа (Р ставит в соответствие некоторый оператор. Ребро (и.,,^) графа описывает передачу управления на оператор ф(и2; после вычисления оператора ф('и1 Вершина и0 указывает оператор ф(и0), с вычисления которого начинается функционирование ЧЫС №р.

Множество операторов 4 разбивается на четыре непересекающиеся подмножества С) - ^и О^и фи ф. ф соответствуют вычислительным процедурам, с}1 - вводу информации, ф- выбору альтернативного пути продолжения расчетов, ф - окончанию работы. Пример процедурной модели изображен на рис 2.

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

Реализация традиционных элементов диалога выполняется за счет специальной реализации в интерпретаторе функции диалога 0(т):

- если затребованный интерпретатором входной объект сети является управлением какого-либо селектора, то по аналогии с операторами Ы. процедурной модели ЧМС человеку предъявляется меню,

в котором перечислены альтернативы данного селектора, и от него

»1

Рис. 2. Пример процедурной модели ЧМС.

требуется ввод номера предпочтительной альтернативы.

- если затребованный интерпретатором входной объект сети не является управлением ни одного из селекторов, то по аналогии с операторам! 1к процедурной модели ЧМС у человека запрашивается ввод значения этого объекта.

Последовательность а^ <а1____>, где а^ С будем называть сценарием работы ЧМС. Предполагается, что ЧМС работает по сценарии а^, если человек при каждом обращении к нему за значением входных данных будет последовательно выбирать их из последовательности а^.

Определение 3.1. Сценарий ,....с^ > называется до-

К

пу стоил л для заданной ЧМС, если при работе по этому сценарию ЧМС введет все значения о^ и после ввода с^ завераит свою работу.

Очевидно, что любую модель ЧМС N мокно рассматривать как отображение 9И: Г1}, где Ад - множество всех допустгалых для данной ЧМС сценариев, а Г}} -.множество всех возможных последовательностей Т^^^»-■ • таких, что Я для процедур-

ных

моделей или ? ~ Для функциональных (здесь / включает

все функции и операции ввода значений входных объектов сети). Определение 3.3. ЧМС эквивалентна /Л,, если =. ен .

"к

2

Б

Другими славами, человеко-машинная система эквивалентна И^, если любой допустимый для сценарий а* будет допустимым и для »2- 8 Т2= V где 71= вн Га*;, т2= ^а).

На рис. 3 изображена ФС, специфицирующая диалоговую систему, аквивалентую системе, заданной с помощью процедурной модели, изображенной на рис. 2 (здесь элементам соответствуют "пустые" операторы, не производящие никаких действий).

Рис. 3. Пример функциональной модели ЧМС.

уеотема 3.2. Для произвольной процедурной модели ЧМС всегда можно построить эквивалентную функциональную модель, имеющую вид рекурсивной функциональной сети.

Теорема 3.3. Любая простая ФС, не содержащая вычисляемых селекторов,может быть преобразована в эквивалентную процедурную модель (СР.ид.ф.О;, где С?- дерево.

Теорема 3.4. Для любой ФС с праволинейной рекурсией,не содержащей вычисляемых селекторов, можно построить эквивалентную процедурную модель.

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

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

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

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

Четвертая глава посвящена синтезу вычислительных программ ЧМС. Тесная связь ФС-моделей с функциональным программированием позволяет для . любой задвчи Я= (/Г,ц,г) синтезировать решающую ее функциональную программу (аппликативное выражение) в ходе регулярного обхода соответствующего графа. Для решения всех возможных задач на заданной сети N разработан алгоритм построения системы безаргументных функций, который каждому объекту х • X сети N ставит в соответствие описание одной безаргументной функции <рх по следующему правилу.

1) Если х « Хг, то (фх; - (I (<РХ^'-'(<РХ )))>

где: 1 - / - фр(е;; е « Е такой элемент, что х в уе;

- безаргументные функции, которые определяются для х^ X так пэ, как <рх; (х^а Xе) ~ (х±- (<^(в)Г1 (л\))\ п - |Хв|.

2) Если х л Xх, то Сфх/) - (ТЯ где 1х- т^(х), а функция Ш определена следующим образом:

{0(х), если ц(1) не определена на х,

ц(х), если щи определена на х, где т?: Р Ь, I - множество строк, определешшх на некотором алфавите (I можно интерпретировать как множество имен процедур, реализующих функции Р).

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

ГР1 ц] ... ^ } " ••• "ь "г ... "к ;

и} Г?1+1 (1Ч и^ ... и|+1... и£+1 ,

1-8

- 16 -

Л 1 ^ 1 ~

где и^е 1 и 1 <= 1 - некоторые имена такие, что тр (и^ « Л, а

т/ (I & т.е. и? - имена объектов X, а I * -

е«Е г 1

имена функций, связанных с элементами Е.

ФС-модель так же удобна в качестве исходной спецификации задачи автоматического синтеза процедурных программ ЧМС. Очевидно, что для простых ФС с фиксированной структурой алгоритм такой программы образует упорядоченная последовательность элементов ФС, которая легко синтезируется управляемым данными интерпретатором. Для задачи Д = (К,р.,г), определенной на сети N с переменной структурой, задание р. для всех входов однозначно определяет значения управлений всех селекторов, т.е. однозначно определяет некоторую сеть с фиксированной структурой, которую будем называть реализацией сети N.

Теорема 4.2. Алгоритм решения всех допустимых вычислительных задач на простой ФС можно представить в виде дерева, удовлетворяющего следующим условиям:

1) число листьев дерева равно п.^ - числу различных реализаций исходной ФС;

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

В диссертации разработан алгоритм синтеза подобных деревьев.

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

(х^,...,хп), ( = 1,...,П (I)

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

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

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

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

В главе 5 исследуются возможности спецификации с помощью ФС распределенных ЧМС и ЧМС реального времени.

Определение 5.1. Пусть задано конечное множество ш1- (N1 функциональных сетей. Пусть на этом множестве определена функция (( и и Л?, Л, где хН и А?. соответственно N«0* " и пи

гагожество входных и зависимых объектов сети N. Обозначим через а - <Я^,...,Нт> некоторую последовательность сетей Я^е т1, такую, что

(УЧ^ I - 2.....П)(зЛ х^яэу1« Х^Жу1- х1; ~

= У1"1 Л,

где у*«— X1 означает зависимость у1 от х* (т.е. наличия пути из х в у в соответствующем графе).

Если А.0 такая функция, что для любой последовательности а справедливо Нт, то двойку №= будем называть рас-

пределенной функциональной сетью (РФС).

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

Определение 5.2. Распределенной человеко-машинной Системой (РЧМС) называется тройка ,11е), где Нь- - рас-

пределенная ФС, №= - граф сети '¿Ш, - множество ЭВМ

сети (|РС| - |ИЬ|), 1Сс р° - множество каналов связи,-соединяющих ЭВМ, и1—► рс - биективное отображение, задающее распределение функциональных сетей по ЭВМ.

В диссертации разработаны алгоритмы управляемой запросами

и данными децентрализованной интерпретации ФС в РЧМС. При этом рассмотрены следующие варианты:

- последовательное решение еадачи на распределенной вычислительной системе;

- решение одной задачи И параллельно на нескольких ЭВМ сети;

- параллельное выполнение нескольких задач в одной распределенной ЧМС; - параллельное выполнение отдельного подзапроса г^ в узле сети ЭВМ.

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

Модель ФС является удобным инструментом для проектирования распределенных ЧМС. Пусть задана некоторая ФС N и сеть ЭВМ в = (Р,1). Требуется найти такое разбиение множества Е на подмножества Е^ и их распределение по процессорам Р, т.е. функцию А.: (£к) Р, что получающаяся в результате распределенная ЧМС будет оптимальной в некотором смысле. В качестве критерия оптимальности можно использовать разные характеристики функционирования распределенных систем. В качестве примера рассмотрим минимизацию времени выполнения некоторого указаннбго запроса.

Пусть задана некоторая ФС N - в - (Х,Е,й) и

некоторая сеть ЭВМ, топология которой описывается ориентированным графом Л°= Пусть также заданы некоторые характеристики сетей N и №, включающие:

- рк - пропускную способность линии связи 1к« 1° (единиц информации в сек.);

- - оперативную память ЭВМ а« Р° (единиц информации); -р. - быстродействие ЭВМ рке Р^ (инструкций в сек.);

- т® - трудоемкость функции, представляющей элемент е^« Е (число инструкций);

- т^ - оперативную память, необходимую для выполения связанной с элементом е^« Е функции (единиц информации);

- - размер объекта X (единиц информации).

В качестве неизвестных в задаче оптимизации распределенной ЧМС будут использоваться элементы у^^ матрицы К, где

I - I.....КЕ, ] - I.....Кр, (0,1), Хк= |Б| и

{I, если элемент е,<= Е размещен на рР°;

1 3

О, если нет на р Тогда в общем виде задача оптимального распределения ФС по заданной сети ЭВМ имеет следующий вид:

Y = arg min (Тр+ Zy,

Y " Я 8. Уц ' (0,1),

*Р

2 !/ij * '' 1 "i»•. • .ÄE,

J=1 KE

"5 * ¿yiJ mi' J " 1.....

Здесь Гр и TL - время, затраченное соответственно на вычисление всех необходимых выходов элементов WD и на передачу информации по линиям связи сети ЭВМ.

Для описания коммуникационных возможностей сети ЭВМ построим матрицу 1С « Ц iri;j Ц, l,J - 1,...,Кр такую, что ici;j равно минимальному времени, необходимому для передачи единицы информации из pj^ в р^ в сети ЭВМ №. Так, если fl1,...,lm ) -

к

последовательность poöep l^e L графа К , соединяющая р^ с р^, то (7^

х. . - min S -i- ,

" Ч m=1 Рш где ßm - пропускная способность линии связи lm.

В качестве исходных данных, характеризующих ФС, введем е = I^ji - квадратную матрицу ЯЕ* КЕ, • описывапцув функциональные зависимости между объектами ФС:

I, если единственный выходной объект элемента е.« Е является входным объектом элемента е^;

. О, в противном случае.

Вид Тр и Т^ существенно зависит от типа ФС и деталей постановки задачи оптимизации. В простейшем случае ФС с фиксированной структурой и единственным выходом (фиксированным запросом) они имеют вид:

КЕ «Р 1?

р 1=1 ;М 13 Р^

^ ^ % Кр ТЬ * 2 П1 еИ ' 2 2 У1к «1т

ь 1=1 ■ ¿=1 13 к=1 т-1 1К зт 1011

где т* - размер выходного объекта элемента е^.

В диссертации рассмотрены та1ске и другие постановки задачи оптимального распределения ФС. Аналогично формулируется и задача проектирования оптимальной сети ЭВМ по заданной ФС и заданным на плоскости координатам узлов сети ЭВМ.

Предположим известны функции ср- /р(р,иР) и с1-описывающие зависимость отоимости ЭВМ ср от ее быстродействия и памяти и стоимость линии связи с1 от ее длины и пропускной способности. Задача построения распределенной ЧМС минимальной стоимости С0 при заданных ограничениях на время выполнения каждого запроса г4 формулируется следующим образом: Кр кр р

Уюп'Р*

^Кт'

КЕ

£ Уи-1 . у±л - го,и ,

о * р^ 3 В , 0 * >£ Мр , О й рк * яр

е

хп

Ъ КР

- < 2 . £П1 м 3 Упк Уы

1«ТЕ к=1 111=1

1 ^ 1е1и

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

- время, затрачиваемое на вычисления по запросу г^;

Т^ - время, затрачиваемое на пересылку данных по запросу г^;

- общее ограничение на время выполнения запроса гф

В - максимально допустимая пропускная способность линий связи;

Мр - максимально допустимая память одной ЭВМ;

Яр - максимально допустимое быстродействие одной ЭВМ;

множество индексов элементов, входящих в г^-фрагмент ФС У; 1Скп/Ч ~ элеМ0НТ матрицы "скорейших путей" из пункта рк в

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

Основу систем реального времени (СРВ) составляют такие понятия, как сигнал прерывания, процесс, приоритет, событие, введенные для ЭВМ традиционной фон-неймановской архитектуры. В диссертации разработаны их функциональные аналоги и алгоритмы их интерпретации. На ФС множество Н функциональных прерываний определяется, как 2 с X * А^, где Х^ - множество натуральных чисел, определяющих приоритет сигналов прерывания. Таким образом, с сигналом прерывания £ - (х,й) связан объект х, значение которого необходимо рассчитать. Как и в ЭВМ с традициогаюй архитектурой, с каждым функциональным прерыванием ассоциируется свой процесс рх= (ЯХ,8Х), обеспечивающий расчет объекта х. Здесь: Их - фрагмент сети К, включающий все объекты, от которых зависит х; 0Х - текущее состояние памяти сети N.

Наиболее крупной конструкцией в СРВ является задача реального времени которая определяется как Кк= (МК,80,20,ЯК), где Нп= (Н,2) - ФС реального времени, 90 - начальное состояние памяти сети Н, 30£ 3 - множество исходных запросов задачи, -приоритет задачи. На одной и той же ФС N может быть сформулировано и одновременно выполняться в СРВ несколько задач, отличающихся друг от друга состоянием памяти в.

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

Основу процедуры интерпретации ФС реального времени составляют алгоритмы смешанной интерпретации: при открытии про-

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

В главе 6 исследуются возможности функциональной спецификации ЧМС для интеллектуализации человеко-машинного интерфейса. Необходимость в интеллектуализации интерфейса возникает тогда, когда в формулировке задачи Н » (И,ц,г) заданы такие исходные данные (1, при которых задача не может быть решена (не хватает необходимой входной информации). Основная функция интерфейса -построить такое продолжение р.* функции р., что задача Я* = (Я,\1»,г) превращается в разрешимую. Интеллектуализация интерфейса основана на двух предположениях: при построении ц* человек на запрос системы "Чему равен х?" (т.е. "0(х) - ?") может ответить "Не знаю", а интерфейс для некоторых объектов из Xх сам может сгенерировать значение 0(х) в качестве гипотезы. В диссертации разработан ряд алгоритмов управления процессами диалога и генерации гипотез.

Пусть II - сеть с переменной структурой, а х* такой ее объ-

окт, что (ух*: к - I.....И)(х*е х£), где х£ - множество входов

й-й реализации сети II (т.е. при выборе любой альтернативы во всех селекторах сети Л необходимо знать ц(х»). Очевидно, что опрос человека желательно начинать с этого обязательного объекта, чтобы избежать ненужных диалога и расчетов.

Утверждение 6Л. Для задачи Н - (И,\1,г) обязательными являются следующие входы

х° - X и ( и х°;, г г

гда 5

х и у«хе-{и) у

Xе - множество всех входов селектора, выходом которого является х, а управлением - и. Хр и Хг - разбиение X* такое, что Хгс Xх, Х^с X2. а X* - входные объекты графа, полученного из графа сети N путем удаления дуг, исходящих из селекторов.

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

управлений всех селекторов сети N. При этом предполагается, что Sei1 и каждое управление связано с одним селектором (независимые гипотезы). Таким образом, 1штерфейсу разрешается менять структуру ЧМС в поисках решаемой задачи. Эта постановка эквивалентна постановке вычислительной задачи в системе ПРИЗ Э.Х.Тыу-гу.

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

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

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

Для ранее нэ рассматривавшегося случая взаимозависимых гипотез (один объект управляет многими селекторами) разработана новая конструкция - модифицированный И/ИЛ11 гиперграф и соответствующий алгоритм вывода. Работа алгоритма основана на построении и модификации системы гипотез - последовательности Н - где и^ « U, описывающей порядок, в.котором

интерфейс генерировал гипотезы относительно неизвестных управлений и^ в процессе поиска решения, и матрицы влияния гипотез

- ГГ - l^ijl- Здесь I = I.....|(/|, а J = I,...;NZ,

\XZ\, a»1;j= {"О,IJ. I, если на данный момент интерфейсом сгенерирована система гипотез И, и^« И и объект Xz прямо или косвенно зависит от свободного управления и,. Если же tu« Н

ИЛИ и^е Н, НО Х^ не зависит ОТ Uí, то 0.

В качестве .одной из составляющих интеллектуализации интерфейса анализируются воаможнооти обучения ЭВМ и человека. Обучение ЭВМ основано на использовании контекста беседы 6°: X —* С, некоторого ограничения согласованной памяти, которое используется в задачах в качестве исходных данных ц. Контекст позволяет интерфейсу настраиваться на специфику беседы с конкретным человеком. Кроме того, в ожидании очередного запроса от человека интеллектуальный интерфейс может управлять упреждающей интерпретацией, сам генерируя последовательность промежуточных запросов. Исследованы различные алгоритмы генерации таких запросов с учетом приоритетов ожидаемых запросов, их вероятности, и времени отклика системы. Рассмотрена возможность организации обучения человека на базе реконструкции его модели ЧМС и сравнении ее с моделью реальной ФС.

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

Наиболее распространенной формой представления вычислительных моделей является множество к « (Я^ отношений, заданных

на множестве переменных X = И^я р ^ , где ^ - область

изменения переменной х^ « X.

К1

На практике каждое отношение Н(ху ,...,хп; « к представляется совокупностью Ф » Гф1,...операторов, описывающих отображения <ру. П и - П где Ху У^ (х,.....хп),

* * х Ч

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

Показано, что ФС можно использовать в качестве реализации фреймов. Роль фрейма играет ФС, слотов - ее выходные объекты, присоединенных процедур - ее элементы.

Не трудно видеть, что аннотированные ФС полностью удовлетворяют определению системы продукций. Действительно, в качестве объектов глобальной БД можно использовать объекты ФС с атрибу-

тами ЗНАЧЕНИЕ и СТАТУС. Текущие значения этих атрибутов опреде ляют текущее состояние системы. В качестве продукционных правил, ивмвнясщих атрибут ЗНАЧЕНИЕ, выступают элементы ФС. Предварительным условием применимости элемента-функции является равенство значения атрибута СТАТУС значению ВЫЧИСЛЕН для всех входных объектов этого элемента. Интерпретатор ФС выступает в роли системы управления, обеспечивая некоторую последовательность применений правил (вызовов функций). В качестве терминального условия можно принять переход атрибута СТАТУС указанного в запросе объекта в состояние ВЫЧИСЛЕН.

Что касается семантических сетей и исчисления предикатов, то ФС можно рассматривать как частный случай семантической сети, в которой на произвольных объектах X определено лишь одно отношение - функциональная зависимость. Реализовать исчисление предикатов в полной мере не удалось, т.к. не удалось реализовать процессы унификации и логического вывода, основанного на резолюции и дедукции. Хотя включение в ФС специальных функций И, ИЛИ, НЕ, ИМПЛИКАЦИЯ позволяет моделировать препозиционное исчисление.

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

IF(Xj -- b, л „, л г, -- b, ) THEN (у = а.). (2) 01 ^ 3k ik i

Для подобных систем разработы два эквивалентных представления -ФС на произвольных объектах и ФС на булевских объектах. Во втором случае, если некоторая переменная у принимает значения о,,... .с^, то Еместо этой переменной можно ввести п булевских пэременных у^,...,уп так, что

Ук= ИСТИНА <-♦ у = с^.

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

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

х, , 0-лк' к

о-

I

о-

<?1 ♦0Ч

♦о

V

♦0 Ул

♦0УП

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

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

АЧИ«

а г.

П„«4 Г

где: - АГ

и

мации - дг

- л*-

в

- характерные интервалы времени между поступлением инфор-о наблюдаемом объекте;

- время, необходимое ЭС для постановки диагноза;

- характерное время смены состояния наблюдаемого объекта.

Приближение вывода к реальному времени осуществляется благодаря тому, что возмущения, поступающие на вход ФС на булевских переменных, могут быстро "гаситься" на предикатах

Рк= .....хп) и логических функциях ИЛИ(р1,... ,рш),

И(р1,...,рт). Действительно, в определенных условиях может иметь место равенство

Ох,

•V

йта)

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

,.<*+1> <8,

_(к+1)

■{I

если

если

ы

(к+1)

г в,

"Г} .....

где в - порог, а - веса. При этом пороги и веоа однозначно рассчитываются по структуре исходной <60. Для преобразования, изображенного на рис.б имеем 9 » I и

,<и+1)

-{

г0е) Г1

N

I для Р^к+1ИЛИ, ДЛЯ р]к+1 И.

.(к+1)

4ю ^

й

к+1)

♦О

„(к)

Г(Ю

О :

,(к+1)

О х. к+1)

(к+1)

в)

О)

Рис.5. Преобразование ФС в персептрон:

а) исходный фрагмент ФС;

б) эквивалентный фрагмент персептрона.

В приложении приводится описание разработанной на базе ФС-моделей и функционального программирования специальной ФС-технологии, обеспечивающей поддержку жизненного цикла ЧМС, специфицируемых функциональными сетями. Структура системного обеспечения ФС-технологии изображена на рис.6, а представление этого обеспечения в ЭВМ - на рис.?.

Банк примитивных функций

Машина функциональных сетей

Машина функционального программирования

Банк функциональных сетей

Банк определений функций

Рис. 6. Структура системного обеспечения ФС-технологии.

Функциональные сети

функциональные программы

Машинные кода

Процессор ЭВМ

Рис. 7. Представление системного обеспечения ФС-технологии в ЭВМ.

ЗАКЛШЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертации опубликованы в следующих работах:

1. Бокова В.Е., Зуеб А.Л., Иовдрин 1KB., Цатуран Г.к., Юрченко В.В. Интерактивная моделирущая система. Препринт. М.: ВНШСИ. 1988.

2. Болатнш С.И., Геловани В.А., Ррченко В.В. Структура и функции системы интерактивного моделирования. - В кн.: Элементы человеко-машинной системы моделирования процессов глобального развития. - М.: ВНИИСИ, 1983.

3. Бритков В.Б., Геловани В.А., Щненко В.В. Система интерактивного моделирования процессов социально-экономического развития. Тезисы докладов 2-й Всесоюзной конференции по проблемам управления развитием систем (КУРС - 2), Таллин, 26-28 апреля 1982. - M., 1982.

4. Валиев И.К'., Кругляков C.B., Юрченно В.В. Адаптируемаяси-стема функционального программирования. В кн.: Системное моделирование и методы информатики. - м.: ВНШСИ, 1986.

Б. Валиев U.K., Кругляков C.B., йрченко В.В. Рекурсивная схема программ как средство сборочного программирования. ШЮОВШЖА-87. Тезисы докладов 2-й Всесоюзной конференции по актуальным проблемам информатики и вычислительной техники, Ереван, 20-22 окт. 1987 г. Ереван: АН АССР, 1937.

6. Валиев U.K., Кругляков C.B., Юрченка B.B. Функциональная сеть как основа среды программирования. Тезисы докладов Всесоюзной конференции "Метода трансляции и конструирования программ", 23-25 ноября 1988 г., г. Новосибирск, часть I, под ред. А.П.Ершова. Новосибирск: ВЦ СО АН СССР,

1988.

7. Валиев U.K., Кругляков C.B., Юрченко B.B. Функциональной программировать Новое в жизни, науке, технике. Серия "Математика-кибернетика? N 12, М.: Знание, 1989, с. 3-45.

8. Геловани В.А., Голубков В.В.", Юрченко В.В. Моделирование глобальных процессовв. Система интерактивного моделирования. Препринт. М.: ВНИИСИ, 1985.

9. Геловани В. А., Киселев А.Г., Сеглин A.A., Юрченко В.В. Интерактивная система построения моделей и алгоритмов их фушсционирования. Тезисы Всесоюзной конференции "Теория, методология и практика системных исследований -М. : BHlillCll, 1984.

10. Геловани В.А., Юрченко В.В. Компьютерное моделирование. Математическое моделирование. Ннв. 1989. T.I, N I, с.3-12.

11. Геловани В.A., Vpiewio B.B. Проблемы компьютерного моделирования. М.: МШШПУ, 1990 , 238 с.

12. ЗуОрев А.Г., Киселев А.Г., Юрченко В.В. Иерархия и рекурсия в функциональных сетях. В кн.: Методы информатики в системном моделировании. - М.: ВНИИСИ, 1988.

13. Зуев А.Л., Круг.кяков C.B., Ноздрин D.B., Сеглин A.A., Скороходов А.П., Юрченко В.В. Человеко-машинная система моделирования СЕТЬ. В кн.: Системное моделирование и метода информатики. - М. : ВНИИСИ. 1986.

14. Киселев А.Г., Сеглин A.A., Юрченко В.В. Автоматизация построения описания моделей в системе интерактивного моделирования - СИМ. В кн.: Процессы глобального развития. - М.: ВНШСИ. 1984.

15. Киселев А.Г., Юрченко В.В. оптимизация функциональных программ. - В кн.: Глобальное моделирование и информационные

системы. - М.: ВНИИСИ, 1989.

16. Сеглш Л.А., l/рченко В.В. Информационная система подмоде-

лей. В кн. Человеко-машинная система моделирования процессов глобального развития. - Ы.: ВНИИСИ, 1982.

17. Юрчешо В.В. Проблемы математического обеспечения имитационного моделирования. - Системные исследования. Методологические проблемы. Ежегодник 1983. - М.: Наука, 1983.

18. Dpченко В.В. Алгоритмизация функционирования моделей с переменной структурой. - В кн.: Элементы человеко-машинной системы моделирования процессов глобального развития. - М.: ВНИИСИ, 1983.

19. Срченко В.В. функциональный подход к автоматизации построения интерактивных систем. В кн.: Программно-математические методы информатики в системном моделировании. М.: ВНИИСИ, 1987.

20. Юрченко В.В. Процедурный и функциональный подход к описанию диалоговых систем. - В кн. Глобальное моделирование и информационные системы. - М.: ВНИИСИ, 1989.

21. Brltkov V.f Gelovanl V., Yvrchenko V. An Interactive Modelling System for Analysis oi Alternative Decisions. -Decision Support Systems. Issues and Challendge, IIASA proceeding series, vol. 11, Pergamon Press, 1980.

22. Gelovanl V.A., Yvrchenko V.Y. System for Interactive Modeling of Soclo-Economlc Development. - Adequate Modeling of Systems. Ed. H.Wedde, Proceedings of the International Working Conf. on Model Realism, Bad Honnef, PRO, April 20 -23, 1982, Springer Verlag, Berlin, Heidelberg, 1983.

Guuto в набор 25.03.81 В печать 28.03.91

Формат -60x901/16 Печать офсетная Усл. печ.л. 2,0. Усл.кр.-отт, 2,12 Уч.-взд.л. 1,90

Тир. 100 8X3. Зах. 2188

Производственно—издательский комбинат ВИНИТИ 140010, Люберцы 10, Московское обл., Октябрьский проспект, 403