Програмирање ограничењаУ рачунарству, програмирање ограничења је програмска парадигма у којој су везе између променљивих задате у виду неких ограничења. Разлика између језика ове парадигме и језика императивне парадигме је у томе што се не задају кораци који треба да се изврше, већ особине које треба да задовоље решења проблема. Ово чини програме парадигме ограничења једним обликом декларативне парадигме. Ограничења која се користе могу бити разних врста: она која се користе код испитивања задовољивости исказних формула (нпр. "A или B је тачно"), она која се решавају помоћу симплекс алгоритма и друга. Ограничења су обично уграђена у конкретан програмски језик или су доступна кроз разне софтверске библиотеке. Програмирање ограничења се може изразити у облику принудног логичког програмирања, које уграђује ограничења у логичко програмирање. За настанак ове варијанте логичког програмирања заслужни су Jaffar и Lassez, који су је 1987. проширили одређеном класом ограничења која је уведена у Prolog II. Прве имплементације принудног логичког програмирања биле су Prolog II, CLP(R), и CHIP. Уместо логичкоg програмирања, ограничења се могу се мешати са функционалним програмирањем, заменом термовима у логичким изразима и императивним језицима. Програмски језици са уграђеном подршком за ограничења укључују програмски језик Oz (функционално програмирање) и Kaleidoscope (императивно програмирање). Најчешће се ограничења спроводе у императивним језицима преко алата за решавање проблема ограничења, који су засебне библиотеке у датом програмском језику. Принудно логичко програмирањеПрограмирање ограничења је уградња ограничења на језику домаћина. Први језици домаћина који су коришћени су били језици логичке парадигме, тако да је ова област првобитно названа принудно логичко програмирање. Ове две парадигме имају многе важне функције, као што су логичке променљиве и бектрекинг. Данас већина имплементација Prolog-а укључује једну или више библиотека за принудно логичко програмирање. Разлика између њих је у великој мери у њиховим стиловима и приступу моделовању спољашњег света . Неке проблеме је природније (па тиме и једноставније ) описати као логичке програме, док је неке природно описати као програме ограничења. Приступ програмирању ограничења је потрага за стањем у спољашњем свету у којем велики број ограничења треба да буде задовољено у исто време . Проблем се обично наводи као стање света које садржи велики број непознатих променљивих. Програм ограничења тражи вредности за све променљиве. Временско конкурентно програмирање ограничења (ТCC) и недетерминистичко временско конкурентно програмирање (NTCC) су варијанте програмирања ограничења које се баве временом. Perturbation или прецизирање моделаЈезици за програмирање ограничења базирају се на једном од два приступа.[1]
Пропагирање ограничења у проблемима задовољивости исказних формула је типичан пример прецизирања модела, a табеларни приказ је најважнији пример модела пертурбације. Модел прецизирања је општији, пошто не ограничава пременљиве да имају једну вредност, па то може довести до неколико решења за исти проблем. Међутим, модел пертурбације је више интуитиван за програмере који користе мешавине императивних и објектно - оријентисаних језика са ограничењима.[2] ДомениОграничења која се користе у програмирању ограничења се обично тичу неких посебних области. Неки од популарних домена за програмирање ограничења су :
Коначни домени су једни од најкориснијих домена програмирања ограничења. У неким областима, као што су операциона истраживања, програмирање ограничења се често поистовећује са програмирањем ограничења преко коначних домена. Сви горенаведени примери се обично решавају SMT солверима. Решења коначних домена су корисна за решавање проблема задовољивости исказних формула, а често се заснивају на локалној доследности или некој од њених апроксимација. Синтакса за изражавање ограничења у коначним доменима зависи од језика домаћина. Следи Prolog програм који решава класичну аритметичку слагалицу са речима (SEND + MORE = MONEY) у контексту програмирања ограничења: Овај код се може користити и у YAP-у and SWI-Prolog-у користећи CLPFD библиотеку за ограничења. Може захтевати мање измене како би радио у другим Prolog окружењима.
sendmore(Digits) :- Digits = [S,E,N,D,M,O,R,Y], % Креира променљиве
Digits ins 0..9, % Додељује домене променљивим
S #\= 0, % Ограничење: S мора бити различито од 0
M #\= 0,
all_different(Digits), % сви елементи морају имати различите вредности
1000*S + 100*E + 10*N + D % Друга ограничења
+ 1000*M + 100*O + 10*R + E
#= 10000*M + 1000*O + 100*N + 10*E + Y,
label(Digits). % Започиње се претрага
</source> Преводилац ствара променљиву за свако слово у слагалици. Оператор Библиотеке програма ограничења за императивне програмске језикеПрограмирање ограничења се често реализује у императивним језицима путем посебних библиотека. Неке популарне библиотеке су:
Неки језици који подржавају програмирање ограничења
Референце
Литература
Спољашње везе
|
Portal di Ensiklopedia Dunia
