Programovani s omezujicimi podminkami predstavuje
stale se rozsirujici technologii pro deklarativni popis a efektivni reseni slozitych problemu predevsim kombinatorickeho
razu. Vyzkum omezujicich podminek spojuje vedce z cele rady oblasti jako je umela inteligence, programovaci jazyky,
operacni vyzkum, symbolicke vypocty a vypoctova logika.
Omezujici podminky nalezly siroke uplatneni
v rade praktickych aplikaci. Nejcastejsi aplikace pochazeji ze sfery pocitacove grafiky, zpracovani prirozeneho
jazyka, databazovych systemu, molekularni biologie a navrhu plosnych spoju.Klicovou oblasti pouziti je potom planovani,
rozvrhovani a obecne optimalizacni ulohy.
Anotace
Prednaska podava prehled o technikach
programovani s omezujicimi podminkami. Zamerena je na algoritmy splnovani podminek a na problematiku reseni prilis
omezenych systemu podminek. Zabyva se take praktickym vyuzitim omezujicich podminek pri reseni realnych problemu.
Osnova
Uvod: historicke souvislosti, vazba
na dalsi obory, prakticke vyuziti.
Zakladni algoritmy splnovani podminek
(generuj a testuj, prohledavani s navracenim, dopredna kontrola, lookahead), binarizace podminek, hranova konzistence,
konzistence po ceste.
Pokrocile techniky a pouziti heuristik
(simulovane zihani, min-conflicts, random-walk, tabu search, GSAT).
Analyza algoritmu a benchmarks.
Prilis omezene systemy podminek a jejich
reseni: FCSP, WCSP, Prob-CSP, PCSP, hierarchie podminek, algoritmy reseni hierarchii, mezi-hierarchicke porovnani.
Modelovani a vyuziti v realnych aplikacich.
Základní literatura
R. Bartak: Expertni systemy zalozene
na omezujicich podminkach, Disertacni prace, MFF UK, 1997
J. Jaffar, M.J. Maher: Constraint Logic
Programming: A Survey, in: Journal of Logic Programming, 1994, vol. 19/20. pp. 503 - 581
E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993
P. Van Hentenryck: Constraint Satisfaction in Logic Programming, Logic Programming Series, The MIT Press, 1989
K Marriott, P.J. Stuckey: Programming with Constraints, The MIT Press, 1988
