Sistemi con vincoli

Sistemi con vincoli
Francesca Rossi
Aprile-Giugno 2006
Scopo del corso




Dare le nozioni di base della
programmazione con vincoli
Come rappresentare un problema
reale con un insieme di vincoli
Tecniche principali per risolverlo
Approccio formale per un tipo di
programmzione con molte
applicazioni pratiche
• Non e’ un corso di programmazione!
Struttura del corso




Lezioni: Martedi’, Mercoledi’, Giovedi’ 9:30-11:10
Aula TA50B
Lezioni ed esercizi in aula
Materiale:
• libro “Principles of Constraint Programming”, K. Apt,
Cambridge University Press, 2003
• Libreria Progetto, 48 euro (nel 2005)
• Lucidi associati al libro, disponibili sul sito del corso
(www.math.unipd.it/~frossi/vincoli2006.html)



Altro materiale sul sito del corso
Anche parti dal libro “Constraint processing”, R.
Dechter, Morgan Kauffman, 2003
Esame: scritto + progetto e sua discussione
Corso integrativo





10 ore, in piu’ rispetto al corso
Facoltativo
Docente: Toby Walsh, Univ. New
South Wales (Sydney, Australia)
Titolo e programma: definiti tra poco
Periodo: inizio Giugno
Programmazione con vincoli




Approccio alternativo alla programmazione
Vincolo su una sequenza di variabili:
relazione sui loro domini
Problema di soddisfazione di vincoli (CSP):
insieme finito di vincoli
Approccio della programmazione con
vincoli:
• Formulare un problema come un CSP
• Risolvere la rappresentazione scelta con
metodi generali o specifici
Risolvere un CSP





Determinare se ha una soluzione
(cioe’ se e’ consistente)
Trovare una soluzione
Trovare tutte le soluzioni
Trovare una soluzione ottima
Trovare tutte le soluzioni ottime
Metodi specifici


Algoritmi specifici per certe classi di
vincoli (risolutori)
Esempi:
• Un programma per risolvere sistemi di
equazioni lineari
• Un pacchetto software per la
programmazione lineare
• Un’implementazione dell’algoritmo di
unificazione
Metodi generali


Algoritmi per la propagazione di
vincoli
Metodi di ricerca nello spazio delle
soluzioni
Caratteristiche di base della
programmazione con vincoli

Programmazione in due fasi:
• Generazione della rappresentazione di
un problema come CSP
• Sua soluzione

Rappresentazione flessibile: i vincoli
possono essere aggiunti, tolti, o
modificati
Applicazioni









Sistemi grafici interattivi (per esprimere la coerenza
geometrica)
Problemi di ricerca operativa (vari problemi di
ottimizzazione)
Biologia molecolare (sequenzializzazione del DNA,
costruzione di modelli 3D delle proteine)
Applicazioni finanziarie
Verifica circuiti
Elaborazione del linguaggio naturale (costuzione di pareser
efficienti)
Schedulazione di attivita’ di satelliti
Generazione di programmi musicali radiofonici coerenti
...
Sommario del corso







Esempi di problemi di soddisfazione di
vincoli
Nozioni di base della programmazione con
vincoli
Alcuni risolutori completi
Nozioni di consistenza locale
Alcuni risolutori incompleti
Algoritmi di propagazione di vincoli
Ricerca nello spazio delle soluzioni