автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Объектно-ориентированная среда для недоопределенных вычислений

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

УШАКОВ Дмитрий Михайлович

ОБЪЕКТНО-ОРИЕНТИРОВАННАЯ СРЕДА ДЛЯ НЕДООПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ

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

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

Новосибирск 1998

Работа выполнена в Новосибирском государственном университете.

Научный руководитель:

кандидат технических наук, старший научный сотрудник Телермап В. В.,

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

профессор Замулин А. В.,

кандидат физико-математических наук, старший научный сотрудник Шарый С. П.,

Ведущая организация: Институт математики СО РАН

Защита состоится " н* ¿¿¿/ТУ^УУШ г. в У-^Ч. З^мин. на заседании специализированного совета К0003.93.01 в Институте систем информатики Сибирского отделения РАН по адресу:

630090, Новосибирск, пр. академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ИВМиМГ СО РАН (пр. ак. Лаврентьева, 6).

Автореферат разослан "

г.

Ученый секретарь специализированного совета К0003.93.01

к. ф. -м. н.

М. А. Бульонков

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

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

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

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

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

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

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

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

• создан объектно-ориентированный язык спецификации задач удовлетворения ограничений в недоопределенных моделях; разработана архитектура программного комплекса НеМо+, предназначенного для интерпретации программ на этом языке.

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

Результаты работы докладывались на XXXIII Международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 1995), Третьей международной студенческой школе-семинаре "Новые информационные технологии" (Крым, 1995), Andrei Ershov Second International Memorial Conference "Perspectives of System Informatics" (Novosibirsk, Russia, 1996), Пятой национальной конференции с международным участием "Искусственный интеллект - 96" (Казань, 1996), XI Международном совещании по интервальной математике (Новосибирск, 1996), The 6th International Conference, EWHCI'96 (Moscow, Russia, 1996), International Conference AISMC-3 (Steyr, Austria, 1996), XII Международном совещании по интервальной матема-

тике (Красноярск. 1997), The 3rd International Conference on Principles and Practice of Constraint. Programming - CP"97 (Linz, Austria, 1997).

По теме диссертации опубликовано 12 печатных работ.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Общий объем работы - 100 страниц (включая список использованной литературы и два приложения). Работа включает 8 таблиц и 6 рисунков.

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

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

В самой обшей постановке задачу {¡доеле творения ограничении (далее ЗУО) можно определить как четверку (D, R.V.C), где D - множество об.частей, R - множество отношений различной арности над атими областями. V* - множество переменных, с каждой ил которых связана область ее возможных значений, С — множество ограничений, связывающих значения переменных из V посредством отношений из R. Решение ЗУО (]). R, V. С) — э то такое означивание неременных Г. которое сопоставляет каждой переменной значение из ее области, такое что для любого ограничения с € С выполняется соответствующее отношение над значениями связанных им переменных.

Выделение задач удовлетворения oi раниченнй в отдельный класс приносит следующие выгоды. Благодаря общему подходу к задачам такого типа были разработаны различные кооперативные методы их решения, позволяющие применять к задачам комбинации известных методов. Еще важнее здесь появление ряда уншсрсальных алгоритмов решения задач удовлетворения ограничений. Подход к спецификации задачи как задачи удовлетворения ограничений позволяет полностью избавиться от всех процедурных деталей спецификации. Специфика задач удовлетворения ограничений позволила ввести новую компоненту знаний — недоопределенностъ.

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

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

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

• области значений переменных (конечные области, числовые области, составные области, иерархии классов),

• виды отношений (экстенсиональные и интенсиональные),

• способ представления значений переменных (единичные значения, экстенсиональные и интенсиональные множественные значения),

• язык спецификации ограничений (язык атомов, язык термов, язык первого порядка),

• алгоритмы удовлетворения ограничений (точные: метод проб и ошибок, перебор с возвратами, метод Гаусса для систем линейных уравнений, симплекс-метод; приблизительные: итерационные методы решения систем уравнений и их интервальные аналоги, методы достижения локальной совместности сети ограничений; кооперативные методы решения задач).

В разделе 1.4 обсуждаются известные системы программирования в ограничениях. Выделяются четыре класса таких систем:

• "чистое" программирование в ограничениях,

• логическое программирование в ограничениях,

• императивное программирование в ограничениях,

• активные базы данных.

Кроме того, выделяется три способа реализации таких систем:

• в виде библиотеки к существующему языку программирования,

в в виде расширения существующего языка программирования,

• в виде нового языка программирования.

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

