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

•. 8 3 I

НАУЧН0-ПР0ИЗВ0ДСТВЕШ0Е ОБЪЕДИНЕНИЕ "ПЕРСЕИ'

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

Зуев Андрей Юрьевич

УДК 681.3

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

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

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

МОСКВА 1992

Работа выполнена в Научно-исследовательском центре электронной вычислительной техники (НИЦЭВТ).

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

старший научный сотрудник Попов С.В.

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

Щукин Б.Н.

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

Дегтярев А.И.

Ведущее предприятие: Институт прикладной математики РАН,

г.Москва.

Защита состоится "_" _199_г. в_часов

на заседании ученого совета Д 115.01.01 Научно-исследовательского центра электронной вычислительной техники по адресу: Москва, 113525, НИЦЭВТ.

С диссертацией мокно ознакомиться в библиотеке НИЦЭВТ. Автореферат разослан "_" _ 199_г.

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

Специализированного совета НИЦЭВТ д.т.н., про^ссор

С,

Е.С.Кузин

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

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

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

диалог ?". В то'кэ время, они не гарантируют оптимальности этого диалога с точки зрения первого направления, оставляя открытым вопрос "каким получится диалог ?". Таким образом, эти два направления практически не- имеют точек соприкосновения, и. поэтому, основной вопрос исследования диалогового интерфейса -"как реализовать оптимальный диалог ?" - остается открытым.

В то ш время, нукно отметить, что попытки в какой-то степени улучшить (или хотя бы учесть) качество диалога в процессе разработки формальных моделей предпринимались. Введем такую характеристику модели кок "показатель оптимальности" который равен числу принципов оптимальности диалога,.' учтенных при проектировании формальной модели. Отметим, что в подавляющем большинстве случаев понятие оптимальности (или качестве) диалога вообще не рассматривается [2,17,24,26,39,46,47], т.е. показатель к Для таких моделей равен нулю. В некоторых работах [14,16,34] предложены рекомендации по формализации одного какого-то параметра оптимальности (К=1). В работе [20] предложен набор Формальных характеристик качества диалогового интерфейса (&=3). К сожалению, этот набор является узкоспециализированным и не может претендовать на какую-то степень общности.

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

Целью настоящей, работы является создание формальной модели диалога, с показателем оптимальности к=8-

Основными задачами работы являются:

1. Выбор системы критериев оптимальности диалога (на основе анализа современных подходов к оптимизации диалогового интерфейса) и их формализация:

2. Выбор формального аппарата описания модели ДС (на основе сравнительного анализа наиболее распространенных средств спецификации диалога).

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

а. создание формальной модели диалога "общего вида";

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

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

4. Доказательство оптимальности полученной модели.

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

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

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

- разработана норжиъная модель диалога как реализация идеи

"локальной связности", примененной к автоматной кодеж;

- доказана корректность определения нормальной модели ДС, а такие ряд утверждений относительно свойств этой модели, гарантирующих оптимальность проектируемого диалога;

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

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

Практическая ценность рнбет,: определяется следующими положениями: ' •

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

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

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

- создан редактор щюграш для инструментальной: система ро-езнии интеллектуальных. задач;

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

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

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

Публикации. Результаты диссертационной работы изложены в 6-ти печатных работах.

СОДЙРХИИЗ РАБОТЫ

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

В главе I (часть. I) представлен сравнительный анализ методов формального описания диалоговых систем. Наличие формального аппарата описания диалогового взаимодействия является необходима,1 условием разработки ДО, т.к. успех з создании конкретной ДО во многом определяется удачшгл выбором адекватной модели. В части I предлагается сравнительный анализ наиболее распространенных формальных моделей диалога, а том числе - графовых моделей, диаграмм пароходов, сетей Петря, аксиоматических методов, граммз-тияа дамаядашс лзшсов, модели интерактивных событий и автоматных моделей. Цоль шализа - выбор на основе опредолозто'Л системы критериев 1 Формальной модели, наиболее соответствуадей поставленной шше задаче формализация психологических принципов оптимизации

диалога.

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

1) полнота;

2) ясность;

3) гибкость;

4) выполнимость;

5) возможность декомпозиции;

6) фиксирование предыстории диалога.

