Содержание к диссертации
Введение
1. Проблемы взаимодействия пользователей с системами недоопределённых вычислений 13
1.1. Анализ современного состояния исследований в области представления и обработки не полностью определённых данных и знаний 13
1.2. Недоопределённые модели и метод недоопределённых вычислений 15
1.2.1. Программирование в ограничениях 15
1.2.2. Недоопределённые модели 16
1.3. Области применения метода недоопределённых вычислений 17
1.3.1. Существующие системы недоопределённых вычислений и области их применения 17
1.3.2. Взаимодействие пользователя с системой недоопределённых вычислений при решении задачи - основные этапы 23
1.3.3. Проблемы применения метода недоопределённых вычислений 26
1.4. Существующие подходы к решению поставленных проблем 28
1.4.1. Визуализация числовых данных 28
1.4.2. Графическое отображение недоопределённых моделей в современных системах недоопределённых вычислений 29
1.5. Структурное представление недоопределённых моделей в современных системах недоопределённых вычислений 32
1.6. Постановка задачи диссертационного исследования 35
Выводы ; 36
2. Методы визуализации и структурного представления недоопределённых моделей 37
2.1. Теоретические основы недоопределённых моделей и метода недоопределённых вычислений .37
2.1.1. Модель и ее недоопределённое описание 37
2.1.2. Операции над недоопределёнными значениями и функции от недоопределённых переменных 40
2.1.3. Недоопределённые расширения 41
2.1.4. Модели с недоопределёнными переменными и метод недоопределённых вычислений 43
2.2. Методы интерактивного графического представления некоторых элементов недоопределённых моделей 47
2.2.1. Требования к графическому отображению элементов недоопределённых моделей в системах недоопределённых вычислений 47
2.2.2. Метод визуализации одномерных массивов недоопределённых переменных 48
2.2.3. Метод визуализации двухмерных массивов недоопределённых переменных 54
2.2.4. Метод визуализации трёхмерных массивов недоопределённых переменных 57
2.2.5. Методы визуализации недоопределённых функций 59
2.2.6. Особенности предложенных методов 63
2.3. Структурные недоопределённые модели 63
2.3.1. Кластерные структурные модели 63
2.3.2. Пример описания недоопределённой модели в кластерном виде 66
2.3.3. Метод частичной автоматизации внесения изменений в кластерные структурные модели в процессе решения задачи 69
2.3.4. Особенности предложенного метода 70
Выводы 71
3. Алгоритмические основы визуализации недоопределённых числовых переменных и функциональных зависимостей 73
3.1. Алгоритмы визуализации элементов недоопределённой модели 73
3.1.1. Работа системы недоопределённых вычислений и её графической подсистемы в режиме диалога с пользователем 73
3.1.2. Работа графической подсистемы в режиме интерактивного отображения массива недоопределённых переменных 79
3.1.3. Работа графической подсистемы в режиме интерактивного отображения недоопределённой функции 81
3.1.4. Визуализация одномерных массивов недоопределённых переменных 83
3.1.4.1. Алгоритм построения линейной шкалы значений недоопределённых переменных 83
3.1.4.2. Алгоритм масштабирования шкалы значений элементов массива по значению элемента массива 86
3.1.5. Визуализация двухмерных массивов недоопределённых переменных 86
3.1.6. Получение графической подсистемой информации об отображаемых элементах недоопределённой модели 91
3.2. Структуры данных для визуализации элементов недоопределённых моделей 95
3.2.1. Структуры данных для представления одномерных массивов недоопределённых переменных 95
3.2.2. Структуры данных для представления двухмерных массивов недоопределённых переменных 99
3.2.3. Структуры данных для представления недоопределённых функций от одного аргумента 101
Выводы 102
4. Проектирование, программная реализация и внедрение графической подсистемы для систем недоопределённых вычислений 104
4.1. Графическая подсистема iG 104
4.1.1. Функции и архитектура графической подсистемы iG 104
4.1.2. Менеджер визуализации 107
4.1.3. Хранилище одномерных массивов 111
4.1.4. Хранилище двухмерных массивов 113
4.1.5. Блок визуализации одномерных массивов 115
4.1.6. Блок визуализации двухмерных массивов 117
4.1.7. Блок визуализации функций от одной переменной 118
4.1.8. Пользовательский интерфейс графической подсистемы 119
4.1.9. Программный интерфейс графической подсистемы iG 120
4.2. Графическая подсистема iG в составе интеллектуального решателя UniCalc 121
4.3. Примеры использования графической подсистемы iG 126
4.3.1. Нахождение глобального минимума функции от двух переменных 126
4.3.2. Использование подсистемы iG при решении недоопределённой системы ограничений 128
4.4. Сравнение графической подсистемы iG с существующими графическими средствами систем недоопределённых вычислений 130
4.5. Тестирование графической подсистемы iG 131
4.6. Внедрение и использование результатов диссертации 132
4.6.1. Области применения графической подсистемы iG 132
4.6.2. Применение графической подсистемы iG для экспериментального исследования метода Н-вычислений и тестирования вычислительного ядра решателя UniCalc 133
4.6.3. Применение графической подсистемы iG при решении задач в области экономики 135
4.6.4. Применение графической подсистемы iG для решения технических и экономических задач
при проектировании летательных аппаратов 136
4.6.5. Использование разработанных методов и алгоритмов 136
Выводы 137
Выводы 139
Литература
- Недоопределённые модели и метод недоопределённых вычислений
- Операции над недоопределёнными значениями и функции от недоопределённых переменных
- Работа системы недоопределённых вычислений и её графической подсистемы в режиме диалога с пользователем
- Функции и архитектура графической подсистемы iG
Введение к работе
Актуальность темы исследования. По мере расширения сферы использования ЭВМ и увеличения масштабов их применения возрастает актуальность проблемы взаимодействия человека с ЭВМ. Эта проблема приобретает особую важность в связи с разработкой интеллектуальных систем, осуществляющих представление и обработку не полностью определённых данных и знаний. Одним из основных направлений решения данной проблемы является наделение пользовательских интерфейсов интеллектуальными возможностями.
Диссертационная работа посвящена решению проблемы интеллектуализации пользовательских интерфейсов в контексте одного из ведущих в последние годы направлений в искусственном интеллекте (ИИ) - методов и систем программирования в ограничениях (Constraint Programming). Сегодня методы программирования в ограничениях широко применяются для решения задач проектирования, планирования, поддержки разработок пользовательских интерфейсов, в электронных таблицах и системах, подобных им, в различных задачах искусственного интеллекта, в качестве расширений универсальных языков программирования и во многих других областях. Программирование в ограничениях является по своей сути максимально декларативным, поскольку основано на описании модели задачи, а не алгоритма ее решения, благодаря чему, методы программирования в ограничениях широко используются для задач с недооп-ределёнными данными. К числу методов программирования в ограничениях, наиболее часто применяемых для решения задач с недоопределёнными данными, относятся метод недоопределённых вычислений, метод толерантного распространения ограничений, метод распространения значений и др.
Значительный вклад в исследование и решение данных проблем внесли отечественные учёные Д.А. Поспелов, Э.В. Попов, А.Н. Мелихов, Э.Х. Тыугу, Г.С. Осипов, А.С. Нариньяни, Г.В. Рыбина, А.П. Еремеев, В.Б. Тарасов, И.Б. Фоминых, А.Н. Аверкин, Н.Г. Ярушкина, В.М. Курейчик, а также целый ряд зарубежных учёных Л. Заде (L. Zadeh), Д. Дюбуа (D. Dubois), А. Прад (А. Prade), Д. Уолц (D. Waltz), А. Макверс (A. Mackworth), У. Монтанари (U. Mon-tanari), E. Фредер (E. Freuder), E. Хивонен (E. Hyvonen) и др.
Однако, при решении задач с недоопределёнными данными с помощью методов программирования в ограничениях перед пользователем встаёт ряд проблем, среди которых можно выделить следующие: недоопределённость значений переменных; наличие в модели большого числа переменных и ограничений; необходимость вносить изменения в модель в процессе решения задачи, воздействуя таким образом, на её область решения; наличие сложной внутренней структуры у моделируемых фрагментов действительности (экономика страны, региона, технический объект, календарный план проекта).
Решение этих проблем возможно путём интеллектуализации пользовательского интерфейса систем программирования в ограничениях. В контексте систем программирования в ограничениях под интеллектуализацией пользовательского интерфейса понимается создание таких средств пользовательского интерфейса, которые позволяют пользователю найти решение задачи в диалоге с системой, выполнив меньшее число шагов диалога за более короткое время:, Это предъявляет определённые требования к средствам пользовательского интерфейса систем, реализующих методы программирования в ограничениях, а именно: обеспечение визуального представления недоопределённых значений переменных модели; обеспечение такого уровня языка описания моделей, который позволял бы представлять внутреннюю структуру объектов моделирования и преодолевать сложность больших моделей посредством их- структурирования и раздельной разработки и отладки фрагментов; расширение возможностей управления процессом решения задач, включая изменение набора ограничений модели в процессе поиска решения; обеспечение графического отображения процесса решения задач и управления им.
В современных коммерческих системах программирования в ограничениях таких как, UniCalc, "Интегра", Time-Ex (Российский НИИ искусственного интеллекта), ILOG СР, ILOG OPL Development Studio (ILOG, Франция-США), Koalog Constraint Solver, Koalog Configurator (Koalog SARL, Франция), MINERVA (IF Computer Japan Ltd., Япония) и др., эти проблемы решены не полностью.
Большая практическая значимость систем программирования в ограничениях и насущная необходимость использования в них средств пользовательского интерфейса, адекватных моделируемым предметным областям и решаемым в них задачам, обуславливает актуальность данного диссертационного исследования.
Цель работы. Целью работы является исследование и разработка методов и программных средств интеллектуализации пользовательского интерфейса, повышающих степень автоматизации и расширяющих возможности взаимодей ствия пользователя с системами недоопределённых вычислений, принадлежа щими к классу систем программирования в ограничениях. v *
Для достижения указанной цели в диссертации решены следующие задачи.
Исследование методов интерактивного графического отображения заданных в недоопределённых моделях числовых переменных и функциональных зависимостей, а также методов структурного представления недоопределённых моделей, применяемых в системах недоопределённых вычислений.
Разработка методов интерактивного графического представления массивов числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.
Разработка методов структурного представления недоопределённых моделей.
Разработка методов частичной автоматизации внесения изменений в структурные недоопределённые модели в процессе решения задачи на основе их интеграции с элементами императивного управления.
Разработка алгоритмов интерактивного графического представления массивов числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.
Разработка архитектуры графической подсистемы для систем недоопределённых вычислений.
Разработка и программная реализация графической подсистемы для систем недоопределённых вычислений
Интеграция графической подсистемы в состав оболочки интеллектуального решателя UniCalc.
Использование графической подсистемы для решения задач в рамках решателя UniCalc.
Объект и предмет исследования. Объектом исследования являются системы недоопределённых вычислений. Предметом исследования являются методы интеллектуализации пользовательских интерфейсов систем недоопределённых вычислений, основанные на графическом отображении и структурном представлении недоопределённых моделей.
Методы исследования. Поставленные задачи решаются с использованием дискретной математики, математической логики, методов искусственного интеллекта (недоопределённые модели, метод недоопределённых вычислений), методов компьютерной графики, программирования в ограничениях, структурного программирования, объектно-ориентированного проектирования и программирования.
Научная новизна. В диссертации получены следующие новые результаты.
1. Предложен новый метод интерактивного графического отображения одномерных массивов недоопределённых числовых переменных.
Впервые предложены методы интерактивного графического отображения двухмерных и трёхмерных массивов недоопределённых числовых переменных.
Предложен новый метод интерактивного графического отображения функциональных зависимостей, заданных в недоопределённых моделях.
Предложен способ расширения области применения кластерного подхода для недоопределённых моделей.
Предложен новый метод частичной автоматизации внесения изменений в структурные недоопределённые модели в процессе решения задачи на основе их интеграции с элементами императивного управления.
Разработаны оригинальные алгоритмы интерактивного графического представления массивов недоопределённых числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.
Впервые разработана архитектура графической подсистемы для систем недоопределённых вычислений, выполнена её программная реализация и экспериментальное исследование.
Основные научные результаты, выносимые на защиту.
Новый метод интерактивного графического отображения одномерных массивов недоопределённых числовых переменных.
Новые методы интерактивного графического отображения двухмерных и трёхмерных массивов недоопределённых числовых переменных.
Новый метод интерактивного графического отображения функциональных зависимостей, заданных в недоопределённых моделях.
Способ расширения области применения кластерного подхода для недоопределённых моделей.
Новый метод частичной автоматизации внесения изменений в структурные недоопределённые модели в процессе решения задачи на основе их интеграции с элементами императивного управления.
Оригинальные алгоритмы интерактивного графического представления массивов недоопределённых числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.
Новая архитектура графической подсистемы для систем недоопределённых вычислений.
Программная реализация графической подсистемы для систем недоопределённых вычислений.
Практическая значимость. Практическая значимость результатов заклю чается в разработке методов интерактивного графического отображения задан ных в недоопределённых моделях массивов числовых переменных и функцио нальных зависимостей, которые могут быть использованы при разработке пользовательских интерфейсов систем недоопределённых вычислений различ ного назначения. Разработанные методы структурного представления недооп ределённых моделей и частичной автоматизации внесения изменений в струк турные недоопределенные модели в процессе вычислений применяются при создании систем недоопределённых вычислений, обеспечивающих решение за дач на недоопределённых моделях большого объёма, в ходе решения которых требуется корректировка исходной недоопределённой модели. й.
Разработанное программное обеспечение для графического отображения заданных в недоопределённых моделях массивов числовых переменных и функциональных зависимостей успешно используется в составе систем недоопределённых вычислений для решения задач из области экономики, проектирования в области авиастроения и др., что подтверждается представленным актом о внедрении, а также в учебном процессе в Московском инженерно-физическом институте.
Достоверность полученных результатов. Достоверность научных результатов подтверждена данными компьютерного моделирования, сравнением полученных результатов с результатами, приведёнными в научной литературе, а также актом о внедрении.
Реализация результатов. Разработанная графическая подсистема интегрирована в состав недоопределённого решателя UniCalc.
Результаты работы использованы в НИР, выполненных в РосНИИ искусственного интеллекта в рамках следующих проектов: международный проект «Распределённое императивное программирование в ограничениях» в сотрудничестве с Centre for Mathematics and Computer Science (CWI) (Центр исследований в информатике), финансировавшийся NWO (Нидерландская организация по научным исследованиям); проект «Разработка аппарата решения сложных вычислительных задач в условиях неточной и недоопределённой информации на основе методов программирования в ограничениях», поддержанный РФФИ (грант № 03-01-00750).
Результаты работы также применялись в рамках проектов Министерства обороны РФ по Государственному оборонному заказу 2000-2004 гг.: «Комплексные исследования по созданию интегрированной системы информационно-аналитического обеспечения военно-экономического анализа и экспертиз мероприятий строительства, развития и содержания Вооружённых сил Российской Федерации» (шифр «Интегра»); «Разработка методического аппарата военно-экономического анализа в системе бюджетного планирования Министерства обороны Российской Федерации» (шифр «Барракуда»); «Разработка научно-методических основ проведения военно-экономических исследований с использованием математических методов ситуационного анализа, оптимизации и принятия решений» (шифр «Сатисфакция»),
Результаты работы применяются при разработке следующей версии решателя UniCalc, а также ряда продуктов, создаваемых на его основе: Time-EX, система ресурсно-календарного планирования на основе недооп-ределённых моделей и развитой временной логики; "Интегра", технология электронных таблиц на основе недоопределённых вычислений; "Экономика", технология разработки недоопределённой модели макроэкономики на основе технологии "Интегра"; "Региономика", специализация технологии "Экономика" для разработки со-цио-экономических моделей регионов РФ.
Внедрение указанных результатов подтверждается соответствующим актом. Результаты работы использовались в учебном процессе в Московском инженерно-физическом институте (государственном университете).
Апробация результатов. Основные положения и результаты диссертации докладывались и обсуждались на III международной конференции «Проблемы управления и моделирования в сложных системах», (г. Самара, 2001 г.), на 9-й национальной конференции по искусственному интеллекту с международным участием - КИИ'2004 (г. Тверь, 2004 г.), на «Научных сессиях МИФИ» (г. Москва, 1999 - 2006 гг.). Доклады, представленные на «Научных сессиях МИФИ» в 2002,2004 и 2005 гг., были отмечены дипломами «Научной сессии МИФИ».
Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 12 печатных работах, в том числе: одна статья в журнале, включённом ВАК РФ в перечень ведущих рецензируемых научных журналов и изданий, одна статья на английском языке в сборнике, выпущенном в рамках международного проекта, десять докладов в сборниках трудов конференций.
Структура и объём работы. Диссертация состоит из введения, четырёх разделов, заключения, списка использованной литературы (69 наименований) и приложений. Основная часть диссертации содержит 150 страниц машинописного текста, включая 33 рисунка, 7 таблиц.
Недоопределённые модели и метод недоопределённых вычислений
Как отмечается в работе [26], одним из основных понятий в математике и связанных с ней прикладных науках является понятие модели, определяемой парой неупорядоченных множеств - множеством переменных и множеством отношений, связывающих значения этих переменных. Модель является базовым понятием для любых областей знаний, использующих аппарат математики, так как любая попытка работать в точных терминах с реальным явлением должна начинаться с описания его формальной модели. Именно модель определяет, что является объектом исследования или расчетов, и характер формального аппарата, используемого для его описания и выполнения необходимых вычислений.
Этим обстоятельством обусловлен тот факт, что создание методов и программных средств, обеспечивающих решение задач путём непосредственного взаимодействия с формальной моделью, является одним из актуальных направлений развития современных информационных технологий. Такие методы разрабатываются в рамках парадигмы программирования в ограничениях (Соп ь. straint Programming).
В рамках программирования в ограничениях задача описывается в виде набора переменных и неупорядоченного набора ограничений (отношений) над ними, то есть модели [27]. Ограничения, могут иметь вид уравнений, неравенств, логических выражений, табличных зависимостей и т. п.
Пусть модель включает в себя набор ограничений R = {Ri, R2, ..., RJ над переменными Xi, Х2, ..., хп с областями значений соответственно Ai, А2, ..., А„. Задача состоит в том, чтобы найти наборы значений (аь а2, ..., ап), а{ є А,, i=l,2,..., п, одновременно удовлетворяющих всем ограничениям из множества R. Задача, поставленная таким образом, называется задачей удовлетворения ограничений (Constraint Satisfaction Problem). В такой постановке задачи удовле творения ограничений и задачи на Н-моделях имеют много общего, однако решаются они разными способами [28].
Одним из наиболее развитых и эффективных подходов в области программирования в ограничениях является метод Н-вычислений, основанный на математическом аппарате Н-моделей [2,3].
Н-модели были предложены в начале 80-х годов для представления и обработки не полностью определённых знаний. К настоящему времени на основе Н-моделей создана прикладная технология. Фактически она является единственной технологией, которая позволяет решать задачу удовлетворения ограничений в самой общей постановке. На основе Н-моделей разработан метод Н-вычислений [2, 3], предоставляющий ряд качественно новых возможностей при решении вычислительных задач, а именно: число переменных в Н-модели может быть не равно числу ограничений, в том числе и уравнений (возможны недоопределённые и переопределённые системы ограничений); Н-модель определяет не отдельные решения, а пространство всех решений, удовлетворяющих её ограничениям; переменные Н-модели не делятся на входные и выходные, поскольку в Н-модели все они взаимозависимы; переменные в одной Н-модели могут иметь разные типы - например, целые и вещественные, а также логические; наряду с уравнениями и неравенствами любого типа могут использоваться логические выражения и табличные зависимости, задающие дополнительные отношения между переменными Н-модели; любые переменные, коэффициенты, константы, показатели в ограничениях Н-модели могут быть заданы неточно - в виде интервалов или списков значений; не требуется задания начального приближения к решению; могут отсутствовать стандартные методы решения.
Следует отметить, что существующие в настоящее время приложения метода Н-вычислений могут работать только с Н-моделями, содержащими алгебраические ограничения. Н-модели могут включать в себя вещественные и целочисленные переменные, которые могут принимать значения в виде числовых интервалов, а также недоопределённые логические переменные. Вычисления на таких Н-моделях реализованы с использованием операций интервальной алгебры [29].
Метод Н-вычислений был реализован в ряде приложений и с успехом применяется для решения задач в таких областях, как экономика и финансы [23, 24, 30, 31, 32, 33, 34, 35, 36], инженерные расчеты [37], календарное планирование [20,25,38], вычислительная математика, САПР [39], экология [37].
На рис. 1.1 представлены некоторые системы программирования в ограничениях, решающие задачи с недоопределёнными данными, в том числе ряд систем Н-вычислений, которые применяются в упомянутых выше областях.
Интеллектуальный решатель вычислительных задач UniCalc (РосНИИ искусственного интеллекта) [19, 40], является универсальной системой, которая может применяться для решения широкого круга задач в различных предметных областях. UniCalc предназначен для решения систем алгебраических уравнений и неравенств, возможно с неточными и интервальными данными.
Операции над недоопределёнными значениями и функции от недоопределённых переменных
В работе [2] вводятся операции над Н-значениями и функции от Н-переменных. Рассмотрим алгебру Q = (A, F) на классе объектов А, замкнутом относительно множества F унарных, бинарных и т. д. операций. Алгебре Q сопоставляется недоопред ел енная алгебра Q (она называется недоопределённым расширением или Н-расширением алгебры Q). Классом объектов Q является А, операции алгебры Q (их совокупность обозначается F) получаются расширением операций множества F на класс А по следующей формуле: m f( a,, a2, ..., am) = {a = f(b)b х щ). (2.1) i=l
Очевидно, что расширенные операции замкнуты на А и сохраняют коммутативность и ассоциативность в тех случаях, когда эти свойства имели место у исходных операций. Однако, как показано в [2], в Q сохраняются не все свойства операций алгебры Q. Причина нарушения некоторых свойств операций, возникающего при переходе от алгебры Q к её Н-расширению Q, лежит в принципиальном различии интерпретации понятия значения в Q и Q.
Как отмечается в работе [2], свойства операций и в том, и в другом случае определяются тем, что они служат для спецификации функций: для алгебры Q -от переменных с областью значений А, для Q - от Н-переменных с областью значений А. При этом значение обычной переменной может быть либо равно денотату, либо полностью неопределено. А для Н-переменной х утверждение х= а имеет смысл «точное значение (денотат), представляемое переменной х, принадлежит значению а». Таким образом, из равенства текущих значений двух Н-переменных следует не равенство денотатов этих переменных, а лишь равенство недоопределённости описаний этих денотатов. На уровне алгебры нет возможности различать равенство денотатов, описываемых одним и тем же Н-значением, от равенства недоопределённости этих описаний. Чтобы отразить это различие в работе [2] вводятся функции от Н-переменных.
Рассмотрим произвольную алгебру Q = (A, F) и множество переменных X = {хі, Х2, ..., хп}, принимающих значения из А. Проводится Н-расширение алгебры Q и каждой Xj из X сопоставляется Н-переменная Xj с областью значений А. При этом результат применения всякой m-местной операции f из F к значениям переменных хц, Х;г,..., Xjm при Хц = aj, j = 1, 2,..., m, определяется как результат операции f( ai, аг,..., am), вычисляемой по формуле (2.1).
Как показывает проведённое в работе [2] исследование свойств функций от Н-переменных, результаты любых исчислений n-значных функций могут быть перенесены на Н-расширения этих функций, в частности, результаты стандартных исчислений высказываний и предикатов могут быть перенесены на соответствующие Н-расширения. Таким образом, для реализации недоопределённо-го логического вывода и вычислений (т. е. вывода и вычислений, оперирующих с функциями от Н-переменных) возможно прямое использование аппарата вывода и вычислений, оперирующего с исходными функциями, служащими для интерпретации какой-либо модели.
В работе [69] введено понятие недоопределенного расширения (Н-расширения) произвольного универсального множества. Н-расширением произвольного универсального множества А называется любая конечная система его подмножеств, замкнутая относительно операции пересечения и содержащая весь универсум и пустое множество. В случае бесконечного множества А в качестве универсума рассматривается некоторое его конечное подмножество А0сА.
Для одного и того же множества А можно построить несколько Н расширений. В статье [57] описаны некоторые виды Н-расширений, которые используются в программных технологиях, реализующих аппарат представления недоопределённостей. Рассмотрим кратко эти Н-расширения.
Наиболее простым является Н-расширение, в котором каждый его элемент представлен точным значением ( А = ASmgIe): Asingle={{a}aeA}u{0}u{A}. Данное Н-расширение добавляет к множеству А два специальных значения: не определено (А) и противоречие (0).
Перечислимое Н-расширение представляется множеством всех подмножеств: AEnum = 2А. Данное Н-расширение можно применять лишь к конечным множествам.
В случае, когда А является решеткой (множеством с определенными на нем ассоциативными и коммутативными операциями, подчиняющимися законам поглощения и идемпотентности), можно задать такие виды Н-расширений А, как интервалы и мулътиинтервалы [57].
Интервальное Н-расширение: AImerval = {[aLo, aUp] aLo, aUp є A }. Здесь aLo обозначает нижнюю, a aUp — верхнюю границу интервала. Пустое множество (0) представляется любым интервалом [aLo, aUp], где aLo aUp. Мультиинтервалъное Н-расширение: AMuitimtervai = ( а J а = u аь ak є A І І}
Пример. Пусть область значений переменной х - это множество целочисленных значений, а её текущее значение равно множеству {3, -2, 7, 8, 9, 4}. В таблице 2.1 показано его недоопределённое представление в различных Н-расширениях множества целых чисел.
Работа системы недоопределённых вычислений и её графической подсистемы в режиме диалога с пользователем
Разработанные алгоритмы визуализации одномерных и двухмерных массивов Н-переменных и недоопределённых функций от одного аргумента, заданных в Н-моделях, учитывают то обстоятельство, что работа системы Н-вычислений и, в частности, её графической подсистемы, происходит в режиме
Большинство современных систем Н-вычислений допускают одновременное хранение в своей памяти нескольких Н-моделей. Н-модель может быть за гружена в память системы с диска или создана заново в системе. При этом пользователь в каждый момент времени может работать только с одной из Н-моделей, находящихся в памяти системы. Н-модель, с которой пользователь работает в данный момент, называется активной.
Таким образом, пользователь в процессе работы с системой выполняет следующие действия: создание или загрузка в память системы Н-модели, при этом вновь созданная или загруженная Н-модель становится активной; выбор активной Н-модели из числа Н-моделей, находящихся в памяти системы; работа с активной Н-моделью.
Как видно из схемы, представленной на рис. 3.1, пользователь имеет возможность в любой момент завершить работу с системой Н-вычислений. При этом блок «Завершение работы» предусматривает сохранение, по указанию пользователя, изменённых данных, находящихся в памяти системы.
На рис. 3.2 представлена схема работы пользователя с активной Н-моделью. Как видно из схемы, эта работа может осуществляться как с использованием графической подсистемы, так и с использованием других компонентов системы Н-вычислений. Работа с активной Н-моделью может включать следующие действия.
1. Редактирование Н-модели, предусматривающее изменение её ограничений и начальных приближений значений переменных, которое может выполняться в виде редактирования текста на формальном языке или значений переменных, представленных в табличной форме.
2. Анализ результатов вычислений на Н-модели, представленных в табличной или текстовой форме.
3. Редактирование Н-модели и анализ результатов вычислений с использованием графической подсистемы.
4. Выполнение вычислений на Н-модели. Вычисления проводятся в вычислительном ядре системы. Результаты вычислений передаются графической подсистеме. Графическая подсистема извлекает из полученных результатов информацию об одномерных и двухмерных массивах Н-переменных, существующих в данной Н-модели, и преобразует её в своё внутреннее представление. 5. Сохранение изменений, внесённых пользователем в Н-модель, и полученного решения. Выполняется оболочкой системы по команде пользователя.
Порядок выполнения указанных действий пользователь может определять произвольно.
На рис. 3.3 представлена общая схема работы пользователя с Н-моделью с использованием графической подсистемы системы Н-вычислений. Эта работа включает в себя как анализ результатов вычислений на данной Н-модели, так и её редактирование.
При визуализации массивов Н-переменных и функций графическая подсистема должна поддерживать два основных режима работы, различающихся как по содержанию информационного обмена между системой и пользователем, так и по используемым способам представления графической информации. Кроме того, различается содержание обмена информацией между графической подсистемой и решателем.
Как видно из схемы (рис. 3.3), визуализация массивов начинается с выбора отображаемого массива из числа одномерных и двухмерных массивов Н-переменных, определённых в данной Н-модели. После этого графическая подсистема переходит в режим интерактивной визуализации выбранного одномерного или двухмерного массива. Более подробно работа подсистемы в этом режиме будет рассмотрена ниже.
Функции и архитектура графической подсистемы iG
С использованием описанных выше методов и алгоритмов в диссертации была разработана графическая подсистема iG для систем Н-вычислений. Подсистема iG предназначена для визуализации одномерных и двухмерных массивов Н-переменных и недоопределённых функций от одной переменной, используемых в Н-моделях. Графическая подсистема реализует следующие основные функции: графическое отображение одномерных массивов Н-переменных; графическое отображение двухмерных массивов Н-переменных; обеспечение возможности введения и изменения дополнительных ограничений на значения Н-переменных-элементов массивов путём взаимодействия с их графическим отображением; обеспечение возможности сравнения значений элементов одномерных массивов, полученных в результате выполнения последовательности шагов вычисления Н-модели; графическое отображение функций с недоопределёнными значениями от одной переменной; обеспечение возможности введения и изменения дополнительных ограничений на значения отображаемой функции путём взаимодействия с её графическим отображением; обеспечение возможности сравнения значений функции, полученных в результате выполнения последовательности шагов вычисления Н-модели.
Нарис. 4.1 представлена структура графической подсистемы iG.
Подсистема включает в себя три основные части: ядро визуализации, программный интерфейс и пользовательский интерфейс.
Основной частью графической подсистемы является ядро визуализации, оно выполняет следующие функции: обеспечивает представление в структурах данных подсистемы отображаемых элементов Н-модели; формирует графическое отображение элементов Н-модели; обрабатывает команды пользователя по управлению графическим отображением; обеспечивает представление в структурах данных подсистемы ограничений на значения переменных Н-модели, введённых пользователем.
Программный интерфейс обеспечивает взаимодействие графической подсистемы с оболочкой системы Н-вычислений и её вычислительным ядром.
Пользовательский интерфейс реализует графическое отображение элементов Н-модели, предоставляет пользователю возможности управления отображением и редактирования модели.
Описанная архитектура графической подсистемы Ю реализована на основе объектно-ориентированного подхода. В табл. 4.1. перечислены основные классы, реализующие описанные компоненты графической подсистемы, и описано их назначение. Диаграмма этих классов представлена на рис. 4.2.
Менеджер визуализации управляет работой компонентов графической подсистемы. Менеджер визуализации реализует следующие функции: извлечение из результатов вычислений, полученных от вычислительного ядра системы Н-вычислений, информации о массивах, определённых в данной
Н-модели, и представление этой информации в виде структур данных графической подсистемы; обработка выбора пользователем отображаемого массива; обработка выбора пользователем сечения двухмерного массива для отображения его как одномерного; обработка ввода пользователем параметров отображаемой недоопределён-ной функции; формирование набора ограничений, введённых в данную Н-модель с помощью графической подсистемы, по запросу, полученному через программный интерфейс; передача через программный интерфейс в вычислительное ядро системы Н-вычислений ограничения на значение Н-переменной или функции, при вводе такого ограничения.
На рис. 4.3 представлена структура менеджера визуализации. Он состоит из трёх основных блоков.
Блок управления визуализацией управляет работой других компонентов менеджера визуализации и графической подсистемы в целом. Он получает через программный интерфейс сообщение о том, что графической подсистеме переданы результаты очередного шага вычислений, а также эти результаты в виде набора пар, состоящих из имени Н-переменной и её Н-значения. Блок управления визуализацией передаёт полученные данные блоку преобразования результатов, который преобразует их в структуры данных графической подсистемы.
После того, как полученные результаты вычислений помещены в структуры данных графической подсистемы, блок управления визуализацией собирает в хранилищах одномерных и двухмерных массивов информацию о массивах, определённых в данной Н-модели, и, через пользовательский интерфейс менеджера визуализации, представляет список этих массивов пользователю.
Пользователь может выбрать отображаемый массив из этого списка. При этом блок управления визуализацией передаёт команду блоку визуализации одномерных или двухмерных массивов отобразить выбранный массив.