Но второй глава приводи тся теоретическое обоснование процесса решения задач удонлетворения ограничений на основе аппарата недо-определенных моделей. В разделе 2.1 вводится необходимый формализм для описания ЗУО: многосортные, алгебраические модели. Стандартным образом определяются попя ) ия многосортной сигнатуры, мо-(кли, термов, атомов и оценки переменные. Выделяется специальный класс формул: экзистенциальные конъюнкции атомов, для которых определяется понятие выполнимости о анданной модели и сиидьтьАЯ выполнимости (оценки переменных). Выделяется специальный класс простейших атомов — ограничений, которые включают в себя не более одного предикатного или функционального символа сигнатуры и связывают различные переменные. Определяется задача удовлетворения ограничений в многосортной модели как экзистенциальная конъюнкция, все атомы которой суть ограничения. Формулируется и доказывается предложение 1.1, утверждающее, что любая экзистенциальная конъюнкция может быть преобразована за конечное число шагов в эквивалентную ей задачу удовлетворения ограничений. В доказательстве предложения приводится алгоритм такого преобразования.

В разделе 2.2 вводится понятие педоопреде ленного расширения (Н-раешпрения) многосортной модели, являющееся развитием одноименного понятия, предложенного А. С. Нариньяни. Переопределенное расширение заданной многосортной модели представляет собой модель той же сигнатуры, 1» которой носитель каждого сорта (И-носитель) есть конечный набор подмножеств носителя этого сорта в исходной модели, замкнутый относительно пересечения и содержащий в себе максимальный (весь носитель) и минимальный (пустое множество) элементы. Определяется аппроксимация любого множества значений в Н-расширении как наименьший элемент Н-носителя, содержащий это множество. Операции Н-расширенной модели определяются как аппроксимации образов исходных операций на заданных множествах значений. Предикаты Н-расширепной модели (Н предикаты) определяются как отношения, выполняющиеся над множествами значений, если аппроксимация пересечения декартова произведения :>тнх множеств с предикатом в исходной модели совпадает с этим декартовым произведением. В предложении 2.2 доказывается корректность предиката равенства в Н-расширенной модели. Далее в диссертации устанавливается связь между понятием Н-предиката и классическим понятием локальной совместности множеств значений, предложенным МаскшойЬ. Для

этого понятие локальной совместности сначала обобщается на случай многосортных моделей, затем вводится понятие Н-совместности как аппроксимация понятия совместности. Лемма 2.1 показывает связь между аппроксимацией и проекциями множества. Наконец, предложение 2.3 формулирует эквивалентность понятий Н-нредиката и Н-совместности его аргументов. В качестве реального примера недо-оиределенного расширения модели рассматривается интервальное расширение множества вещественных чисел, операций и отношений над ним. В конце раздела обсуждаются свойства оценок переменных в II-расширснии модели (Н-оценок). Показывается, что множество всех Н-оценок является частично упорядоченным множеством с наибольшим элементом. Определяется операция пересечения Н-оценок и отношение принадлежности точной оценки недоопределенной оценке. Понятие Н-совместности распространяется на множество Н-оценок. Формулируется основная задача недоопределенных моделей (их декларативная семантика): найти такую наибольшую II-оценку переменных, которая Н-совместна со всеми ограничениями заданной ЗУО.

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

• содержится в исходной Н-оценке,

• является Н-совместной по отношению к фильтруемому ограничению,

• является максимальной Н-оценкой среди всех, обладающих двумя вышеперечисленными свойствами.

В предложении 2.4 доказывается корректность такого определения, т. е, существование такой Н-оценки. Лемма 2.2 устанавливает важные свойства фильтрации ограничения:

• корректность (если в исходной Н-оценке содержались какие-либо свидетели выполнимости ЗУО в заданной модели, то фильтрация любого ограничения ЗУО не теряет этих свидетелей),

• сжимаемость (результирующая Н-оценка всегда содержится в исходной),

• монотонность (фильтрация более точной Н-оценки всегда дает более точную Н-оценку),

• идемпотентность (повторное применение одной и той же фильтрации не изменяет Н-оценку).

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

В разделе 2.4 описывается операционная семантика распространения ограничений в недоопределенных моделях на основе схемы потоковых вычислений. Для формального описания этой схемы вводится понятие абстрактной машины с состояниями и правилами перехода из состояния в состояние. Состояние абстрактной машины — это некоторая Н-окенка переменных вместе с множеством активных ограничений. Такая 1 ¡-опенка рассматривается как информация о единичных (точных) значениях переменных ЗУО, т. е. информация о всех свидетелях выполнимости ЗУО в заданной модели. Переходы между состояниями выполняются фильтрациями активных ограничений. В начальном состоянии, все ограничения ЗУО являются активными, а Н-оценка -- максимально неопределенной. После фильтрации ограничения оно становится пассивным, но все ограничения, чьи переменные изменили своп 11-значения во время этой фильтрации, помешаются в множество активных ограничений. Процесс останавливается (достигается конечное состояние) когда множество активных ограничений становится пустым. Н-оценка, полученная в конечном состоянии абстрактной машины, определяет операционную семантику распространения ограничений. В предложении 2.5 устанавливаются следующие свойства такой абстрактной машины:

в завсршасмостъ (существование верхней оценки числа шагов, за

которые машина обязательно придет в конечное состояние), * корректность (все конечные состояния одинаковы, и вычисленная 11-оценка является наибольшей Н-совместной со всеми ограничениями ЗУО Н-оценкой переменных в заданном Н-расширешш модели).

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

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

В определении 2.14 вводится формальное понятие недоопределенной модели как шестерки Р = (Е, X, С, М, "М, Л4), где £ = (5, Р, Р) — многосортная сигнатура, X — ¿"-индексированное множество переменных, С — £(Х)-задача удовлетворения ограничений, М — £-модель, *М — Н-расширение М, и М. — абстрактная машина для вычисления наибольшей Н-совместной по отношению к С оценки переменных X в *М, содержащей всех свидетелей выполнимости ЗУ О С в М.

В разделе 2.5 рассматривается метод поиска точных решений ЗУО. Н-оценка переменных в заданном Н-расширении многосортной модели называется непротиворечивой, если она содержит по крайней мере одну точную оценку. Если полученная в результате распространения ограничений Н-оценка противоречива, то мы можем утверждать, что ЗУО не выполняется в рассматриваемой модели. Если финальная Н-оценка непротиворечива, то ее можно разделить ца две части и применить к каждой из них метод распространения ограничений. Для этого в определении 2.16 вводится понятие бисекции Н-оценки. Би-секция — это разделение Н-оценки на две части, каждая из которых содержится в исходной Н-оценке, не совпадает с ней и является непротиворечивой. Кроме того, любая точная оценка переменных, содержащаяся в исходной Н-оценке, содержится и в одной из результирующих Н-оценок. Оценки, для которых возможно проведение бисекции назовем делящимися. В лемме 2.3 постулируется и доказывается тот факт, что такая бисекция может проходить по Н-эначению только одной переменной. Идея метода бисекции состоит в попеременном применении распространения ограничений и бисекции Н-оценок вплоть до получения непротиворечивой и неделящейся финальной Н-оценки переменных, которую можно рассматривать как потенциальное точное решение ЗУО. Мы ставим перед собой задачу локализацию всех таких множеств потенциальных решений. Для формального описания операционной семантики этого процесса в определении 2.17 вводится новая

абстрактная машина. Состояние этой абстрактной машины — это четверка, состоящая из текущей {{-оценки переменных, множества активных ограничений, множества отложенных состояний и множества найденных "решений ". Отложенное состояние — это пара, состоящая из П-оценки переменных и множества активных ограничений. "Решение' это непротиворечивая неделящаяся Н-оценка. В начальное состоянии текущей Н-оценкой является максимально пеон ре деленная Н-оценка, а все остальные компоненты являются пустыми множествами. Конечное состояние — это состояние с противоречивой текущей Н-оценкоЙ и пустыми множествами активных ограничений и отложенных состояний. Переход из состояния в состояние выполняется по одному из четырех правил:

• фильтрация активного ограничения,

• бисекция текущей Н-оценки,

• запоминание "решения",

• откат к отложенному состоянию.

Результатом работы такой абстрактной машины является множество найденных "решений" в конечном состоянии. Важные свойства введенной выше абстрактной машины формулируются и доказываются в предложении 2.6:

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

• любой свидетель выполнимости ЗУО в заданной модели содержится в одном из найденных ''решений"'.

Часто в реальных приложениях требуется найти оптимальное по заданному критерию решение задачи удовлетворения ограничений. Задача поиска оптимального решения ЗУО обсуждается в разделе 2.6. В определении 2.18 вводится формальное понятие оптимального свидетеля выполнимости ЗУО в заданной модели с линейно упорядоченным универсумом. Первый рассматриваемый метод для поиска такого оптимального свидетеля основан на понятии упорядоченной бисекции. Бисекция П-оценки называется упорядоченной, если результирующие Н-оценки упорядочены в соответствии с линейным порядком на универсуме. Определение 2.20 вводит понятие абстрактной машины для вычисления оценки оптимального свидетеля методом упорядоченной бисекции. Эта машина является разновидностью машины описанной в предыдущем разделе, при этом множество отложенных состояний

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

Другим способом поиска оптимального решения ЗУО является метод ветвей и границ. Определение 2.21 вводит абстрактную машину для формального описания операционной семантики этого метода, а в предложении 2.8 содержится доказательство его завершаемости и корректности.

Раздел 2.7 посвящен описанию различных видов недоопределенных расширений, используемых в практических приложениях Н-моделей. Определения 2.22-2.26 вводят такие типы Н-расширений, как точное, перечислимое, интервальное, мультиинтервалъное и структурное II-расширения. В предложении 2.9 устанавливается связь между различными видами Н-расширений.

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

• научные и инженерные расчеты,

• моделирование физических, химических, социальных, экономических процессов,

• проектирование и планирование,

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

Архитектура системы НеМо-\- описывается в разделе 3.2. Комплекс НеМо+ состоит из нескольких взаимосвязанных программных компонент, среди которых можно выделить

• редактор текстов,

• компилятор модулей на языке НеМо+

• генератор вычислительной сети,

• потоковый вычислитель,

в библиотеки, содержащие код инструментальных типов данных ц отношений,

® средства просмотра текстовых файлов.

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

В разделе 3.3 описан язык представления знаний системы НеМо-\~. Ключевыми понятиями этого языка являются понятия класса, отношения, модуля, объекта, ограничения и модели.

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

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

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

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

Отношения в языке А'еЛ/о-Ь разделяются по синтаксическому признаку на функции и операции. Семантически они разделяются на инструментальные, пользовательские, и табличные.

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

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

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

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

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

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

Существуют три вида ограничений в описываемом языке представления знаний: выражения, условные ограничения, альтернативные ограничения. Выражения составляются по обычным правилам из имен объектов, констант и отношений. Условные ограничения представляют собой ограничения, срабатывающие при выполнении логического условия. Альтернативные ограничения генерируют различные альтернативы, которые проверяются с помощью процедуры бэктрекинга. Кроме

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

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

В разделе 3.4 описан вычислитель системы НеМо+. Вычислитель НеМо+ реализован с помощью библиотеки классов языка Си++ для поддержки потоковых вычислений на структурированных сетях, состоящих из объектов и ограничений. Инструментальные библиотеки наполняют вычислитель различными типами данных и отношениями. В вычислителе выделены следующие группы понятий (каждому из которых соответствует некоторый инструментальный класс):

• сетевые объекты (базовый сетевой объек т, информационный объект. функциональный, групповой обьект, модель);

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

• абстрактные ограничения (ограничение, унарное отношение, бинарное отношение, п арное отношение, операция, унарная операция, бинарная операция, тьарная операция);

в дескрипторы типов данных и отношений.

В разделе 3.5 описаны библиотеки типов данных и отношений комплекса НеМо+.

В четвертой главе рассматривается применение системы //>А/о+ для решения различных задач. В разделе 4.1 разбираются задачи с конечными областями значений. Рассмотрены спецификация и решение в среде НеМо+ таких стандартных тестовых задач, как "Зебра", зашифрованная арифметика, расстановка ферзей, магический квадрат, лемма Шура, размещение голубей.

Решение трех типов численных задач (диофантовы уравнения, по-

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

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

Раздел 4.4 посвящен разбору типовой задачи ресурсного планирования.

Наконец, в разделе 4.5 рассматривается решение задачи из области САПР.

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

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

Список использованной литературы содержит 99 наименований.

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

Приложение Б состоит из текстов моделей на языке НеМо+ для задач, которые разбираются в четвертой главе настоящей диссертации.

Заключение. Основные результаты диссертационной работы перечислены ниже.

1. Теоретические результаты.

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

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

• Рассмотрены различные модификации этого алгоритма для поиска точных и оптимальных решений задачи.

• Классифицированы различные виды недоопределейных расширений.

2. Технология программирования.

• Создан объектно-ориентированный язык спецификации задач удовлетворения ограничений в недоонределенных моделях (совместно с В. В. Телерманом, И. Е. Швецовым, В. А. Сидоровым) .

• Разработана архитектура программного комплекса НсМо+, предназначенного для интерпретации программ на этом язы-

ко (совместно с В. В. Телерманом, И. Е. Швецовым, В. Л. Сидоровым).

3. Практическая реализация.

о Реализован вычислитель для нелооирсдоленных моделей и модуль оконного интерфейса с пользователем, которые совместно с реализованным В. А. Сидоровым транслятором программ составляет объектпо-орпснтпрованную среду для не-доопределенных вычислений НеМо+, функционирующую в среде Microsoft Windows.

• Произведено наполнение комплекса НеМо+ библиотеками не-доопределенных типов данных и ограничений (часть библиотек была реализована совместно с В. А. Сидоровым и Г. Б. За-горулько).

4. Экспериментальные исследования.

е Проведена серия экспериментов, показывающая эффективность применения комплекса НеМо+ при решении задач различных классов.

Список опубликованных работ по теме диссертации.

1. Ушаков Д. М. Развитие технологии недоопределенных моделей // Материалы XXXIII Междунар. научной студснч. конф. "Студент и научно-технический прогресс": Математика. — Новосибирск: ИГУ, 1995. — С. 34- 35.

2. Ушаков Д. М. Объектно-ориентированный язык спецификации недоопредслеттттых знаний // Третья междунар. стпуденч. школа-семинар "Новые информационные технологии": Тез. докл. Крым, май 1995. — С. 135.

3. Телерман В. В., Ушаков Д. М. Недоопределенные модели: формализация подхода и перспективы развития // Проблемы представления и обработки не полностью определенных знаний / Под ред. И. Е. Швецова. Москва-Новосибирск: РосИИП ПН. 199(1

— С. 7-30.

4. Telerman V., Ushakov D. Using the Subdefiniteness in Real World Models // Human-Computer Interaction: Proc. of the 6th Internat. Conf. EWHCI'96 / Ed. by S. Overmyer, Ju. Gornostaev. — Moscow: International Centre for Scientific and Technical Information, 1996.

— P. 194-206.

5. Telerman V., Ushakov D. Data Types in Subdefinite Models // Artißcial Intelligence and Symbolic Mathematiral Computation: Proc.

/ Ed. by J. Calmet, J. A. Campbell and J. Pfalzgraf. — Berlin a.o.: Springer-Verlag, 1996. — P. 305-319. — (Lect. Notes Comput. Sci.; 1138).

6. Telerman V., Ushakov D. Subdefinite Models as a Variety of Constraint Programming // Proc. of the 8th Internal. Conf. on Tools ivith Artificial Intelligence, ICTAI'96. — IEEE Computer Society, 1996. — P. 157-163.

7. Telerman V., Sidorov V., Ushakov D. Problem Solving in the Object-Oriented Technological Environment NeMo+ // Perspectives of System Informatics: Proc. / Ed. by D. Bj0rner, M. Broy, I. V. Pot-tosin. — Berlin a.o.: Springer-Verlag, 1996. — P. 91-100. — (Lect. Notes Comput. Sci.; 1181).

8. Телерман В. В., Сидоров В. А., Ушаков Д. М. Интервальные и мультиинтервальные расширения в недоопределенных моделях // Вычислительные технологии. — 1997. — Т. 1, N 2. — С. 62-70.

9. Telerman V., Ushakov D. Levels of Parallelism in CSP with Sub-definite Objects // Proc. of the Poster Session of JFPLC'97, Sixth French Conf. on Logic and Constraint Programming. — Orleans, France, 26-28 May 1997. — (Rapport de Recherche LIFO 97-6).

10. Shvetsov I., Telerman V., Ushakov D. NeMo+: Object-Oriented Constraint Programming Environment Based on Subdefinite Models // Principles and Practice of Constraint Programming - CP97: Proc. / Ed. by G. Smolka. — Berlin a.o.: Springer-Verlag, 1997. — P. 534548. — (Lect. Notes Comput. Sci.; 1330).

11. Телерман В. В., Ушаков Д. М. Удовлетворение ограничений в задачах математического программирования // Вычислительные технологии. — 1998. — Т. 3, N 2. — С. 45-54.

12. Ushakov D. Some Formal Aspects of Subdefinite Models. — Novosibirsk, 1998. — 23 p. — (Prepr. / Siberian Division of Russian Acad. Sci. IIS; N 49).

Введение

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 Решение задач в среде НеМо+ 102 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 Задачи САПР

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

Программирование в ограничениях базируется на результатах исследований методов решения задач удовлетворения ограничений (ЗУО). Задачи этого класса определяются совокупностью ограничений, связывающих между собой значения различных переменных. Решением задачи является такое означивание переменных, которое удовлетворяет всем заданным ограничениям. Многие задачи, возникающие в различных областях науки и техники, можно отнести к этому классу задач. Алгоритмы, разработанные для их решения, показали свою эффективность на реальных приложениях. Большинство таких алгоритмов являются специализированными (т. е. применимыми только к конкретным видам ЗУО). Однако, существуют универсальные алгоритмы решения ЗУО, одним из которых является предложенный А. С. Нариньяни в начале 1980-х годов метод недоопределенных вычислений [15].

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

Главной целью диссертационной работы является разработка принципиально нового языка программирования в ограничениях, основанного на концепции недоопределенных моделей, с использованием объектно-ориентированного подхода. Теоретические аспекты решения задач удовлетворения ограничений исследуются с помощью аппарата недоопределенных моделей. В рамках проведенных работ создан программный комплекс ЯеМо+, включающий в себя развитые средства спецификации и решения задач.

Диссертационная работа состоит из введения, четырех глав, заключения и двух приложений. Общий объем работы (включая список использованной литературы и приложения) — 160 страниц. Работа включает 8 таблиц и 6 рисунков.

Основные результаты диссертационной работы перечислены ниже.

1. Теоретические результаты.

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

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

• Рассмотрены различные модификации этого алгоритма для поиска точных и оптимальных решений задачи.

• Классифицированы различные виды недоопределенных расширений.

2. Технология программирования.

• Создан объектно-ориентированный язык спецификации задач удовлетворения ограничений в недоопределенных моделях (совместно с В. В. Телерманом, И. Е. Швецовым, В. А. Сидоровым).

• Разработана архитектура программного комплекса НеМо+, предназначенного для интерпретации программ на этом языке (совместно с В. В. Телерманом, И. Е. Швецовым, В. А. Сидоровым).

3. Практическая реализация.

• Реализован вычислитель для недоопределенных моделей и модуль оконного интерфейса с пользователем, которые совместно с реализованным В. А. Сидоровым транслятором программ составляет объектно-ориентированную среду для недоопределенных вычислений НеМо+, функционирующую в среде Microsoft Windows.

• Произведено наполнение комплекса НеМо+ библиотеками недоопределенных типов данных и ограничений (часть библиотек была реализована совместно с В. А. Сидоровым и Г. Б. Загорулько).

4. Экспериментальные исследования.

• Проведена серия экспериментов, показывающая эффективность применения комплекса НеМо+ при решении задач различных классов.

Благодарности

Автор выражает благодарность всем людям, которые внесли вклад в создание этой диссертации, а именно: своему научному руководителю Виталию Васильевичу Телерману за постановку задачи и руководство исследованиями; соавторам комплекса НеМо+: Игорю Евгеньевичу Швецову (сору ководителю проекта), Владимиру Анатольевичу Сидорову (автору компилятора языка НеМо+ и нескольких инструментальных библиотек), Галине Борисовне Загорулько, принявшей участие в разработке библиотек недоопределенных типов данных для комплекса НеМо+; без творческого участия этих людей в проекте НеМо+ данной работе не суждено было появиться на свет; одному из ведущих ученых в области искусственного интеллекта Александру Семеновичу Нариньяни — автору концепции недоопределенных моделей; Давиду Яковлевичу Левину и Татьяне Михайловне Яхно за постоянную поддержку и помощь в организации участия автора в работе нескольких научных конференций; сотрудникам проекта "Уникальк" (руководитель — Александр Леонидович Семенов) за любезно предоставленный код библиотеки интервальных операций; Ивану Геннадьевичу Попову за его помощь в разрешении многочисленных вопросов по поводу функционирования операционной системы и прикладных программ; всем неупомянутым выше сотрудникам Новосибирского филиала Российского НИИ искусственного интеллекта и лаборатории искусственного интеллекта ИСИ СО РАН за техническую помощь в работе над диссертацией и ценную критику; Александру Васильевичу Замулину за ценные замечания к работе [90], которая составила основу теоретической части настоящей диссертации; Сергею Петровичу Шарому, который заинтересовал автора проблематикой интервального анализа и ввел в интервальное сообщество; Полине Строговой за любезно предоставленный компьютер, на котором данная диссертация обрела свой окончательный вид; любимой жене за поддержку на протяжении всей работы над диссертацией, также как родителям и друзьям. Спасибо им всем!

Заключение

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

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

В теоретической части диссертации исследованы аспекты решения задачи оценивания множества свидетелей выполнимости произвольной многосортной экзистенциальной конъюнкции в заданной многосортной модели. Введено формальное понятие недоопределенного расширения многосортной модели, являющееся развитием понятия недоопределенного расширения, предложенного А. С. Нариньяни [16]. Рассмотрен метод оценки множества всех свидетелей выполнимости конъюнкции с помощью элементов недоопределенного расширения, который является развитием алгоритма недоопределенных вычислений [16]. Показана связь этого метода с классическими алгоритмами распространения ограничений, предложенными МаскгуогМ [66], для достижения локальной совместности сети ограничений. В терминах недоопределенного расширения модели описана декларативная семантика метода распространения ограничений в недоопределенных моделях. Денотационная семантика рассматриваемого метода описана в терминах наибольшей неподвижной точки системы отображений специального вида, называемых фильтрациями ограничений. Операционная семантика определена в терминах состояний и правил перехода некоторой абстрактной машины (с недетерминированным выбором). Главный результат теоретической части настоящей диссертации заключен в доказательстве эквивалентности всех этих семантик. Тем самым, автором доказана независимость результата алгоритма распространения ограничений от результатов недетерминированного выбора. Кроме того, доказана завершаемость и корректность рассматриваемого алгоритма. Автором были предложены специальные методы для нахождения недоопределенных оценок точных и оптимальных свидетелей выполнимости заданной конъюнкции, сформулированы и доказаны некоторые их свойства. Наконец, автор классифицировал различные виды недоопределенных расширений и установил некоторые связи между ними.

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

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

1. Агафонов В. Н. Спецификация программ: понятийные средства и их организация. Новосибирск, Наука, 1987, 240 с.

2. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. Москва, Мир, 1987, 260 с.

3. Борде С. Б. и др. Недоопределенное календарное планирование. Труды IV национальной конференции "Искусственный интеллект-94", т. 2, Рыбинск, 1994, сс. 377-381.

4. Гретцер Г. Общая теория решеток. Пер. с англ. под редакцией Д. М. Смирнова. Москва, Мир, 1982, 456 с.

5. Карманов В. Г. Математическое программирование. Москва, Наука, 1986.

6. Колмероэ А., Кануи А., ван Канегем М. Пролог — теоретические основы и современное развитие. Логическое программирование. Москва, Мир, 1988, сс. 27-133.

7. Манцивода А. В. Программирование в ограничениях на Флэнге. Системная информатика, вып. 4, Новосибирск: Наука, 1995, сс. 118-159.

8. Нариньяни А. С. Недоопределенные множества — новый тип данных для представления знаний. Препринт/АН СССР. Сиб. отд-ние. ВЦ. N 232, Новосибирск, 1980. 33 с.

9. Нариньяни А. С. Недоопределенные модели и операции с недоопределенными значениями. Препринт/АН СССР. Сиб. отд-ние. ВЦ. N 400, Новосибирск, 1982, 33 с.

10. Нариньяни А. С. Недоопределенность в системах представления и обработки знаний. Известия АН СССР, Серия "Техническая кибернетика" 5, 1986, сс. 3-28.

11. Нариньяни А. С. Искусственный интеллект: стагнация или новая перспектива. Труды V Национальной конференции по искусственному интеллекту, 1998.

12. Нариньяни А. С., Телерман В. В., Ушаков Д. М., Швецов И. Е. Программирование в ограничениях и недоопределенные модели. Информационные технологии, Москва, 1998. (В печати.)

13. Нечепуренко М. И. Элементы булева интервального анализа. Системное моделирование в информатике, СМ-11, Новосибирск, 1985, сс. 37-61.

14. Нильсон Н. Принципы искусственного интеллекта. Москва, Радио и связь, 1985.

15. Телерман В. В. Активные типы данных. Препринт ВЦ СО АН СССР, 792, Новосибирскк, 1988, 30 с.

16. Телерман В. В., Дмитриев В. Е. Технология программирования на основе недоопределенных моделей. Препринт/РАН. Сиб. отд-ние. ИСИ. N 25, Новосибирск, 1995, 38 с.

17. Телерман В. В., Сидоров В. А., Ушаков Д. М. Интервальные и мультиинтерваль-ные расширения в недоопределенных моделях. Вычислительные технологии, том 2, № 1, Издательство СО РАН, Новосибирск, 1997, сс. 62-70.

18. Телерман В. В., Ушаков Д. М. Удовлетворение ограничений в задачах математического программирования. Вычислительные технологии, том 3, № 2, Издательство СО РАН, Новосибирск, 1998,сс. 45-54.

19. Тыугу Э. X. Концептуальное программирование. Москва, Наука, 1984, 255 с.

20. Ушаков Д. М. Развитие технологии недоопределенных моделей. Материалы XXXIII Международной научной студенческой конференции "Студент и научно-технический прогресс": Математика. Новосиб. ун-т, Новосибирск, 1995, сс. 34-35.

21. Ушаков Д. М. Объектно-ориентированный язык спецификации недоопределенных знаний. Третья международная студенческая школа-семинар "Новые информационные технологии". Тезисы. Крым, май 1995, с. 135.

22. Швецов И. Е. Основные положения технологии активных объектов. Препринт РосНИИ ИИ, Новосибирск, 1995, 26 с.

23. Шокин Ю. И. Интервальный анализ. Новосибирск, Наука, 1981, 112 с.

24. Яковлев А. Г. Машинная арифметика мультиинтервалов. Вопросы кибернетики. Проблемно-ориентированные вычислительные системы, 1987, сс. 66-81.

25. Яхно Т. М. Программирование в ограничениях: обзор и классификация подходов и методов. Системная информатика, вып. 4, Новосибирск: Наука, 1995, сс. 160-192.

26. Apt К. R. The Essence of Constraint Propagation. Journal of Logic Programming, to appear.

27. Babichev А. В., Kadyrova О. В., Kashevarova T. P., Leshchenko A. S., Semenov A. L.

28. UniCalc, A Novel Approach to Solving Systems of Algebraic Equations. Proceedings of the1.ternational Conference on Numerical Analysis with Automatic Result Verifications. Lafayette, Louisiana, USA, 1993. Interval Computations 2, 1993, pp 29-47.

29. Benhamou F., McAllester D., Van Hentenryck P. CLP (Intervals) Revisited, M. Bruynooghe (ed.), Proceedings of the 1994 International Logic Programming Symposium, MIT Press, 1994, pp. 124-138.

30. Benhamou F., Older W. J. Applying Interval Arithmetic to Real, Integer and Boolean Constraints. Journal of Logic Programming 32(1), 1997, pp. 1-24.

31. Borning A., Freeman-Benson В., Wilson M. Constraint Hierarchies. Constraint Programming: Proceedings 1993 NATO ASI Parnu, Estonia, Springer-Verlag, 1994, pp. 80-122.

32. Burstall R. M. A program for solving word sum puzzles. Сотр. J. 12, 1969, pp. 48-51.

33. Caseau Y., Puget J.-F. Constraints on Order-Sorted Domains. Manfred Meyer (ed.), Proceedings ECAI'94 Workshop on Constraint Processing, Amsterdam, 1994.

34. Cleary J. G. Logical Arithmetic. Future Generation Computing Systems 2(2), 1987, pp. 125-149.

35. Cleary J. G. Constructive Negation of Arithmetic Constraints. Proceedings of Workshop on Interval Constraints, ILPS'95, Portlend, Oregon, USA, 1995.

36. Colmerauer A. An introduction to Prolog III. Communications of the ACM 33(7), 1990.

37. Davis E. Constraint Propagation with Interval Labels. Artificial Intelligence 32, 1987, pp. 281— 331.

38. Dennis J. E., Schnabel R. B. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall, Englewood Cliffs, New Jersey, 1983.

39. Deville Y., Van Hentenryck P. An Eflicient Arc Consistency Algorithm for a Class of CSP Problems. Proceedings of IJCAI, 1991, pp. 325-330.

40. Diaz D., Codognet P. A minimal extension of WAM for clp(FD). Proceedings of the 10th Interbational Conference on Logic Programming, 1993.

41. Fikes R. E. REF-ARF: A System for Solving Problems Stated as Procedures. Artificial Intelligence 1(1), 1970, pp. 27-120.

42. Freeman-Benson B. N., Borning A. Integrating Constraints with an Object-Oriented Language. Proceedings of ECOOP'92, 1992, pp. 268-286.

43. Freuder E. C., Wallace R. J. Partial Constraint Satisfaction. Artificial Intelligence 58, 1992, pp. 21-70.

44. Freuder E. Exploiting Structure in Constraint Satisfaction Problems. Constraint Programming: Proceedings NATO ASI Parnu, Estonia, Springer-Verlag, 1994, pp. 54-79.

45. Gaede V., Wallace M. An Informal Introduction to Constraint Database Systems. Lecture Notes in Computer Science 1191, 1997, pp. 7-52.

46. Gervet C. Conjuncto: Constraint Logic Programming with Finite Set Domains. Technical report ofECRC, EC-94-15, 1994.

47. Goguen J. A., Meseguer J. Models and Equality for Logical Programming. Lecture Notes in Computer Science 250, 1987, pp. 1-22.

48. Hyvônen E. Constraint Reasoning Based on Interval Arithmetic. Proceedings of IJCAI, 1989, pp. 193-199.

49. Hyvôonen E., De Pascale S. Interval Computations on the Spreadsheet. Applications of Interval Computations, R. Baker Kearfort and Vladik Kreinovich (Eds.), Kluwer Academic Publishers, 1996, pp. 169-210.

50. ILOG Optimization Suite white paper, http://www.ilog.com/papers/optimization/

51. Jaffar J., Michayov S., Stuckey P. J., Yap R. H. C. The CLP(ft) Language and System. TOPLAS: ACM Transactions on Programming Languages and Systems, 14(3), 1992, pp. 339-395.

52. Jaffar J., Maher M. J. Constraint Logic Programming: A Survey. Journal of Logic Programming 19/20, 1994, pp. 503-581.

53. Kumar V. Algorithms for Constraint Satisfaction Problems: A Survey. AI Magazine 13(1), 1992, pp. 32-44.

54. Lhomme O. Consistency Techniques for numeric CSPs. Proceedings of IJCAP93, Chambery. France, pp. 232-238.

55. Mackworth A. K. Consistency in Networks of Relations. Artificial Intelligences, 1977, pp. 99-118.

56. Mayoh B. Constraint Programming and Artificial Intelligence. B. Mayoh, E. Tyugu, J. Penjaam (Eds.), Constraint Programming: Proceedings 1993 NATO ASI Parnu, Estonia, Springer-Verlag, 1993, pp. 18-53.

57. Mohr R., Henderson T. Arc-consistency and path-consistency revisited. Artificial Intelligence 28, 1986, pp. 225-233.

58. Mohr R., Masini G. Good old discrete relaxation. Y. Kodratoff (ed.), Proceedings of the 8th European Conference on Artificial Intelligence (ECAI), Pitman Publishers, 1988, pp. 651-656.

59. Montanari U. Networks of Constraints: Fundamental Properties and Application to Picture Processing. Information Science 7(2), 1974, pp. 95-132.

60. Older W., Vellino A. Extending Prolog with Constraint Arithmetic on Real Intervals. Proceedings of the Canadian Conference on Electrical and Computer Engineering, 1990.

61. Puget J.-F., Leconte M. Beyond the Glass Box: Constraints as objects. Logic Programming. Proceedings of the 1995 International Symposium, MIT Press, pp. 513-527.

62. Puget J.-F. PECOS A High Level Constraint programming Language. Proceedings of Spicis 92, Singapore, September, 1992.

63. Saraswat V. A., Rinard M. Concurrent Constraint Programming. Proceedings of ACM Symposium on Principles of Programming Languages, 1990, pp. 232-245.

64. Shary S. P. A New Approach to the Analysis of Static Systems Under Interval Uncertainty. Scientific Computing and Validated Numerics, edited by G. Alefeld, A. Frommer and B. Lang, Akademie Verlag, Berlin, 1996, pp. 118-132.

65. Shokin Y. I. On Interval Problems, Interval Algorithms and Their Computational Complexity. Scientific Computing and Validated Numerics, Akademie Verlag, Berlin, 1996, pp. 314-328.

66. Shvetsov I., Kornienko V., Preis S. Interval spreadsheet for problems of financial planning. Proceedings of PACT'96.

67. Shvetsov I., Semenov A., Telerman V. Application of Subdefinite Models in Engineering. Artificial Intelligence in Engineenring 11, 1997, pp. 15-24.

68. Telerman V. V. Propagation of Mathematical Constraints in Subdefinite Models. J. Calmet and J. A. Campbell (Eds.), Integrating Symbolic Mathematical Computation and Artificial Intelligence, Lecture Notes in Computer Science 958, 1995, pp. 191-208.

69. Telerman V., Lipski S., Ushakov D. Object-Oriented Constraint-Based Database Processing. Proceedings of PACT'98, London, 1998.

70. Telerman V., Sidorov V., Ushakov D. Problem Solving in the Object-Oriented Technological Environment NeMo+. Perspectives of System Informatics : proceedings. Lecture Notes in Computer Science 1181, Springer, 1996, pp. 91-100.

71. Telerman V., Ushakov D. Subdefinite Models as a Variety of Constraint Programming. Proceedings of the 8th International Conference on Tools with Artificial Intelligence, ICTAI'96, IEEE Computer Society, 1996, pp. 157-163.

72. Telerman V., Ushakov D. Using the Subdefiniteness in Real World Models. Proceedings of the 6th International Conference EWHCP96. Moscow, Russia, August 12-16, 1996, pp. 194-206.

73. Telerman V., Ushakov D. Levels of Parallelism in CSP with Subdefinite Objects. Proceedings of the Poster Session of JFPLC'97, Sixth French Conference on Logic and Constraint Programming, Orleans, France, 26-28 May 1997, Rapport de Recherche LIFO 97-6.

74. Telerman V., Ushakov D. Constraint Satisfaction Techniques for Mathematical Programming Problems. Proceedings of International Conference on Interval Methods and their Application in Global Optimization, INTERVAL '98, April 20 23, 1998, Nanjing, China.

75. Ushakov D. Some Formal Aspects of Subdefinite Models. Preprint IIS SB RAS, no. 49, Novosibirsk, 1998, 23 p.91. van Emden M. H. Value constraints in the CLP scheme. Constraints 2(2), 1997, pp. 163-184.

76. Van Hentenryck P. Constraint Satisfaction in Logic Programming, Logic Programming Series, MIT Press, Cambridge, MA, 1989.

77. Van Hentenryck P. Constraint Satisfaction Using Constraint Logic Programming. Artificial Intelligence 58, 1992, pp. 113-159.

78. Van Hentenryck P., Michel L., Deville Y. Numerica: a Modeling Language for Global Optimization. The MIT Press, Cambridge, Mass., 1997.

79. Voronkov A. Merging Relational Database Technology with Constraint Technology. Perspectives of System Informatics : proceedings, Lecture Notes in Computer Science 1181, Springer, 1996, pp. 409-419.

80. Walinsky C. CLP(S*): Constraint Logic Programming with Regular Sets. G. Levi and M. Martelli (Eds.), ICLP'89: Proceedings 6th International Conference on Logic Programming, MIT Press, 1989, pp. 181-196.

81. Waltz D. Understanding line drawing in scenes with shadows. Patrick Henry Winston (Ed.), The Psychology of Computer Vision, McGraw-Hill, 1975, pp. 19-91.

82. Wright M. H. Numerical Methods for nonlinearly constraint optimization. Ph. D. Thesis, Stanford University, 1976.

83. Yakhno T., Petrov E. LogiCalc: Integrating Constraint Programming and Subdefinite Models. Proceedings of PACT'96, 1996, pp. 357-372.