ОСНОВНЫЕ ВЫВОДЫ СРАВНИТЕЛЬНОГО АНАЛИЗА:

1. Для описания параллельных и асинхронных диалоговых процессов в большей степени подходят СЕТИ. ПЕТРИ или АКСИОМАТИЧЕСКИЕ МЕТОДЫ.

2. АКСИОМАТИЧЕСКИЕ МЕТОДЫ' и ГРАММАТИКА КОМАНДНЫХ ЯЗЫКОВ обладают наиболее мощной выразительной способностью и позволяют детально описывать проектируемую систему с различных точек зрения. Одновременно с этим (а лучше сказать, по этой причине) упомянутые модели чрезвычайно сложны для понимания и пороадают существенно более громоздкие описания, чем остальные модели.

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

• 4. Практически во всех моделях (за исключением автоматной) отсутствуют удобные и естественные средства фиксирования предыстории диалогового взаимодействия.

5. Модели, характеризуюпщеся ясностью и доступностью концепций, а также их адекватностью основным компонентам диалога (ГРАФОВЫЕ МОДЕЛИ, ДИАГРАММЫ ПЕРЕХОДОВ, СЕТИ ПЕТРИ (отчасти), МОДЕЛЬ ИНТЕРАКТИВНЫХ СОБЫТИИ) - эквивалентны классу АВТОМАТНЫХ МОДЕЛЕЙ.

И, как следствие этих утверждений, можно сделать следующий

основной вывод:

6. (ОСНОВНОЙ) В случае моделирования синхронных диалоговых систем наиболее адекватным формальным аппаратом (с точки зрения предложенных критериев) представляются АВТОМАТНЫЕ МОДЕЛИ.'

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

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

Работы в этой области можно условно разделить на три группы.

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

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

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

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

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

машинного интерфейса.

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

1. Гибкость.

а. Универсальность.

б. Индивидуализация.

2. Управляемость.

3. Легкость (простота) ведения диалога.

4. Ясность.

5. Контроль времени реакции системы.

• 6. Учет ограничений кратковременной памяти человека.

В Главе 2 неформально изложены основные идеи диссертационной работы.

Глава 3 посвящена формализации принципов оптимальности диалога. Такая формализация необходима для установления соответствия между свойствами модели диалога (являющейся строго

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

Первому соответствует набор неформальных критериев оптимальности диалога.

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

К третьему уровню абстракции относится собственно формальная автоматная модель диалога.

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

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

СТРУКТУРА:

Н=<НЮ,Н1,>> НБ={в*,3,Х,У,М}, НЬ={Р,0.т} Н=<в*,Б,Х,У,М,?,<1,т>,

Здесь:

1) н1 и нв - наборы элементов модели, описывающих соответственно ее логику и данные;

2) Б - множество состояний диалога, Бен0; в*-специальное "стоп"-состояние;

3) X -алфавит сообщений пользователя, Х€НС;

4) У - алфавит реакций ДО, У€НВ;

5) м - память диалога, мен0; Легкость (возможность исправить ошибку), Управляелостъ (возможность исправить ошибку), Проблемная отатлальностъ (фиксирование предыстории).

6) Р - семейство функций переходов, (угеЕ) | Гибкость (индивидуализация).

7) а - семейство функций реакций системы, (УабО) а:Б*х-*У; | Гибкость (индивидуализация).

8) т:Б*Х-*М - отображение, изменяющее память модели. Легкость (возможность исправить ошибку), Управляелостъ (возможность исправить ошибку), Проблемная сттыальность (фиксирование предыстории).

' УСЛОВИЯ:

1) Н^Чш0, .

| Гибкость (универсальность).

2) УееБ ЭРВ(В«, где Рв1 в2- путь (последовательность перехо-

дов) из состояния в1 в состояние Bg, И |РВ в*| < const. Управляелость (возможность прекратить диалог), Ясность (аналогичность действий в аналогичных условиях).

3) VB^BgCsaiP^^jmeoHP-tP^^...-..^^^}. п~1.

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

