Методы и средства программирования в ограничениях для систем автоматизации проектирования тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Сидоров, Владимир Анатольевич

• Сидоров, Владимир Анатольевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Сидоров, Владимир Анатольевич

Введение.

Глава 1. Система NemoNext. Формальное описание.

Методы достижения совместности.

Базовые понятия.

Модель NemoNext.

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

Виды педоопределённости.

Одиночное значение (Single).

Интервал (Interval).

Перечисление (Enum).

Ограниченное перечисление (EnumN).

Мультиинтервал (Multilnterval).

Ограниченный мультиинтервал (MultilntervalN).

Смешанный вид недоопределённости (MixedN).

Структурный вид недоопределённости (Struct).

Особые случаи.

Логический тип данных.

Применение вида недоопределённости Single.

Применение мультиинтервалов.

Типы данных.

Целые числа.

Вещественные числа.

Логический тип данных.

Строки.

Структуры.

Запись.

Массив.

Множество.

Ссылка.

Ограничения.

Ограничения для типа данных interval int.

Ограничения для типа данных interval real.

Ограничения для типа данных single bool.

Ограничения для типа данных enum string.

Ограничения для типа данных array.

Ограничения для типа данных interval set.

Глава 2. Система программирования в ограничениях NemoNext.

Архитектура системы NemoNext. Инструментальный уровень.

Библиотеки типов данных и ограничений.

Вычислитель.

Сервисный уровень.

Архитектура системы NemoNext. Пользовательский уровень.

Декларативное представление модели.

Модульность.

Виды недоопределённости.

Типы данных.

Отношения.

Объектно-ориентированная парадигма описания модели.

Механизм обобщённых классов и отношений.

Классы решаемых задач.

Глава 3. Интеграция системы программирования в ограничениях NemoNext в САПР.

Параметрическое проектирование.

Реализация параметрического проектирования в системе CATIA V5.

Виды инженерных отношений.;.

Параметрическая оптимизация.

Интеграция NemoNext в систему CATIA V5.

Методы поиска точного решения в системе NemoNext.

Поиск точного решения.

Оценка точности найденного решения.

Нахождение точного решения, ближайшего к заданному.

Задача оптимизации.

Иерархическое удовлетворение ограничений.

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

Нахождение нескольких точечных решений.

Ползущие решения.

Поиск частичного решения.

Реализация.

Глава 4. В1аскВох-ограничение.

Формулировка задачи.

Взаимодействие внешней процедуры с В1аскВох-ограничением.

Эвристики.

Многомерные эвристики.

Алгоритм «Бисекция».

Градиентный метод.

Метод координатного спуска.

Дополнительные задачи.

Локальность.

Поиск условного экстремума.

Несовместные точки.

Поиск точного решения.

Поиск решения, близкого к заданной точке.

Одномерные Эвристики.

Квадратичная интерполяция.

Локальность.

Другие эвристики.

Алгоритм «Interval Bisection».

Реализация.

Введение диссертации (часть автореферата) на тему «Методы и средства программирования в ограничениях для систем автоматизации проектирования»

Метод удовлетворения (распространения) ограничений является одним из активно развивающихся подходов для решения нестандартных и сложных задач. Он относится к той области искусственного интеллекта, которая занимается решением комбинаторных задач, а также работой с неточными и неполными данными. Задача удовлетворения ограничений (constraint satisfaction problem, CSP) неформально описывается следующим образом:

- Решаемая задача состоит из набора переменных и набора ограничений.

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

- Ограничения связывают переменные и ограничивают множества их значений.

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

- Целью решения CSP может быть как поиск одного решения (возможно, с заданными свойствами), так и поиск всех решений.

Впервые задача удовлетворения ограничений была сформулирована Хаффманом (Huffman) [20] и Маквортом (Mackworth) [28] в 70х годах.

Примерно до середины 90х годов задача удовлетворения ограничений рассматривалась только для дискретных данных (finite domain CSP; CSP FD) [6, 14, 30, 43]. Классическим примером CSP FD является задача о расстановки ферзей: на шахматном поле размером NxN требуется расположить N ферзей так, чтобы они не били друг друга. Описание задачи состоит из N переменных, соответствующих ферзям и набора ограничений, реализующих условия «2 ферзя не могут стоять на одной вертикали», «2 ферзя не могут стоять на одной горизонтали», «2 ферзя не могут стоять на одной диагонали». Пример описания данной задачи в системе NemoNext приведён ниже в Главе 2.

