Объектно-ориентированная среда для недоопределенных вычислений

• Автор: Ушаков, Дмитрий Михайлович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Новосибирск
• Количество страниц: 160 с. : ил.

Содержание
Введение

1 Программирование в ограничениях

1.1 Искусственный интеллект и программирование в ограничениях.

1.2 Обзор работ в области программирования в ограничениях.

1.3 Классификация и анализ различных алгоритмов удовлетворения ограничений . . .

1.3.1 Области значений переменных .

1.3.2 Виды отношений

1.3.3 Способ представления значений переменных.

1.3.4 Язык спецификации ограничений

1.3.5 Алгоритмы удовлетворения ограничений

1.4 Языки и системы программирования в ограничениях
1.4.1 Чистое программирование в ограничениях.
1.4.2 Логическое программирование в ограничениях.
1.4.3 Императивное программирование в ограничениях.
1.4.4 Активные базы данных.
2 Теория недоопределенных моделей
2.1 Задача удовлетворения ограничений в многосортных алгебраических моделях .
2.2 Недоопределенные расширения .
2.3 Денотационная семантика распространения ограничений.
2.4 Операционная семантика
2.5 Поиск точного решения задачи удовлетворения ограничений
2.6 Поиск оптимального решения.
2.6.1 Метод упорядоченной бисекиии.
2.6.2 Метод ветвей и границ
2.7 Виды недоопределенных расширений.
3 Объектноориентированная среда НеМо
3.1 Назначение комплекса.
3.2 Архитектура системы
3.2.1 Схема функционирования комплекса
3.2.2 Требования к окружению .
3.2.3 Структура комплекса НгМо.
3.3 Язык представления знаний
3.3.1 Классы
3.3.2 Отношения.
3.3.3 Модули
3.3.4 Объекты.
3.3.5 Ограничения.
3.3.6 Модели
3.4 Вычислитель
3.4.1 Вычислительная сеть.
3.4.2 Недоопределенные объекты
3.4.3 Ограничения.
3.4.4 Дескрипторы типов и отношений
3.5 Библиотеки типов данных и отношений
4 Решение задач в среде НеМо
4.1 Задачи с конечными областями значений.
4.1.1 Зебра
4.1.2 Зашифрованная арифметика.
4.1.3 Расстановка ферзей.
4.1.4 Магический квадрат.
4.1.5 Лемма Шура.
4.1.6 Размещение голубей
4.1.7 Расстановка ферзей булева версия.
4.1.8 Показатели производительности .
4.2 Численные задачи
4.2.1 Диофантовы уравнения
4.2.2 Поиск вещественных корней уравнения .
4.2.3 Нелинейная оптимизация с ограничениями
4.3 Задачи с таблицами
4.4 Задачи ресурсного планирования
4.5 Задачи САПР.
Заключение
Благодарности
Литература


Поэтому начнем классификацию алгоритмов с классификации решаемых ими задач. Каждая задача удовлетворения ограничений имеет четыре составляющих (Определение 1. Задачи с конечными областями значений переменных — традиционный объект исследований в ИИ. Для решения таких задач было предложено (и продолжает предлагаться) множество методов (Нильсон []): от перебора с возвратами до генетических алгоритмов. Задачи с такими областями — основной объект исследования в математике, где разработано огромное количество алгоритмов для их решения. Речь идет о таких популярных у программистов-теоретиков областях как множества, деревья (термы), или графы. Багаж накопленных здесь алгоритмов может успешно использоваться для решения задач удовлетворения ограничений над такими областями. Иерархическая организация гетерогенных (разнородных) областей может служить областью для задач удовлетворения ограничений. Универсальные алгоритмы для работы с такими областями, также как и кооперативные решатели таких задач с помощью разных методов, сейчас начинают занимать центральное место в области программирования в ограничениях (Caseau и Puget [], Телерман и Ушаков []). Конечно, тот или иной вид отношения определяется в первую очередь природой областей значений. Например, над числовыми областями существуют арифметические отношения типа ’’сумма двух чисел равна третьему”, над графами существует отношение изоморфности, над множествами — включения, и т. Однако, можно выделить одно универсальное свойство отношения, а именно, отношения можно разделить на экстенсиональные и интенсиональные. Речь идет о конечных отношениях, которые можно задать простым перечислением всех кортежей элементов областей, которые удовлетворяют данному отношению. Конечно, так можно задать все отношения над конечными областями. Другим, более важным примером таких отношений могут служить таблицы в реляционных базах данных. Многие свойства моделируемого предмета или явления часто задаются именно таким образом. Эти отношения играют важную роль в области САПР (систем автоматизированного проектирования) и в области ГИС (геоинформационных систем). Алгоритмы удовлетворения ограничений, поддерживающие экстенсиональные отношения, находят здесь самое широкое применение. Имеются в виду отношения, заданные параметрически. Таковыми являются почти все отношения над числовыми областями. Например, отношение ’’сумма двух чисел равна третьему” является интенсиональным. Соответственно, для их обработки требуется применять специальные методы удовлетворения ограничений. Традиционный программистский способ, связывающий с каждой переменной одно значение из се области определения, не всегда применим при решении задач удовлетворения ограничений. Рассмотрим, каким образом представляют значения переменных различные алгоритмы удовлетворения ограничений. Первые методы удовлетворения ограничений работали именно с такими значениями переменных. Б частности, в работе Тыугу [] описывается система, позволяющая решать задачи, имея только их декларативную спецификацию. Решение происходит методом распространения известных значений переменных к неизвестным. При этом, наряду с простым распространением констант в выражениях, используются специализированные методы для решения различных подклассов задач: системы линейных уравнений и др. Другой плодотворный метод, основанный на единичных значениях, был описан в работе ЛаАГаг и др. Суть метода состоит в поиске точных решений линейных подсистем задачи, после которого вычисленные значения подставляются в нелинейные части, благодаря чему степень нелинейности снижается, что позволяет еще раз применить тот же самый метод. Кроме того, единичные значения переменных используются в методах иерархического удовлетворения ограничений, предложенных Вогшг^ и др. Как отмечалось выше, качественный скачок в решении задач удовлетворения ограничений был достигнут при переходе от единичных к множественным значениям для каждой переменной. Первые работы на эту тему (МаскиогЬЬ [], Мопипап []) дали и обшее название таким алгоритмам: алгоритмы достижения локальной совместности.