Programmazione a vincoli
Argomenti del corso:
- introduzione
- tecniche risolutive di ricerca:
backtracking, backjumping
backmarking, constraint
learning, bucket
elimination
- consistenza locale e propagazione di vincoli:
node consistency, arc consistency,
path consistency, hyperarc consistency, i-consistency,
directional
consistency,
relational
consistency
- look ahead
- local
search
- algoritmi ibridi
- ottimizzazione vincoli
- constraint logic
programming, concurrent constraint
logic programming, constraint handling rules
- complessità della
programmazione a vincoli; tipi di restrizioni; equivalenza
con il problema dell'omomorfismo; teoremi dicotomici;
condizioni sufficienti per la trattabilità;
condizione necessaria basata sul gadget universale
- problema duale; join graph e
join tree; metodi di decomposizione