Задачи удовлетворения ограничений для непрерывных областей данных обычно называются численными задачами удовлетворения ограничений {numerical CSP; NCSP) [12, 18, 21, 25]. NCSP очень часто встречаются в реальных приложениях, например, при моделировании физических явлений, при описании химических процессов, в системах моделирования и проектирования. Как правило, эти задачи представляют собой совокупность уравнений и неравенств, связывающих переменные с непрерывной областью определения, хотя иногда ограничения могут задаваться в виде таблиц, а также включать целочисленные переменные. Очень часто реальные системы являются недоопределёнными или переопределёнными. Поэтому применение классических вычислительных методов или методов компьютерной алгебры для решения таких задач оказывается неудачным и приходится прибегать к упрощению исходной системы.

Примером NCSP может быть решение уравнения <<sin(x*cos(y))-cos(y*sin(x)) = 0». Задача состоит из двух переменных («х» и «у») и одного ограничения. В общем случае любая система уравнений и неравенств может рассматриваться как задача NCSP.

Таким образом, для решения CSP выделяют два класса методов - методы решения CSP FD и методы решения NCSP. Для каждого из этих классов разработан свой набор эффективных алгоритмов и построены соответствующие прикладные системы [4, 23, 43, 45]. Причём в настоящее время методы распространения ограничений все чаще объединяются с другими подходами. Например, методы распространения ограничений над конечными областями (CSP FD) используется в комбинации с методами исследования операций и методами линейного программирования, а методы распространения ограничений над непрерывными областями (NCSP) используют методы интервальной математики.

В начале 80х годов А.С. Нариньяни был предложен метод недоопределённых вычислений [57, 59]. Неформально, метод может быть описан следующим образом:

- Модель (описание задачи) состоит из конечного набора объектов и конечного набора ограничений.

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

- Ограничения связывают объекты и вычисляют новые (недоопределённые) значения для своих аргументов.

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

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

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

- Семейство математических решателей 11шСа1с [2, 3, 24], ориентированных на решение численных задач.

- Мультиагентные системы ТАО [67, 68] позволяют использовать понятие «время» в постановке задачи и моделировать поведение динамических систем.

- Экспертные системы для работы с неточными данными [51, 52].

- Семейство систем НеМо (Немо-Тек - [63]; НеМо+ [37, 46, 49]), характерной чертой которых является расширяемость (возможность настроить систему на конкретную предметную область путём создания новых типов данных и ограничений).

В конце 90х годов фирма Dassault Systèmes, ведущий производитель инженерных САПР верхнего уровня1, в рамках развития своего флагманского продукта CATIA V5 [10], столкнулась с потребностью в универсальном решателе задач удовлетворения ограничений. В этот момент основным перспективным направлением развития системы являлось повышение интеллектуальности системы. Под понятием «интеллектуальность» подразумевался набор инструментов, повышающих уровень автоматизации процесса проектирования, в частности: контроль корректности модели изделия при её модификации, автоматическое построение различных конфигураций изделия по внешним параметрам, автоматическая корректировка модели при изменении пользователем её параметров, нахождение оптимальных конфигураций и т.д. Основными требованиями, предъявляемыми к такому универсальному вычислителю, были:

- Способность решать произвольные системы уравнений и неравенств.

- Лёгкая интеграция в систему С ATI A V5.

- Возможность настраивать вычислитель для решения специализированных задач CATIAV5.

Фирма Dassault Systèmes выбрала в качестве базового вычислителя для решения CSP систему НеМо+. На основе НеМо+ была разработана и реализована система NemoNext, которая в отличие от НеМо+ удовлетворяла всем требованиям Dassault Systèmes по технологичности, настраиваемости, расширяемости и другим требованиям, предъявляемым к промышленным