4) 3q*eQ - "объясняющее отображение": Vb' es зу €У -справочная информация, ассоциированная с в' и q*(e' ,х*)=у , где х*- запрос на выдачу справки в состоянии & .

Ясность (предоставление необходимых объяснений), Легкость (удобная диагностика ошибок), Контроль врелени реакции систехы.

<

5) ЗХ*сх - набор стандартных входов (команд пользователя) 3Y*cy,s*cs - набор соответственно стандартных реакций системы и стандартных состояний диалога. Тогда: Vxex*, Vees, Vf€P, VqeQ: f(e,x )=в €S, q(s,x )=y €Y .

Ясность (однородность структуры диалога, аналогичность

действий системы в аналогичных-ситуациях). Легкость (удобная диагностика ошибок).

6) s= и s,, vs. 3!s4S. и справедливо утверждение: 1=1 1 1 1 х

(s/ffij, f(B,x)=B'i, B'i€S1) > B'jSB^

__р

Причем это условие справедливо и для 81,1=Т7Е: и т.д.)

Ясность (однородность структуры диалога, аналогичность действий системы в аналогичных ситуациях)

7) Пусть у*су - совокупность справочных сообщений ДС. Тогда

У*= и у£, причем множество (у*.....У*} - частично упорядочено.

1=1

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

