Введение к работе
Актуальность теыы. В настоящее время диалоговый интерфейс присутствует в большинстве прикладных программных систем, особенно относящихся к искусственному интеллекту (например, в экспертных системах). И если несколько лет назад участник диалога с компьютером был, как правило, программистом (системным или іфикладннм), то сегодня круг пользователей ЭВМ резко расширился, и прежде всего за счет людей, слабо знакомых с программированием. Поэтому требования к качеству диалоговой поддержки программных систем существенно возросли.
Основной "программный" вопрос разработки средств поддержки диалогового взаимодействия - "как реализовать приемлемый диалог ?". Нетрудно заметить, что на самом деле в нем содержатся два вопроса: "каким должен быть диалог ?" и "как реализовать такой диалог ?". Поиски ответов привели к появлению различных направлений, подходов к исследованию диалога: На наш взгляд, среди них можно выделить два основных. Первый - "психолого-эмпирический" - связан с многочисленными психологическими исследованиями и экспериментами, призванными ответить на вопрос: "каким должен быть диалог ?". Основным недостатком этого подхода является его неформальность. Исследования, достаточно полно отвечающие на вопрос "каким должен быть диалог ?", описывающие принципы "оптимальности" диалогового интерфейса, оставляют открытой проблему реализации средств поддержки такого диалога. Второй, так называемый "модельный подход", имеет целью разработку формальных средств описания диалогового взаимодействия. Формальные модели позволяют создать практически любую диалоговую систому (ДС), т.е. исчерпывающе отвечают на вопрос "как реализовать
_ 4 -
диалог ?". В токе время, они не гарантируют оптимальности этого диалога с точки зрения первого направления, оставляя открытым вопрос "каким получится диалог ?". Таким образом, эти два направления практически не- имеют точек соприкосновения, и. поэтому, основной вопрос исследования диалогового интерфейса -"как реализовать оптимальный диалог ?" - остается открытым.
В то ш время, нукно отметить, что попытки в какой-то степени улучшить (или хотя бы учесть) качество диалога в процессе разработки формальных моделей предпринимались. Введем такую характеристику модели кок "показатель оптимальности" ft, который равен числу принципов оптимальности диалога,.' учтенных при проектировании формальной модели. Отметим, что в подавляющем большинстве случаев понятие оптимальности (или качестве) диалога вообще не рассматривается [2,17,24,26,39,46,47], т.е. показатель ft для таких моделей равен нулю. В некоторых работах [14,16,34] предложены рекомендации по формализации одного какого-то параметра оптимальности (ft=I). В работе [20] предложен набор Формальных характеристик качества диалогового интерфейса (k=3)..К сохсалеиию, этот набор является узкоспециализированным и не может претендовать на какую-то степень общности.
Для реализации "приемлемого .диалога" необходимо создать формальную модель ДС с достаточно высоким ' показателем оптимальности ft диалога, причем выбор критериев оптимальности должен быть обоснован.
Целью настоящей, работы является создание формальной модели диалога, с показателем оптимальности ft=8.
Основными задачами работы являются:
-
Выбор системы критериев оптимальности диалога (на основе анализа современных подходов к оптимизации диалогового интерфейса) и их формализация;
-
Выбор формального аппарата описания модели ДС (на основе сравнительного анализа наиболее распространенных средств спецификации диалога).
3. Созданий формальной модели ДС, позволяющей конструировать диалоговые системы, обладающие свойствами оптимальности;
а. создание формальной модели диалога "общего вида"; б» выделение из всего множества ДС, описываемых данной моделью, некоторого подмножества, элементы которого обладают требуемыми свойствами оптимальности;
. в.. трансформация исходной модели за счет привнесения в нее формализованных элементов оптимальности с целью сужения класса описываемых ею ДС до указанного подмножества.
4. Доказательство оптимальности полученной модели.
Методы исследований. Для решения поставленной задачи использовались методы теории множеств, теории автоматов, теории графов, методы системного программирования.
Научная новизна работы представлена следующими результатами:
разработана автоматная модель диалога, организованная по принципу обратной' связи,' о разделенными памятью и структурной частью;
разработана нормальная модель диалога как реализация идеи
- 6.-
"локальной связности", примененной к автоматной модели;
доказана корректность определения нормальной модели ДС, а также ряд утверждений относительно свойств етой модели, гарантирующих оптимальность проектируемого диалога;
предложена система критериев оптимальности диалогового интерфейса, полученная в результате анализа современных: подходов к оптимизации диалога человек-ЭВМ; на ее основе резработанн формальные требования к оптимальной модели диалоговой система;
на основе модифицированного подхода "множеств ссшіок" разработан язык описания нормальной подели ДС, позволящий учитывать элементы оптимальности проектируемых диалоговых систем.
Практическая ценность работа: определяется следующими положе
ниями: '
- разработанная формальная модель диалога может слушть тео
ретической основой создания ерздетв сшщфнквции диалоговых сис
тем;
- разработана инструментальная система проектирования оптимальных диалоговых систем;
создана системе диалоговой поддерпси процесса синтезе комбинационных czbk ке Функциональных елемзнтов;
создан редактор программ для инструментальной' система решении кнтеллоктуалышж задач;
предложенные критерии оптимальности диалогового интерфейсе г є тшсісо принципи их практической роалиаацші могут быть использована при создании диалоговш:- систем иоддерккь поиска рэЕб-
Апробации рсбош. Основина результаты раоотк докладывались
на семинаре "Развитие интеллектуальных возможностей совремвшшх и перспективных ЭВМ" (Москва, 1988), 8-ой Всесоюзной конференции по теоретической кибернетике (Горький, 1988), отраслевой научно-технической конференции "Актуальные проблемы развития вычислительной техники", семинаре "Методы логической обработки информации" (Киев. 1983).
Публикации. Результаты диссертационной работы изложены в 6-ти печатных работах.
Во введения обоснована актуальность создания средств формализации диалоговых систем, содержащих принципы оптимальности диалогового интерфейса, сформулированы цели и задачи исследований.
В главе I (часть. I) представлен сравнительный анализ методов формального описания диалоговых систем. Наличие формального аппарата описания диалогового взаимодействия является необходимым условием разработки ДО, т.к. успех з создании конкретной ДО во многом определяется удачным выбором адекватной моделі. В части I предлагается сравнительный анализ наиболее распространенных формальних моделей диалога, а том числе - графовых моделей, диаграмм пароходов, сетей Петря, аксиоматических методов, граммз-тики командных лзыков, модели интерактивных событий и автоматных моделей. Прлъ шализа - выбор на основе определенной системы критериев формальной моделі, наиболее соответ'ствуадей поставленное шшв задаче формализации психологических принципов оптимизации
диалога.
В качестве системы критериев сравнительного анализа взят следующий набор характеристик:
-
полнота;
-
ясность;
-
гибкость;
-
выполнимость;
-
возможность декомпозиции;
-
фиксирование предыстории диалога.
-
Для описания параллельных и асинхронных диалоговых процессов в большей степени подходят СЕТИ.ПЕТРИ или АКСИОМАТИЧЕСКИЕ МЕТОДЫ.
-
АКСИОМАТИЧЕСКИЕ МЕТОДЫ' и ГРАММАТИКА КОМАНДНЫХ ЯЗЫКОВ обладают наиболее мощной выразительной способностью и позволяют детально описывать проектируемую систему с различных точек зрения. Одновременно с этим (а лучше сказать, по этой причине) упомянутые модели чрезвычайно сложны для понимания и поровдают существеїшр более громоздкие описания, чем остальные модели.
-
Практически все модели достаточно легко могут быть расширены с целью включения механизма декомпозиции.
4. Практически во всех моделях (за исключением автоматной) отсутствуют удобные и естественные средства фиксирования предыстории диалогового взаимодействия.
5. Модели, характеризующиеся ясностью и доступностью концепций, а также их адекватностью основным компонентам диалога (ГРАФОВЫЕ МОДЕЛИ, ДИАГРАММЫ ПЕРЕХОДОВ. СЕТИ ПЕТРИ (отчасти). МОДЕЛЬ ИНТЕРАКТИВНЫХ СОБЫТИИ) - эквивалентны классу АВТОМАТНЫХ МОДЕЛЕЙ.
И, как следствие этих утверждений, можно сделать следующий
основной вывод:
6. (ОСНОВНОЙ) В случве моделирования синхронных диалоговых систем наиболее адекватным формальным аппаратом (с точки зрения предложенных критериев) представляются АВТОМАТНЫЕ МОДЕЛИ.'
Результаты сравнительного анализа обусловили тот факт, что именно теория абстрактных автоматов была положена в основу создания описанных ниже формальной модели диалога общего вида, а также полученной из нее в результате определенной трансформации так называемой "нормальной"'модели.
В части 2 главы I рассмотрены подходы к решению проблемы выбора системы критериев оптимальности диалога. Именно качество, удобство, оптилалъностъ средств взаимодействия с системой во многом определяет отношение *к ней пользователя. Поэтому нисколько не преуменьшая роли функционального наполнения, можно утверждать, что путь к оптимальности системы лежит через оптимизацию диалогового интерфейса.
Работы в этой области можно условно разделить на три группы.
В первой рассматриваются некоторые общие вопросы создания оптимального интерфейса (реализация понятия удобства, раздельное проектирование интерактивных систем, способы классификации диалоговых систем).
Работы второй группы посвящены изучению отдельных характеристик оптимальности диалога. Среди них - время реакции системы, характеристики памяти человека, модель пользователя, категории пользователей,' индивидуализация диалога.
Результаты этих исследований полезны в плане выбора отдельных элементов оптимальности диалога, но не дают целостной системы таких критериев.
Третьей группе принадлежат исследования подходов к систематизации критериев оптимальности диалога, попытки их формализации.
В большинстве работ наборы критериев только определяются, вопрос их формализации не рассматривается. В тех же работах, где приводятся примеры формализации, выбранные системы критериев слишком узкоспециализированы, ориентированы на строго определенный тип взаимодействия и не отражают всех аспектов человеко-машинного интерфейса.
Таким образом, проблема формализации принципов оптимальности диалога, понимаемая как создание инструментальных средств проектирования ДО, изначально содержащих в себе принципы оптимальности диалогового интерфейса - остается открытой. Данная диссертационная работа представляет собой попытку решения этой проблемы. За основу системы критериев оптимальности диалога в работе принят следующий комплекс параметров:
1. Гибкость.
а. Универсальность.
б. Индивидуализация.
-
Управляемость.
-
Легкость (простота) ведения диалога.
-
Ясность.
-
Контроль времени реакции системы.
6. Учет ограничений кратковременной памяти человека.
В Главе 2 неформально изложены основные идеи диссертационной работы.
Глава 3 посвящена формализации принципов оптимальности диалога. Такая формализация необходима для установления соответствия между свойствами модели диалога (являющейся строго
- II -
формальный объектом) и сформулированными на содержательном уровне критериями оптимальности. Тем самым позволительно утверждать, что созданная формальная модель диалога дает возможность конструировать оптимальные (с точки зрения предложенной' системы критериев) диалоговые системы. Для решения этой проблемы в главе 3 введены три уровня абстракции.
Первому соответствует набор неформальных критериев оптимальности диалога.
Второй уровень абстракции содержит "обобщенное" описание модели диалоговой системы, содержащее все основные компоненты будущей автоматной модели (возможно, недостаточно конкретизированные), а также формальную интерпретацию свойств оптимальности.
К третьему уровню абстракции относится собственно формальная автоматная модель диалога.
С точки зрения введенных уровней абстракции, глава 3 посвящена описанию модели диалога 2-ого уровня абстракции, а также проблемной конкретизации критериев оптимальности и созданию их формальных эквивалентов.'
В результате сформулированы критерии оптимальности модели диалога. Суммируя полученный результат, определим структуру такой модели и набор ограничений на ее элементы. Курсивом (Легкость) отмечены параметры оптимальности, далее в скобках (.Легкость (возможность исправить ошибку) ) - конкретные стороны этого параметра, отраженные в данном элементе модели или условии.
- 12.-
H=
1) HL и HD - наборы элементов модели, описывавдшс
соответственно ее логику и данные;
-
Б - множество состояний диалога, seHD; в*-специальное "стоп"-состояние;
-
X -алфавит сообщений пользователя, XHD;
-
Y - алфавит реакций ДО, YHD;
5) м - память диалога, менв;
Легкость (возможность исправить ошибку),
Управляелостъ (возможность исправить ошибку),
Проблемная отатлалъностъ (фиксирование предыстории).
В) - семейство функций переходов, (VfeF) t:SxX-»S; I Гибкость (индивидуализация).
7) Q - семейство функций реакций системы, (VqeQ) q:S*X-*Y;
I Гибкость (индивидуализация).
8) m:S*X-*M - отображение, изменящее память модели.
Легкость (возможность исправить ошибку),
УпраЗляелость (возможность исправить ошибку),
Проблемная сттилальность (фиксирование предыстории).
' УСЛОВИЯ:
1) &AiD, HLnHD=fl.
| Гибкость (универсальность).
2) Vees 3?B в*. где Рв1 2- путь (последовательность перехо-
- ІЗ -
дов) из состояния в1 в состояние в2, и |РВ в*| < oonst. Управляелостъ (возможность прекратить диалог), Ясность (аналогичность действий в аналогичных условиях).
3) VB1>B2S3!PBi>B2Jni60 3P={PBl>B2....,P^fB2}, п~1.
Управляелостъ (возможность быстро и легко переместиться в любое состояние, легко исправить допущенную ошибку);
Легкость (возможность легко исправить ошибку);
Ясность (аналогичность действий в аналогичных условиях, простота структуры диалога).
4) 3q*eQ - "объясняющее отображение": Vb' eS ЗУ Y -
справочная информация, ассоциированная с в' и q (в' ,х )=у , где
х*- запрос на выдачу справки в состоянии в* .
Ясность (предоставление необходимых объяснений), Легкость (удобная диагностика ошибок), Контроль врелени реакции систели.
5) ЗХ*сх - набор стандартных входов (команд пользователя)
3Y*cY,s*cs - набор соответственно стандартных реакций системы и
стандартных состояний диалога. Тогда: Vxex*. Vees, VfP, VqcQ:
f(s,x*)=B*es1! q(s,x*)=y*Y*.
Ясность (однородность структуры диалога, аналогичность
действий системы в аналогичных-ситуациях). Легкость (удобная диагностика ошибок).
6) s= и s,, vs. 3!s4S. и справедливо утверждение: i=i 1 1 х х
(s/ffij, 1 (.в,ъ)=б'±, B'iS1) > B'jSB^
.^ p Причем это условие справедливо и для slfi=T7K: (s^ и s.^ и т.д.)
Ясность (однородность структуры диалога, аналогичность действий системы в аналогичных ситуациях)
7) Пусть Y*cy - совокупность справочных сообщений ДС. Тогда
* п Y
и Yj, причем множество (Y1 YR} - частично упорядочено.
Легкость (возмошость быстро получить необходимую информации).
8) Пусть A:S-»in - отображение, которое ставит в соответствие кавдому состоянию диалога натуральное число, равное количеству альтернатив в данном состояшш. Пусть п„е(и - число, ограничивающее количество альтернатив в состоянии.
Тогда VeS А(в)<п*. | Учет ограничений іцшловреле}<лой палжи человека.
. В главе 4 вводится понятие нормальной ловёли АО, в основу которой положена следующая модель\диалога общего вида.
Прежде чем говорить собственно о модели, рассмотрим схему, функционирующую по принципу обратной связи (назовем ее d-автома-том), которая достаточно полно и адекватно отражает структуру и функционирование синхронной диалоговой системы (см. рисі). В этой схеме автомат AD описывает структуру ДО, а структурный автомат Ак (являющийся простий объвдинанкек автоматов Кура) - ее пимять, механизм імксированип предыстории диалога:
рисі
Выход т автомата Ау является точнш "слепком" текущего состояния памяти ДО. Оно изменяется на'каждом такта работы схемы под воздействием входа и, и затем используется на следу идем такте. Переход из одного состояния диалога в другое (из одного состояния автомата AD в другое) производится в результате анализа состояния памяти (v) и воздействия пользователя (х). Кроме перехода в новое состояние диалога, реакция ДО заключается в выдаче пользователю некоторых сообщений (у) и изменении текущего состояния памяти (и).
Одной из причин явного выделения памяти и структурной части ДО является необходимость фиксирования предыстории диалога, протоколов диалогового взаимодействия в системах автоматизированного поиска с целью последующего анализа траектории решения. Это необходимо, поскольку поиск решения в таїсих системах (например, построение доказательства теоремы, или поиск "счастливой" комбинации для игры в "15" или кубика Рубина) не является линейным, последовательным процессом. Как правило, он предполагает отказ от некоторых путей, возврат на несколько шагов назад, чтобы попробовать другую возможность, а осли и она не подойдет, то, мозют быть, возврат еще дальше и т.д. И в конце концов, когда решение. все-таки получено, определить окончательную траекторию, сравнить ее с другими иозно только с поглсщьв протокола. Предлояонный способ организации памяти диалога позволяет более естественно и удобно (например, по сравнению с УП-автоі!ата:.йї
-. 16 -
или механизмом маркировки сетей Петри) описывать иерархическую структуру памяти ДО и динамику обмена информацией. Кроме того, это дает возможность расширить понятие состояния диалога.
Описанная вше схема положена в основу автоматной модели диалога, состоящей из: входного и выходного алфавитов, множества состояний, памяти, функций: переходов, выходов и преобразования памяти.
Входной алфавит модели формируется из независимого входного алфавита пользователя (X) и множества допустимых состояний памяти (V). Выходной алфавит - из независимого выходного алфавита ДО (Y) и множества команд изменения памяти (и) (см. рис.1).
В реальном диалоге человек-ЭВМ нередко возникает ситуация, когда можно считать, что действия пользователя приводят не к переходу к новому состоянию диалога, а к изменению, некоторых параметров, характеристик того же самого состояния. Например, перемещение курсора в окне редактора при нажатии пользователем клавиш:
I * 1'1 * 1'1 * Ы * I' ^01811119 экршш и т.п. Отметим, что каждое такое изменение в принципе можно описать как переход в новое состояние, но в этом случае модель становится существенно более громоздкой и сложной для понимания. (Так в примере с редактором число состояний может возрасти как минимум в 1920=80*24 раз, где 80 - число позиций курсора в строке, 24 - число строк в окне редактора). Поэтому в предлагаемой модели понятие СОСТОЯНИЕ представлено двумя составляющими - состоянием автомата Аы, характеризующим текущее положение в структуре диалога, и совокупностью элементов структурной памяти, описывающих параметры этого текущего состояния.
ПАМЯТЬ модели представлена двумя компонентами: элелентарной
и структурной. Такая организация преследует цель более гибкого и адекватного описания процессов фиксирования предыстории диалога, а также характеристик его текущего состояния.
Назначение элементарной памяти - описание отдельных атрибутов, свойств, признаков состояний модели (как текущих, так и прошедшее). Она представляет собой множество всевозмокных состояний автомата Ам.
Структурная память группирует параметры (представленные элементарной памятью) в классы и тем самым позволяет учитывать влияние на ход диалога уже не просто совокупности в большинстве своем разнородных элементов памяти, а структурированных объектов, более полно характеризующих содержательные свойства диалога. С этой целью структурная память определяет механизм формирования на основе элементарной памяти некоторой многоуровневой иерархической структуры.
Пусть, например, А, в, о, D, Е, F,' G - множества состояний "ячеек" памяти модели (множества состояний автоматов Мура, соств-влякщих структурный автомат Ау). Тогда элементарная память модели представляет собой декартово произведение: 1^"~ A«B«...«G. А один из вариантов структурной памяти формируется следующим образом:
Элементы структурной ы00=А, М01=В, М02=С, М03=Б, М04=Е,
памяти 0-го уровня: „ ,, „ _„
м05 ' 06
Элементы структурной м1о=моо"м01"м02 м11=М0Э' ы12=м01"М03"М05. памяти 1-го уровня: „ _„ » „„
Ы1Э"М04 М05 МОб
Элементы структурной М20=м10»м11( м21=м11»м13, м22=м12»м13 памяти 2-го уровня:
Тогда структурная память (в данном случае - 3-х уровневая)
м""= м00«и01»ы1-»м20'<н21>'М22 мокет быть проиллюстрирована гра-
фом:
1о
S
"02
»06
"03
"04
"05
из й
Пользуясь терминологией формальных языков, если в качестве операции образования слова из букв алфавита " брать не конкатенацию, а декартово произведение, то элементами і-го уровня являются некоторые слова в алфавите Mi_1, образованном элементами
і-1-го уровня. А структурной памятью является некоторое слово в
к алфавите им., представлящем собой объединение элементов всох 1=01
уровней.
Если множество состояний и память представляют структуры "данных" модели диалога, то ее "логика" описывается с помощью функций (входов, выходов и'преобразования памяти). Они определяют, в какое состояние перейдет ДС в зависимости от текущего'значения памяти (v) и команда пользователя (х) (см. рис.1), как при этом будет изменена память (и) и какое сообщение будет передано пользователю (у).
Описанная выше автоматная модель диалога является моделью общего вида. Она не дает гарантии оптимальности создаваемых на ее основе диалоговых систем.
Первым шагом к созданию интеллектуальной модели, контролиру-вдэй степень оптимальности проэктируеьюго диалога, является выделение в классе ДС, определяемом моделью общего вида, подкласса.
обладащего рядом "хороших" свойств и переход к "нормальной" модели, описывающей этот подкласс.
Характерным свойством нормальных диалоговых систем, предо--пределявдим наличие у них элементов оптимальности, является регулярность структуры диалога. На множестве состояний модели диалога можно ввести отношение эквивалентности, разбивающее это множество на клабсы (называемые о-подмнокествами). Все состояния, пргшадле-яащие одному классу эквивалентности (кроме одного или двух выделенных), характеризуются отсутствием связей с элементами других классов (связь понимается как возмокность перехода из одного состояния в другое). Выделенные состояния связывают классы мевду собой.
Это свойство является проявлением более общей идеи - локальной связности.-Согласно этой идее, пространство, описывающее какую-либо деятельность, процесс, разбивается на участки "локальной связности", элементы которых "хорошо" связаны мевду собой и "плохо" - с элементами других участков. Другими проявлениями этой идеи можно считать решение задачи путем разбиения ее на подзадачи, принятие заключения на основе анализе локальной области при обработке изображений и т.п. Причини такого разбиения связаны с ограничениями на какие-либо ресурсы или на характеристики процессов мышления и запоминания человека. Так, ограниченность кратковременной памяти (о которой упогашалось раньше), выявленная в результате многочисленных психологических исследований и экспериментов, не позволяет человеку эффективно оперировать одновременно более чем и элементами (имеется- ввиду бистрий сравнительный анализ, выбор из альтернатив, выявление взаимных связей и т.д.). Причем, N
хоть и является субъективной величиной, но, как правило, не превышает 8. При N>8 эффективность такой деятельности резко падает и при и>20 практически становится равной нулю. Именно это свойство человеческого мышления, как представляется, лежит в основе идеи локальной связности. Более того, оно может дать не только качественную, но и количественную информацию для развития этой идеи, поскольку число N напрямую связано с ограничениями на количество элементов в участках локальной связности.
Заметим, что в нашем случае в каждом о-подмножестве также может быть введено отношение эквивалентности. По тому, насколько глубоко может быть продолжен этот процесс, определяется принадлежность ДС к подклассу нормальных.
Определение нормальной модели ДС тесно связано с понятием залкнутой лодёли. Замкнутая модель вводится операцией замыкания как расширение автоматной модели диалога общего вида за счет введения нового т.наз. "стоп"-состояния, описывающего ситуацию, когда ДС находится в "неактивном" состоянии.
Разбиение модели ДС осуществляется с помощью операции декомпозиции, результатом которой являются две модели; основу множества состояний одной из них составляет некоторый класс эквивалентности (о-подмножество), множество состояний другой является его дополнением до множества состояний исходной модели.
операция декомпозиции с замыканием, примененная к замкнутой модели, разбивает ее на две модели, также являющиеся замкнутыми. Не останавливаясь пока на вопросе о корректности операции декомпозиции с замыкап'.ем, определим (неформально) понятие нормальной модели диалоговой системы:
I. Замкнутая модель специального вида, множество состояний которой состоит из двух элементов: инициального и "стоп"-состоя-
ний, называется нормальной.
2. Любая замкнутая модель, результатом декомпозиции которой по некоторому с-подмножеству множества ее состояний являются две нормальные модели ДС, также считается нормальной.
В главе 5 рассмотрены свойства нормальной модели, обусловившие выбор ее в качестве базиса интеллектуальной модели диалога, гарантирующей оптимальность (с точки зрения предложенной выше системы критериев) создаваемых на ее основе ДС.
Выше было отмечено, что результатом декомпозиции замкнутой модели ДС являются две замкнутые модели. Если теперь в множестве состояний одной из этих моделей удастся выделить некоторое с-подмножество, то декомпозицию можно продолжить. В этом случае можно говорить о многократном применении операции декомпозиции с замыканием (многократной декомпозиции). Если в результате применения операции многократной декомпозиции получились замкнутые модели, ни в одном из множеств состояний которых не удается выделить с-подмнокества, такая операция называется полной декомпозицией, в противном случае - частичной.
Введенные операции позволяют описать еще одно свойство .нормальной ДС: если в результате полной декомпозиции замкнутой модели получились модели, имеющие специальный вид (см.1-ое определение нормальной модели, п.1), то исходная модель является нормальной. Доказательство этого утверждения приведено в 1 главы 5.
Важность доказанного факта в его содержательной интерпретации: любая нормальная модель ДС может быть разбита с помощью операции полной декомпозиции на конечное число "кирпичиков" - так называемых "элементарных" нормальных моделей; и наоборот - из набора таких "кирпичиков" с помощью опрвделешюй
заранее операции интеграции (обратной операции декомпозиции) можно "собирать" различные (в зависимости от порядка сборки) большие ДС, которые заведомо будут нормальными, т.е. обладать "хорошими" свойствами. Это' имеет большое значение в плане 1)легкости реализации инструментальных средств моделирования нормальных ДС; 2)характеристики простоты и однородности структуры нормальной ДС, а также ее гибкости как основных показателей оптимальности диалоговых систем.
До сих пор, говоря об операции полной декомпозиции, мы не задавались вопросом о корректности этой операции, о единственности результата полной декомпозиции модели ДС в зависимости от порядка выполнения операции декомпозиции с замыканием. Этот вопрос непосредственно связан с двумя проблемами: Ппроблемой единственности выделения в множестве состояний модели диалоговой системы всех с-подмножеств; 2)проблемой зависимости результата полной декомпозиции модели ДС от порядка выполнения операции декомпозиции с замыканием.
Доказательство теоремы о корректности операции полной декомпозиции проводится по следующей схеме:
1. Доказывается утверждение о частичной непересекаемости
с-подмножеств множества состояний модели ДС, в котором говорится,
что любые два с-подмножества замкнутой модели ДС находятся между
собой в одном из отношений: й,с,=, либо имеет место специальный
вырожденный случай - "цепочка".
-
Доказывается утверждение о единственности результата час-тичний декомпозиции туш всех случа. в отношений между двумя с-под-множествами одного множества состояний модели ДС.
-
Вводится понятие правильного множества состояний модели ДО как множества, не допускающего ситуации "цепочка".
-
Доказывается упрощенный вариант теоремы - о корректности операции полной декомпозиции для случая правильного множества состояний модели ДС.
-
Доказывается утверждение о возможности сведения любого множества состояний к правильному множеству.
-
Доказывается собственно основная теорема о корректности операции полной декомпозиции замкнутой модели ДС для общего случая.
Доказав факт корректности операции полной декомпозиции замкнутой модели, мы тем самым доказали корректность определения нор-лсиъной лодёли. ДС.
Біде одно важное свойство нормальной модели связано с понятием уровня состояния модели. Состоянием О-го уровня считается инициальное состояние модели. Состояниями і+1-го уровня - те, в которые можно попасть из состояний 1-го уровня за один такт работы модели. Очевидно, что в общем случае результат определенной таким образом процедуры нумерации состояний неоднозначен.
Для нормальной модели.ДС это не так. В этом случае справедливо утверждение о единственности результата операции нумерации состояний, а, значит, и о корректности понятия уровень состояния для нормальной модели ДС. Следствием этого утверждения является факт единственности монотонного (в смысле последовательности номеров состояний) пути для любых двух состояний нормальной модели ДС. Содержательный смысл этого свойства заключается в том, что для каждого состояния zl модели существует единственная траектория, переводящая модель в наперед заданное состояние s2.
Итак, в главах 4-5 была введена нормальная модель диалога. Напомним, что цель настоящей работы - создание оптимальной модели
диалога. Является ли нормальная модель оптимальной ? Прежде чем ответить на этот вопрос, вспомним, что условия оптимальности модели диалога были сформулированы на неформальном уровне в главе I,, а затем формализованы в главе 3, где определена общая структура оптимальной модели, а также ограничения на ее элементы. Поэтому для установления факта оптимальности нормальной модели диалога достаточно показать, что ее структура соответствует структуре оптимальной модели, а элементы удовлетворяют ограничениям на элементы нормальной модели.
В результате анализа, проведенного в главе 6, установлено:
1) Структура нормальной модели практически полностью идентична
структуре оптимальной модели, определенной в главе 3;
2) Элементы нормальной модели полностью удовлетворяют
ограничениям, сформулированным в главе 3 в качестве
формализованных критериев оптимальности диалога.
Поэтому можно утверждать, что нормальная модель является оптиыальной с точки зрения предложенной в главе I системы критериев.
В главе 7 рассмотрены принципы практической реализации нормальной модели диалога. В их основу положен подход "множеств ссылок", модифицированный исходя из требований описания нашей модели.
Согласно этому подходу, информация, описывающая "данные" модели и "логику" ее функционирования, организована в виде таблиц. Каждая таблица представляет некот рое множество элементов - записей этой таблицы. Каждая запись является кортежем. Элементы кортежей таблиц, описывающих "логику" модели, являются ссылками на соответствующие кортежи таблиц "данных". Иными словами, табли-
цы "логики" модели содержат информацию о том, какие действия нуж-' но совершать, когда и при каких условиях, а описания этих условий, действий,, текстов сообщений и т.п. хранятся в таблицах "данных".
Основное достоинство такой организации заключается в четком разделении. описаний "логики" и "данных" модели, что позволяет проектировать эти'компоненты независимо друг от друга. Благодаря этому появляется возможность быстрой реализации "скелета", структурной основы ДС, с целью анализа и модификации. После этого (или во время этого) производится дополнение, наращивание этой структуры конкретными данными: текстами справочной информации, конкретными условиями и т.п. Кроме того, при таком разделении одна и та же логическая компонента описания может быть реализована с различными версиями текстовых данных, что обеспечивает гибкость диалога, возможность его адаптации к различным категориям пользователей и типам решаемых задач.
Другим достоинством метода является однородность описания, поскольку все таблицы "данных" модели имеют единый формат записей: <идентификатор, информация>. Это позволяет использовать одни и те же процедуры поиска и модификации данных для всех компонент описания, что немаловажно для практической реализации.
Рассмотрим в качестве примера спецификацию модели, описывающей следующий фрагмент диалога. Пусть в определенный момент работы некоторой ДС пользователю необходимо ввести идентификатор задачи, после чего на экран выдается меню со следующими пунктами: 1-редактирование, 2-моделирование, 3-отладка, 4-выход. При выборе пункта меню управление передается соответствующей подмодели.
Основу описания "данных" составляют таблицы state (описапио состояний) и MEMORY (описание памяти) (таблицу I и 2).
т 26 -
STATS
Таблица I.
MEMORY
value/structure
ohoice test menu testl
testk
llll
MEMORY:ohoioe z MEMORY:test "задача I"
"задача к"
Таблица 2. В пашем примере множество состояний.модели состоит из двух элементов: ident (ввод идентификатора задачи) и msnu (маню). Кортах: строки таблицы state имеет вид: <п>, ишону, prompt, help, error, езо(logic/dialog) >. Здесь ID - идентификатор состояния. Наличие элемента mmory (являющегося идентификатором строки таблицы MMORY) говорит о том, что данное! состояние является макросостоя-ниэм. prohpt является ссылкой на строку таблицы prompt, содерка-цзй текст (и способ вывода на' экран) праглаиавдего сообщения.
НЕЬР И ERROR - Идентификаторы строк ТабЛИЦ HELP И ERROR,- ГДв'
хранятся тексты, выдаваемые при запросе справіси или ошибочном ВЕОде в данном состоянии диалога; езо описывает способ передачи управления при стандартном вводе— eso (выход), return в данном случае означает возврат к вызывающей подмодели, а logic:ident - передачу управления таблице logic:ident описания "логики" состояния '. ident при выходе из меню. В таблице MSiORY содержатся конкретные значения элементов структурной памяти 0-го уровіш (ohoioe - о, test - "", tes-Ы ' - "задача I"), либо описание структуры элементов более высокого уровня (menu - choice *
test).
"Логику" диалога описывает набор таблиц - для каждого состояния своя. Число этих таблиц равно числу строк в таблице state. Таблицы "логики" являются ядром описания, они содеряат ключевую' информацию, определяющую закони функционирования диалоговой' система.
Поведоіше ДС в состоянии ident описывает табліща LOGIC:ident (таблица 3),
LOGIC-.ident
Таблица 3. Согласно втому описанию, если команда пользователя удовлетворяет условию test! (описанному в таблице х.сони - таблице 4), то происходит преобразованЕО памяти ДС по алгоритму testi (зафиксированному в таблице м.аст - таблице 5), пользователю выдается сообщение testi (оішешшое в таблице у.act - таблице 6) и проас-ходит переход в новое состояний "menu".
X.COND
input condition
testl
teetk enter up
dovm
X = ШЖЖУ: testl
У = IffllORYrtestk X = ENTER X = UP X = BOOT
Таблица 4.
memory aotion
testl
testk up down
MEMORY:menu.test = MEMORY:testl
MEMORY:menu.teBt = MEMORY:testk
MEMORY:menu.choice = (MEMORY:menu.choice + 4) % 4
MEMORY:menu.ohoioe = (MEMORY:menu.ohoioe + 1) % 4
Y.ACT
Таблица 5.
Таблица 6.
В случае, если ни одно из условий на ввод пользователя не выполняется, выдается сообщение об ошибке, ссылка на которое содержится в таблице state в строке ident, и ДО остается в том кё состоянии.
В состоянии "menu".(как видно из таблицы LOGIC:menu - шабли-1<ы 7) происходит проверка условий на макросостояние menu, записанных в m.cond (таблица б), и в зависимости от результата происходит передача управления подмоделям edit, model, debug, либо обработка стандартного запроса ESC. LOGIC:menu
Таблица 7.
memory oondition
ohoicel ohoice2 ohoioe3 ohoice4
MEMORY:raenu.ohoioe = 0 MEHORY:menu.ohpioe = 1 MEMORY:menu.ohoioe = 2 MEMORY:menu.choioe = 3
Таблица 8.
Структура таблиц s.coiro {гюблихір. 9), m.cond, х.сого, описывающих условия, достаточно прозрачна. В таблицах y.ACT, неер, error, prompt (соответственно таблицы 6, 10, II, 12) вторая компонента кортежа представляет имя функции, реализующей определенный способ вывода на экран текста, описанного 3-ей компонентой. В таблице f.act (тайлиид 13) содержатся имена процедур, внполнящих саше произвольные действия. Такті образом, модель может описывать только некоторую внешнюю управляющую структуру, внутреішие блоки которой, прэдстввлошше такими процедурами, могут быть сами по себе сколь угодно слопшми программами.
і і
S.COND
Таблица 9.
HELP
Таблица 10.
- зо -
ERROR
Таблица II.
PROMPT
Таблица 12.
P. ACT
functional action program
Таблица ІЗ.