1 Системы автоматизации проектирования (САПР) разделяются на три класса систем, в зависимости от набора предоставляемых возможностей, цены одного рабочего места и рыночного позиционирования: системы нижнего уровня, системы среднего уровня, системы верхнего уровня. программным продуктам. Тем не менее, в процессе интеграции системы №то№х1 в САПА У5 возник целый ряд задач, потребовавших разработки специализированных методов и алгоритмов.

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

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

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

Для достижения поставленной цели в диссертации последовательно решены следующие задачи исследования:

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

2. Разработан декларативный объектно-ориентированный язык описания задачи удовлетворения ограничений.

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

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

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

6. Разработана архитектура системы программирования в ограничениях №то№х!;.

7. Осуществлена интеграция системы №то№х1 в САПР САТ1АУ5.

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

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

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

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

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

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

Для решения задачи удовлетворения ограничений, системой №то№х1 используется метод недоопределёниых вычислений, описанный в работах [39, 44, 59, 62]. Формальное доказательство сходимости метода было представлено в работе [44], но скорость сходимости метода, в силу его универсальности, сильно зависит от способа реализации конкретных ограничений и выбранного представления данных: различные (но при этом корректные с точки зрения метода недоопределёниых вычислений) реализации могут приводить к различным результатам и могут иметь принципиально разную скорость сходимости. В первой главе работы приведено краткое формальное описание метода недоопределёниых вычислений. На основе введённых понятий выполняется уточнение и конкретизация способов представления множества значений (видов недоопределённости) переменных, и дано краткое описание их основных свойств. Далее приводится формальное описание основных типов данных и семантики некоторых видов ограничений.

Вторая глава посвящена описанию архитектуры системы программирования в ограничениях №то№х<:. При её разработке учитывались следующие базовые принципы:

Универсальность системы означает способность формулировать и решать с её помощью максимально широкий диапазон задач. Сюда можно отнести следующие свойства:

- Расширяемость системы дополнительными типами данных и ограничений.

- Единый универсальный алгоритм решения задачи.

- Использование концепции «недоопределённость» для работы с неточными и не полностью определёнными данными. Тем самым существенно расширяется диапазон решаемых задач и они точнее соответствуют реальным задачам пользователя.

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

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

Описание реализации вышеуказанных принципов системы программирования в ограничениях приводится с двух точек зрения:

- С точки зрения архитектуры и внутреннего строения системы.

- С точки зрения пользователя и языка описания модели.

В третьей главе описываются проблемы интеграции системы NemoNext в промышленные программные продукты. Так как основным заказчиком работ по системе NemoNext выступает фирма Dassault Systèmes, то система с самого начала проектировалась для использования в качестве универсального решателя в системах автоматизации проектирования (САПР). Соответственно, одной из важнейших задач, которую необходимо было решить, была проблема интеграции системы в состав САПР С ATI A V5. В третьей главе описываются модули САПР CATIA V5, которые взаимодействуют с системой NemoNext. Показывается роль, которую выполняет система программирования в ограничениях в составе CATIA V5 и описываются задачи, которые NemoNext решает по запросу внешней системы. Эти задачи заметно отличаются от задач, обычно решаемых системой программирования в ограничениях. В частности, САПР может потребоваться найти:

- Решение с заданной точностью.

- Решение, ближайшее к текущему значению аргументов.

- Несколько или все различные решения.

- Частичное решение.

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

В четвёртой главе описывается концепция использования внешних вычислительных модулей в задаче удовлетворения ограничений. Такой вычислительный модуль мы будем далее называть ШаскВох-процедурой, а отношение, которое данный модуль реализует - чёрным ящиком или ВШскВох. Соответствующее ограничение системы программирования в ограничениях будем называть В1аскВох-ограничением.

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

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

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

Также можно выделить ряд дополнительных факторов, серьёзно влияющих на решение указанной задачи:

- Большое время вычисления одного вызова В1аскВох-процедуры.

- Неизвестная природа В1аскВох отношения.

- Неизвестная область определения В1аскВох.

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

В результате, были разработаны несколько специализированных методов и алгоритмов, которые позволили решить все указанные выше задачи [35].

Предложенные алгоритмы и методы реализованы в системе NemoNext, входят в состав нескольких продуктов (компонентов) САПР CATIA V5 и поставляются клиентам Dassault Systèmes, что характеризует практическую значимость данной работы.

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и четырёх приложений. Объем диссертации: полный - 152 страниц; без приложений - 128 страниц. Список литературы содержит 72 наименований. Работа включает 16 рисунка и 12 таблиц.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Сидоров, Владимир Анатольевич