8) Пусть А:3-«£И - отображение, которое ставит в соответствие кавдому состоянию диалога натуральное число, равное количеству альтернатив в данном состоянии. Пусть п„е(и - число, ограничивающее количество альтернатив в состоянии.

Тогда Ув€Б А(в)<п*. | Учет ограничений ¡срсшюврелетой памяти человека.

. В главе 4 вводится понятие норжалъной ловёли АО, в основу которой положена следующая модельIдиалога общего вида.

Прежде чем говорить собственно о модели, рассмотрим схему, функционирующую по принципу обратной связи (назовем ее ¿-автоматом), которая достаточно полно и адекватно отражает структуру и функционирование синхронной диалоговой системы (см. рис.1). В этой схеме автомат Ав описывает структуру ДО, а структурный автомат Ак (являющийся простым объединение*; автоматов Кура) - ее память, механизм фиксирования предастории диалога:

- 15 -

и У

1 т

Аы

I

V

рис.1

Выход т автомата А^ является точным "слепком" текущего состояния памяти ДО. Оно изменяется на'каждом такте работы схемы под воздействием входа и, и затем используется на следу идем такте. Переход из одного состояния диалога в другое (из одного состояния автомата А0 в другое) производится в результате анализа состояния памяти (у) и воздействия пользователя (х). Кроме перехода в новое состояние диалога, реакция ДС заключается в выдаче пользователю некоторых сообщений (у) и изменении текущего состояния памяти (и).

Одной из причин явного выделения памяти и структурной части ДО является • необходимость фиксирования предыстории диалога, протоколов диалогового взаимодействия в системах ■ автоматизированного поиска с целью последущего анализа траектории решения. Это необходимо, поскольку поиск решения в таютх системах (например, построение доказательства теоремы, или поиск "счастливой" комбинации для игры в "15" или кубика Рубика) не является линейным, последовательным процессом. Как правило, он прздполага-. ет отказ от некоторых путей, возврат на несколько шагов назод, чтобы попробовать другую возможность, а если и она не подойдет, то, мозют быть, возврат еще дальше и т.д. И в конце концов, когда решение. все-таки получено, определить окончательную траекторию, сравнить ее с другими аозно только с. помощью протокола. Предлозонный способ организации па:отги диалога позволяет более естественно и удобно (например, по сравнению с МП-автоматая!

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

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

Входной алфавит модели формируется из независимого входного алфавита пользователя (X) и множества допустимых состояний памяти (V). Выходной алфавит - из независимого выходного алфавита ДО (У) и множества команд изменения памяти (и) (см. рис.1).

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

I * 1'ГП'1 * М "* I' ■листани0 экР0118 и т-п* Отметим, что

каждое такое изменение в принципе можно описать как переход в новое состояние, но в этом случае модель становится существенно более громоздкой и сложной для понимания. (Так в примере с редактором число состояний может возрасти как минимум в 1920=80*24 раз, где 80 - число позиций курсора в строке, 24 - число строк в окне ■редактора). Поэтому в предлагаемой модели понятие СОСТОЯНИЕ представлено двумя составляющими - состоянием автомата Ам, характеризующим текущее положение в структуре диалога, и совокупностью элементов структурной памяти, описывающих параметры этого текущего состояния.

ПАМЯТЬ модели представлена двумя компонентами: элементарной

и структурной. Такая организация преследует цель более гибкого и адекватного описания процессов фиксирования предыстории диалога, а тага® характеристик его текущего состояния.

Назначение элементарной памяти - описание отдельных атрибутов, свойств, признаков состояний модели (как текущих, так и прошедшее). Она представляет собой множество всевозможных состояний автомата Ам.

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

Пусть, например, А, в, о, X), Е, Р,' с - множества состояний

"ячеек" памяти модели (множества состояний автоматов Мура, соств-

»

влякщих структурный автомат Ам). Тогда элементарная память модели представляет собой декартово произведение: ы<т>= А*В«...«с. А один из вариантов структурной памяти формируется следующим образом:

Элементы структурной ы00=А, М01=В, М0?=С, М0Э=Б, М0,=Е,

памяти 0-го уровня:

00 ' И01 * м02~и* "03* 04" Ы05=Р- «06=°

Элементы структурной ы., 0=м00,,м01 "М02 • Щ 1 =моэы12=м01 'ч0')'и05, памяти 1-го уровня: „ » ж„

13 04 05 Об

Элементы структурной ^^М^-М^, М21=М11 »М1Э, М22=М12"Ы13 памяти 2-го уровня:

Тогда структурная память (в данном случае - 3-х уровневая)

м""= м00*и01»м12»м20"Н21*М22 мокет быть проиллюстрирована графом:

А ,В С Б Е Рч0

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

операции образования слова из букв алфавита " брать не

конкатенацию, а декартово произведение, то элементами 1-го уровня

являются некоторые слова в алфавите ы^, образованном элементами

1-1-го уровня. А структурной памятью является некоторое слово в ■ к

алфавите им., представлящем собой объединение элементов всех 1=0Х

уровней.

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

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

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

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

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

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

хоть и является субъективной величиной, но, как правило, не превышает 8. При N>8 эффективность такой деятельности резко падает и при N>20 практически становится равной нулю. Именно это св<?йство человеческого мышления, как представляется, лежит в основе идеи локальной связности. Более того, оно Может дать не только качественную, но и количественную информацию для развития этой идеи, поскольку число N напрямую связано с ограничениями на количество элементов в участках локальной связности.

Заметим, что в нашем случае в каждом о-подмножестве также может быть введено отношение эквивалентности. По тому, насколько глубоко может быть продолжен этот процесс, определяется принадлежность ДО к подклассу нормальных.

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

• Разбиение модели ДО осуществляется с помощью операции декомпозиции, результатом которой являются две модели; основу множества состояний одной из них составляет некоторый класс эквивалентности (о-подмножество), множество состояний другой является его дополнением до множества состояний исходной модели.

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

I. Замкнутая модель специального вида, множество состояний которой состоит из двух элементов: инициального и "стоп"-состоя-

ний, называется нормальной.

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

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

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

Введенные операции позволяют описать еще одно свойство .нормальной ДС: если в результате полной декомпозиции замкнутой модели получились модели, имеющие специальный вид (см.1-ое определение нормальной модели, п.1), то исходная модель является нормальной. Доказательство этого утверждения приведено в §1 главы 5.

Важность доказанного факта в его содержательной интерпретации: любая нормальная модель ДС может быть разбита с помощью операции полной декомпозиции на конечное число "кирпичиков" - так называемых "элементарных" нормальных моделей; и наоборот - из набора таких "кирпичиков" с помощью определенной

заранее операции интеграции (обратной операции декомпозиции) можно "собирать" различные (в зависимости от порядка сборки) большие ДС, которые заведомо будут нормальными, т.е. обладать "хорошими" свойствами. Это' имеет большое значение в плане 1)легкости реализации инструментальных средств моделирования нормальных ДС; 2)характеристики простоты и однородности структуры нормальной ДС, а также ее гибкости как основных показателей оптимальности диалоговых систем.

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

• Доказательство теоремы о корректности операции полной декомпозиции проводится по следующей схеме:

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

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

3. Вводится понятие правильного множества состояний модели ДО как множества, не допускающего ситуации "цепочка".

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

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

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

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

Оце одно важное свойство нормальной модели связано с понятием уровня состояния модели. Состоянием О-го уровня считается инициальное состояние модели. Состояниями 1+1-го уровня - те, в которые можно попасть из состояний 1-го уровня за один такт работы модели. Очевидно, что в общем случае результат определенной таким образом процедуры нумерации состояний неоднозначен.

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

Итак, в главах 4-5 была введена нормальная модель диалога. Напомним, что цель настоящей работы - создание оптимальной модели

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

В результате анализа, проведенного в главе 6, установлено:

1) Структура нормальной модели практически полностью идентична структуре оптимальной модели, определенной в главе 3;

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

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

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

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

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

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

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

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

