Парадигма программирования 4 Императивное программирование 6


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



Скачать 43,03 Kb.
страница4/5
Дата02.08.2022
Размер43,03 Kb.
#187953
1   2   3   4   5
Связанные:
Microsoft Word Document
Системная архитектура и структура ORACLE

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


Программирование в ограничениях - достаточно новое направление в декларативном программировании. Появилось оно во многом в результате развития систем символьных вычислений, искусственного интеллекта и исследования операций. Программирование в ограничениях - это программирование в терминах "постановок задач". Постановка задачи - это конечный набор переменных V = {v[1], ..., v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1], ...,D[n]}, и набор ограничений С = {C[1],...,C[m]}. Ограничения представлены как утверждения, в которые входят в качетсве "параметров" переменные из некоторого подмножества V[j],j=1..m набора V. Решение такой задачи - набор значений переменных, удовлетворяющий всем ограничениям C[j].
Синтаксически такую постановку задачи пожно записать как "правило" для "типизированного" Пролога:
problem(V1:D1, ..., Vn:Dn) :-
С1, ... Cm.
Семантически, однако, программирование в ограничениях отличается от традиционного логического программирования в первую очередь тем, что исполнение программы рассматривается не как доказательство утверждения, а нахождение значений переменных. При этом порядок "удовлетворения" отдельных ограничений не имеет значения, и система программирования в ограничениях, как правило, стремится оптимизировать порядок "доказательства" утверждений с целью минимизации отката в случае неуспеха.С этой целью набор ограничений может быть соответствующим образом преобразован - по правилам, аналогичным правилам Пролога. Любую задачу можно рассматривать как ограничение: "значения переменных должны быть решением этой задачи". Часто о программировании в ограничениях говорят исключительно как о "дополнительной" ветви логического программирования.
В качестве примера, мы можем задать системе программирования в ограничениях следующий запрос:
? (X : integer) X>1, member(X, [1,2,3]).
Типичная Пролог-система на таком запросе выдаст ошибку: Х является неинициализированной переменной, и его нельзя сравнивать с числом 1. Система, поддерживающая программирование в ограничениях, воспримет эти "утверждения" как ограничения (а не как цели, которые требуется доказать), и выдаст нам требуемые решения: Х=2 и Х=3. Это может быть реализовано, например, следующим образом: при "прологовском" доказательстве утверждения Х>1 будет выведено ограничение на переменную Х (естественно, Х>1). Результаты доказательства следующей подцели (member(...)) будут проверяться на удовлетворение этому ограничению (фактически, будет передоказываться утверждение X>1 для конкретных значений Х). Первый вариант (Х=1) не пройдет эту проверку, остальные будут приняты как удовлетворяющие выведенному ограничению.
Задачу в ограничениях можно рассматривать и как задачу о минимальном необходимом наборе ограничений, что позволяет в некоторых случаях описать в явном виде бесконечные множества решений. Так, минимальным необходимым набором ограничений для задачи X:integer, X>2, X<4 будет Х=3; для задачи X,Y:integer, X*2=Y таким набором будет X:integer, Y mod 2 = 0.
Системы символьных вычислений нередко позволяют использовать "допущения" - по сути, те же ограничения. И на следующий (простой) запрос:
assume X>0. 
when X+1<10 ?
выдавать ответ:
X in (0..9).
Как правило, такие системы могут доказывать достаточно нетривиальные матичематические утверждения, выводя "минимальными необходимыми ограничениями", и проверяя эти ограничения на совместность. В задачах исследования операций и реализации искусственного интеллекта часто используется некоторое "пространство решений", сужением которого достигается необходимый результат. Такие "сужения" естественным образом представляются как ограничения. Кроме этого, программирование в ограничениях естественным образом приложимо к задаче автоматического вывода типов: выведенные ограничения на переменные, соответствующие типам подвыражений, будут задавать "минимальный набор требований на типы". Так, удовлетворение ограничения type_correct("lambda x -> x+1") потребует выполнения набора ограничений{number(x.type_of)}, что, буквально, обозначает, что для того, чтобы прибавить к х единицу, х должно быть числом.
Как и логическое программирование, программирование в ограничениях предполагает совершенно аналогичную "естественную" реализацию на параллельных платформах.

Скачать 43,03 Kb.

Поделитесь с Вашими друзьями:
1   2   3   4   5




База данных защищена авторским правом ©psihdocs.ru 2022
обратиться к администрации

    Главная страница