Результаты работы докладывались на международных конференциях.

Личный вклад автора.

В рамках разработки системы автор диссертации выполнил следующие работы:

- Исследование видов недоопределённости MultiintervalN и MixedN, структурных недоопределённых типов данных.

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

- Разработка объектно-ориентированного декларативного языка описания модели и реализация его транслятора.

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

- Разработка концепции использования внешних вычислительных модулей (BlackBox) в задаче удовлетворения ограничений. Рзаработка специализированных алгоритмов и методов для работы с BlackBox. Реализация библиотеки BlackBox системы NemoNext.

Кроме того автор внёс большой вклад в разработку ядра системы, модуля поиска точных решений, модуля интеграции с системой С ATI A V5, модуля абстрактных типов данных, модуля строковых типов данных.

Дальнейшие работы по развитию системы NemoNext можно разбить на несколько групп:

- Создание дополнительных продуктов в рамках САПР С ATI A V5, таких как: система контроля максимальных допусков изделия (Tolerancing), интервальный вычислитель (Interval Solver), система совместной разработки изделия (Collaborative Design). Возможно, данные продукты потребуют от системы NemoNext решения новых задач.

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

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

Заключение.

Одним из способов повышения функциональности систем автоматизации проектирования является использование в их составе систем программирования в ограничениях для решения различных задач. При такой интеграции, зачастую, возникает ряд научных проблем, требующих специальных исследований. В данной работе рассматривается полный спектр задач, возникающих при организации взаимодействия между системой программирования в ограничениях NemoNext и машиностроительной САПР CATIA V5 фирмы Dassault Systèmes, начиная с проектирования системы программирования в ограничениях и заканчивая созданием специальной техники для работы со специфическими сущностями САПР.

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

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

2. Разработана концепция использования внешних вычислительных модулей (механизм В1аскВох-ограничений) в задаче удовлетворения ограничений.

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

4. Разработана архитектура и выполнена реализация системы программирования в ограничениях NemoNext.

5. Выполнена интеграция системы NemoNext в САПР CATIA V5.

Кроме того получены менее значимые результаты:

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

Разработаны оригинальные виды недоопределённости, типы данных и ограничения.

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

Список литературы диссертационного исследования кандидат физико-математических наук Сидоров, Владимир Анатольевич, 2007 год

1.V., Hopcroft J.E., Ullman J.D. Data structures and algorithms. — Reading: Addison-Wesley, 1983.

2. Babichev A., Kadyrova O., Kashevarova Т., Semenov A. UniCalc as a tool for solving problems with inaccurate and subdefmite data // Proc. Conf. Interval'92. — Interval Computations. — 1992. — Vol. 3(5). — P. 13-16.

3. Benhamou F., McAllester D., Van Hentenryck P. CLP(Intervals) Revisited, // Proc. 1994 Intern. Logic Progr. Simp. — MIT Press, 1994. — P. 124-138.

4. Besiere C. Arc-consistency and Arc-consistency again. // Artificial Intelligence.1994. —N65. —P. 179-190

5. Besiere C., Freuder E.C., Region J.C. Using inference to reduce arcconsistency computation. // Proc. 14th IJCAI. — 1996. — Vol. 1. — P. 592-598.

6. Borning A., Freeman-Benson В., Wilson M. Constraint Hierarchies. // Constraint Programming: Proc. 1993 NATO ASI Parnu, Estonia. — SpringerVerlag, 1994. —P. 80-122.

7. CAA С++ Source Checker: http://www.3ds.com/index.php?id=847&type=222&nocache=l&cHash=e6a36 cc62b&3dsplmproductsdomain.=19&3dsplmproducts[product]=273&filename =doc/

8. CATIA V5R17 Fact Sheet to review the new features of the Solution: http://www.3ds.com/fileadminAA 5R17/c517factsheet.pdf

9. CATIA V5R17 PLM solution for digital product definition and simulation: http://www.3ds.com/products-solutions/plm-solutions/catia/overview/