Основу описания "данных" составляют таблицы state (описание состояний) и memory (описание памяти) (таблицу I и Z).

stats

id umory prompt TTOLP error eso (logic/dialog)

ident menu menu ident menu ident ¡r.enu ident return bogic:ident

Таблица I.

MEMORY

ID ■ value/structure

ohoice 0

test llll

menu MEMORY:ohoioe z MEMORY:test

testl "задача I"

testk "задача k"

Таблица 2.

В пашем примере множество состояний.модели состоит из двух элементов: ident (ввод идентификатора задачи) и menu (мани). Кортах: строки таблицы state имеет вид: <id, ишону, prompt, help, error, gso(loqic/dialoq) >. Здесь id - идентификатор состояния. Наличие элемента memory (являющегося идентификатором строки таблицы memory) говорит о том, что данноэ:состояние является макросостоя-ниэм. prohpt является ссылкой на строку таблицы 'prompt, содержащей текст (и способ вывода на 'экран) цриляаиавдого сообщения. help и error - идентификаторы строк таблиц пеьр и error,' гдв' хранятся текста, выдаваемые при запроса справки или ошибочном

веодэ в данном состоянии диалога; езо описывает способ передачи 1 , управления при стандартном ввода — eso (выход). return в данном

случае означает возврат к вызывающей подмодели, a logic .-ident - передачу управления таблице logic:ident описания "логики" состояния '. ident при выходе из юна. в таблице msiory содержатся конкретные значения элементов структурной памяти 0-го уровня (ohoioe - О, test - teotl ' - "задача I"), либо описание структура элементов более высокого уровня (menu - choice *

test).

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

Пове'доше ДС в состоят® ident описывает таблица LOGIC :i<Ient (таблица 3).

LOGIC-.ident

S.COHD К. СОТО X.COHD F.ACT И. ACT Y.AOT LOGIC/DIALOG

' _ _ testi _ testi testi LOQIO:roenu

- — test2 - test2 test2 LOGIC:menu

- - testk teetk teetli LOGIC:menu

Таблица 3.

Согласно втому списанию, если команда пользователя удовлетворяет условию test! (сшисенному в таблице X.CGHD - таблице 4), то происходит преобразование памяти ДС по алгоритму testi (зафякси-ровашому в таблице м.аст - таблице 5), пользователю выдается сообщение testi (описанное в таблице у.act - таблице 6) и проис-

г

ходит пороход в новое состояние "menu".

X. COITO

J 115 input condition

testi X = ШЖЖУ: testi

téstk У = UHIORY:testk

1 enter X = ENTER

I up X = UP

| dovm x = doot

Таблица 4.

m.ACT

ID memory aotion

testi testk up •down MEMORY:menu.test = MEMORY:testi MEMORY:menu.teBt = MEMORY:testk MEMORY:menu.choice = (MEMORY:menu.choice + 4) % 4 MEMORY:menu.ohoioe = (MEMORY:menu.ohoioe + 1) % 4

Таблица 5.

Y.ACT

ID output aotion program text

testi testk edit model debug <program 1> <program 1 > <program 2> <program 2> <program 2> "Выбрана задача " MEMORY:testi "Выбрана задача " memory:testk "Переходим к редакттгаванию задачи " MEMORY:menu.test "Переходим к моделированию задачи " MEMORY:menu.test "Переходим к отладке задачи" MEMORY:menu.teet

Таблица 6.

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

• В состоянии "menu".(как видно из таблицы LOGICsmenu - шабли-

t.

цы 7) происходит проверка условий на макросостояние menu, записанных в M.COND (таблица в), и в зависимости от результата происходит передача управления подмоделям edit, model, debug, либо обработка стандартного запроса ESC.

LOGIC:menu