10. Cleary J. G. Logical Arithmetic. // Future Gener. Сотр. Systems. — 1987. —1. Vol 2(2). —P. 125-149.

11. Collavizza H., Delobel F., Rueher M. A note on partial consistencies over continuous domains // Proc. CP98, Pisa, Italy, October 26-30, 1998. — Berlin a. o.: Springer Verlag, 1998. —P. 147-161.

12. Davis E. Constraint Propagation with Interval Labels. // Artificial Intelligence.1987.—N32. —P. 281-331.

13. Deville Y., Van Hetenryck P. An Efficient Arc Consistency Algorithm for a Class of CSPProblems. //Proc. IJCAI. — 1991, —P. 325-330.

14. Gaschning J.A General Backtracking Algorithm That Eliminates Most Redundant Tests. // Proceeding IJCAI-77. — 1997. — P. 457.

15. Ginsberg M.L. Dynamic BackTracking. // J. Artificial Intelligence Research. — 1993.—N1.—P. 25-46.

16. Golomb S.W. , Baumert L.D. Backtrack programming // J. of the ACM. — 1965. —Vol 12,N.4. —P. 516-524.

17. Hansen E.A., Sengupta S. Bounding solutions of systems of equations using interval analysis // BIT. — 1981. — Vol. 21. — P. 203-211.

18. Haralick R.M., Elliot G.L. Increasing Tree Search Efficiency For Constraint Satisfaction Problems. // Artificial Intelligence. — 1980. — N 14. — P. 263313.

19. Huffman D.A. Impossible objects as nonsence sentences // Machine Intelligence. — 1971. — Vol. 6. — P. 295-323.

20. Hyvonen E. Constraint Resoning Based on Interval Arithmetic. // Proc. IJCAI.1989. —P. 193-199.

21. Nelder J.A., Mead R. A simplex method for function minimization. Computer Journal, P. 308-313,1965.

22. Kumar V. Algorithms for Constraint Satisfaction Problems: A Survey. // AI Magazine. — 1992. —Vol.l3(l). —P. 32-44.

23. Lhomme O. Consistency techniques for numeric CSP's // Proc. of the 13th IJCAI / Ed. by R. Bajcsy. — IEEE Computer Society Press, 1993. — P. 232238.

24. Lipski S., Sidorov V., Telerman V., Ushakov D. Database Processing in Constraint Programming Paradigm Based on Subdefinite Models // Joint Bulletin ofNCC&IIS,. 12 (1999), NCC Publiher. Novosibirsk, 1999.

25. Mackworth А.К. Consistency in Networks of Relations. // Artificial Intelligence. — 1977. — N 8. — P. 99-118.

26. Minton S., Johnston M.D., Philips A.B., Laird P. Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. // Proc. of AAAI90. — 1990. — P. 17-24.

27. Mohr R., Henderson T. Arc-consistency and path-consistency revisited. // Artificial Intelligence. — 1986. — N 28. — P. 225-233.

28. Narin'yani A.S. NE-factors: Different Pragmatics of an Interval in Knowledge Representation // Conf. on Numerical Analisys with Automatic Result Verification, Lafayette, Louisiana, February 25-March 1, 1993.

29. Nilsson N.J. Principles of artificial intelligence. — Palo Alto: Tioga, 1980. 66. Numerical Computation Guide. — Mountain View, USA, November, 1995.

30. Lewis R.M., Torczon V., and Trosset M.W. Direct search methods: Then and now. Journal of Computational and Applied Mathematics, 124, 2000.

31. Jacoby S.L.S., Kowalik J.S., and Pizzo J.T. Iterative Methods for Nonlinear Optimization Problems. Prentice-Hall, Englewood Cliffs, N.J., 1972.

32. Telerman V., Sidorov V., Ushakov D. Problem Solving in the Object-Oriented Technological Environment NeMo+, // Perspectives of System Informatics: Proc., Lecture Notes in Computer Science 1181. — Berlin a.o.: Springer-Verlag, 1996. —P. 91-100.

33. Telerman V., Ushakov D. Data Types in Subdifinite Models. // Artificial Intellegence and Symbolic Mathematical Computation: Proc., Lecture Notes in Computer Science 1138. — Springer-Varlag, 1996. — P. 305-319.

34. Telerman V., Ushakov D. Subdififnite Models as a Variety of Constraint Programming. // Proc. 8th Intern. Conf. on Tools with Artificial Intelligence. ICTAI'96. —IEEE Computer Soc., 1996, —P. 157-163.

35. Telerman V.V. Propagation of numerical constraints in sub-definite models // International Congress on Computer Systems and Applied Mathematics (CSAM'93), St.Petersburg, July 19-23, Abstracts. — St.Petersburg, 1993. — P. 101-102.

36. Tsang E. Foundation of Constraint Satisfaction. — London: Academic Press Ltd., 1993.

37. Ushakov D. Some Formal Aspects of Subdifinite Models. — Novosibirsk, 1998. — 23 p. — (Preprint/A. P. Ershov Institute of Informatics Systems,

38. Siberian Division of Russian Academy of Sciences; N 49).

39. Van Hentenryck P., Michel L., Deville Y. Numérica: a modeling language for global optimization. — Cambridge: MIT Press, 1997.

40. Telerman V., Ushakov D., Sidorov V. Object-Oriented Constraint Programming Environment NeMo+ and its Applications // ICTAI'97, Newport Beach, CA, USA, 1997.

41. Гурии JI.C., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. Москва: Советское радио, 1968 -463 с.

42. Загорулько Ю.А., Попов И.Г. Представление знаний в интегрированной технологической среде SemP-TAO. // Проблемы представления и обработки не полностью определенных знаний / под ред. И. Е. Швецова. — Москва,

43. Новосибирск, 1996. — С. 59-74.

44. Загорулько Ю.А. Технология конструирования развитых системобработки знаний на основе семантических сетей и систем продукций.-Новосибирск, 1995. — 65 с. (Препр./ РАН. Сиб. отд-ние. ИСИ; N 27).

45. Летова Т.А., Пантелеев A.B. Экстремум функций в примерах и задачах. Москва: МАИ, 1998. — 376 с.

46. Лоенко М .Ю. Алгоритм коррекции решения // Тр. конф. молодых ученых, посвященная 10-летию ИВТ СО РАН. — Новосибирск, 2001. — Т. 1. — С. 49-53.

47. Нариньяни A.C. недоопределённость в системах представления и обработки знаний. // Изв. АН СССР. Сер. "Техн. кибернетика." — 1986. — N5. —С. 3-28.

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

49. Нариньяни А.С, Телерман В.В., Ушаков Д.И., Швецов И.Е. Программирование в ограничениях и недоопределённые модели // Информационные технологии. — М.: Машиностроение, 1998. — № 7. — С. 13-22.

50. Нариньяни A.C. недоопределённые модели и операции с недоопределёнными значениями. — Новосибирск, 1982. — 33с. — (Препр. / АН СССР. Сиб. отд-ние. ИЦ; N 400).

51. Сидоров В.А. Программирование в ограничениях с чёрными ящиками. —

52. Новосибирск, 2003. — 39 с. — (Препр. / ЗАО Ледас; N2).

53. Телерман В.В. Использование мультиинтервалов в недоопределённыхмоделях. // Тез. докл. X всесоюз. семинара " Параллельное программирование и высокопроизводительные системы: Методы представления знаний в информационных технологиях". — Киев, 1990.

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

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

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

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

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

59. Швецов И.Е., Нестеренко Т.В., Старовит С.А., Титова М.В. Технология активных объектов: от концепции к реализации. //Проблемы представления и обработки не полностью определенных знаний / под. ред. И. Е. Швецова.

60. Москва, Новосибирск, 1996. — С. 88-100.

61. Швецов И.Е., Телерман В.В. Интервалы и мультиинтервалы внедоопределённых вычислительных моделях // Тр. Междунар. конф. по интервальным и стохастическим методам в науке и технике "ИНТЕРВАЛ92", 1992. —Т. 1, —С. 201-203.

62. Загорулько Ю.А., Попов И.Г., Костов Ю.В., Сергеев И.П. Общая концепция агентов в системе моделирования SEMP-A. // Труды международной научно-практической конференции KDS-2001 "Знание

63. Диалог- Решение". — Т. 1. — Санкт-Петербург, 2001. — С.259-267.

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