S.COND M.COND X.COND P.ACT M.ACT Y.AOT LOGIC/DIALOG

ohoicel _ enter _ edit DIALOG:edit

ohoioe2 - enter - - model DIALOG:model

ohoioe3 - enter - - debug DIALOG .-debug

ohoioe4 - jnter - - - ESC

- - up - up - LOGIC:menu

— — down — down — LOGIC:menu

m.cond

ID memory oondition

ohoicet MEMORY:menu.oho ioe = 0

ohoice2 MEMORY:menu.chpioe = 1

ohoios3 MEMORY:menu.ohoioe = 2

ohoice4 MEMORY:menu.oho ioe = 3

Таблица 8.

Структура таблиц s.cotcd (грабмща 9), m.cond, x.cond, описывающих условия, достаточно прозрачна. В таблицах у.act, неер, error, prompt (соответственно таблицы 6, 10, II, IS) вторая компонента кортежа представляет имя функции, реализующей определенный способ вывода на экран текста, описанного 3-ей компонентой. В таблице p.act (таблиид 13) содержатся имена процедур, выполняющих саше произвольные действия. Таким образом, модель может описывать только некоторую внешнюю управляющую структуру, внутренние блоки которой, представленные такими процедурами, могут быть сами

по себе сколь угодно слопшш программами.

1 1

s.cond

ID STATE M.COND

ohoicel menu ohoioel

ohoioe2 menu ohoioe2

ohoice3 menu ohoioe3

ohoioe4 menu choioe4

Таблица 9.

HELP

id help program text

ident menu <progrqm 3> <program 4> "Необходимо ввести идентификатор задачи в формате ss...s - не более 8-ми смв." "Выберите одну из возможностей с помощью клэеиш t и 4, и нажмите enter"

ERROR

ID help) program text

ident <program 5> "He найдена задача с указанным именем"

Таблица II. '

PROMPT

ID prompt program. text

ident menu <program 6> <program 7> "Введите идентификатор задачи" "Выберите одну из возможностей: 1-редактирование 2-моделирование ч 3-отладка 4-выход"

Таблица 12.

Р.АСТ

ID functional action program

<id> <program>

Таблица 13.

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

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

2. Разработана норлалъная модель диалога как реализация идеи "локальной связности", примененной к автоматной модели.

3. Доказана корректность определения нормальной модели ДС.

4. Доказано утверждение о единственности ■ монотонного пути для любых двух состояний нормальной модели ДС.

5. Предложена система 1фитериев оптимальности диалогового ин-

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

6. Доказана оптимальность нормальной модели диалога."

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

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

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

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

1. Зуев А.Ю., Попов C.B. Продукционная система с управлением. Материалы семинара "Развитие интеллектуальных возможностей современных и перспективных ЭВМ", ВДНТП, M., 1988, с.28-36.

2. Зуев А.Ю., Орлов В.А., Попов C.B. Инструментальная система для САПР ВС. Тезисы доклада на 8-ой Всесоюзной конференции по теоретической кибернетике, Горький, 1988, с.35.

3. Зуев А.Ю., Попов C.B. Система продукций с управляемыми стратегиями поиска решения. Кибернетика, Киев, Наукова думка, М, 1989, с.97-101.

4. Зуев А.Ю., Мирошников С.А., Попов C.B. Продукционная система решения прикладных задач. Тезисы доклада ка отраслевой научно-технической конференции "Актуальные проблемы развития вычисли-

. тельной техники", Москва, 1938, с.75-76.

5. Зуев A.D., Мирошников С.А., Попов C.B. Система логико-функционального программирования в задачах САПР ВС. Сборшж "Автоматизация проектирования в электронике", Киев, 1989, с.51-60.

6. Зуев А.Ю. Оптимизация диалогового интерфейса. Сборник "Вопросы радиоэлектроники", 1991, сер.ЭВТ, й5, с.23-32.

7. Зуев А.Ю., Попов C.B. Инструментальная система решения интеллектуальных задач, решение как поиск в пространства состояний. Материалы семинара "Прикладные интеллекту алыщ; системы", ЦРДЗ, M., 1992, с.74-851

Инв. Р 39-256, от 02.12.92. Доп. ,размн. 80 экз. по з/н Щ8 / 573 от 02.12.92.