Sistemi con vincoliSistemi con vincoli

Francesca RossiFrancesca Rossi

Aprile-Giugno 2006Aprile-Giugno 2006

Scopo del corsoScopo del corso

Dare le nozioni di base della Dare le nozioni di base della programmazione con vincoliprogrammazione con vincoli

Come rappresentare un problema Come rappresentare un problema reale con un insieme di vincolireale con un insieme di vincoli

Tecniche principali per risolverloTecniche principali per risolverlo Approccio formale per un tipo di Approccio formale per un tipo di

programmzione con molte programmzione con molte applicazioni praticheapplicazioni pratiche• Non e’ un corso di programmazione!Non e’ un corso di programmazione!

Struttura del corsoStruttura del corso Lezioni: Martedi’, Mercoledi’, Giovedi’ 9:30-11:10Lezioni: Martedi’, Mercoledi’, Giovedi’ 9:30-11:10 Aula TA50BAula TA50B Lezioni ed esercizi in aulaLezioni ed esercizi in aula Materiale: Materiale:

• libro “Principles of Constraint Programming”, K. Apt, libro “Principles of Constraint Programming”, K. Apt, Cambridge University Press, 2003Cambridge University Press, 2003

• Libreria Progetto, 48 euro (nel 2005)Libreria Progetto, 48 euro (nel 2005)• Lucidi associati al libro, disponibili sul sito del corso Lucidi associati al libro, disponibili sul sito del corso

(www.math.unipd.it/~frossi/vincoli2006.html)(www.math.unipd.it/~frossi/vincoli2006.html) Altro materiale sul sito del corsoAltro materiale sul sito del corso Anche parti dal libro “Constraint processing”, R. Anche parti dal libro “Constraint processing”, R.

Dechter, Morgan Kauffman, 2003Dechter, Morgan Kauffman, 2003 Esame: scritto + progetto e sua discussioneEsame: scritto + progetto e sua discussione

Corso integrativoCorso integrativo

10 ore, in piu’ rispetto al corso10 ore, in piu’ rispetto al corso FacoltativoFacoltativo Docente: Toby Walsh, Univ. New Docente: Toby Walsh, Univ. New

South Wales (Sydney, Australia)South Wales (Sydney, Australia) Titolo e programma: definiti tra pocoTitolo e programma: definiti tra poco Periodo: inizio GiugnoPeriodo: inizio Giugno

Programmazione con vincoliProgrammazione con vincoli

Approccio alternativo alla programmazioneApproccio alternativo alla programmazione Vincolo su una sequenza di variabili: Vincolo su una sequenza di variabili:

relazione sui loro dominirelazione sui loro domini Problema di soddisfazione di vincoli (CSP): Problema di soddisfazione di vincoli (CSP):

insieme finito di vincoliinsieme finito di vincoli Approccio della programmazione con Approccio della programmazione con

vincoli:vincoli:• Formulare un problema come un CSPFormulare un problema come un CSP• Risolvere la rappresentazione scelta con Risolvere la rappresentazione scelta con

metodi generali o specificimetodi generali o specifici

Risolvere un CSPRisolvere un CSP

Determinare se ha una soluzione Determinare se ha una soluzione (cioe’ se e’ consistente)(cioe’ se e’ consistente)

Trovare una soluzioneTrovare una soluzione Trovare tutte le soluzioniTrovare tutte le soluzioni Trovare una soluzione ottimaTrovare una soluzione ottima Trovare tutte le soluzioni ottimeTrovare tutte le soluzioni ottime

Metodi specificiMetodi specifici

Algoritmi specifici per certe classi di Algoritmi specifici per certe classi di vincoli (risolutori)vincoli (risolutori)

Esempi:Esempi:• Un programma per risolvere sistemi di Un programma per risolvere sistemi di

equazioni lineariequazioni lineari• Un pacchetto software per la Un pacchetto software per la

programmazione lineareprogrammazione lineare• Un’implementazione dell’algoritmo di Un’implementazione dell’algoritmo di

unificazioneunificazione

Metodi generaliMetodi generali

Algoritmi per la propagazione di Algoritmi per la propagazione di vincolivincoli

Metodi di ricerca nello spazio delle Metodi di ricerca nello spazio delle soluzionisoluzioni

Caratteristiche di base della Caratteristiche di base della programmazione con vincoliprogrammazione con vincoli

Programmazione in due fasi:Programmazione in due fasi:• Generazione della rappresentazione di Generazione della rappresentazione di

un problema come CSPun problema come CSP• Sua soluzioneSua soluzione

Rappresentazione flessibile: i vincoli Rappresentazione flessibile: i vincoli possono essere aggiunti, tolti, o possono essere aggiunti, tolti, o modificatimodificati

ApplicazioniApplicazioni Sistemi grafici interattivi (per esprimere la coerenza Sistemi grafici interattivi (per esprimere la coerenza

geometrica)geometrica) Problemi di ricerca operativa (vari problemi di Problemi di ricerca operativa (vari problemi di

ottimizzazione)ottimizzazione) Biologia molecolare (sequenzializzazione del DNA, Biologia molecolare (sequenzializzazione del DNA,

costruzione di modelli 3D delle proteine)costruzione di modelli 3D delle proteine) Applicazioni finanziarie Applicazioni finanziarie Verifica circuitiVerifica circuiti Elaborazione del linguaggio naturale (costuzione di pareser Elaborazione del linguaggio naturale (costuzione di pareser

efficienti)efficienti) Schedulazione di attivita’ di satellitiSchedulazione di attivita’ di satelliti Generazione di programmi musicali radiofonici coerentiGenerazione di programmi musicali radiofonici coerenti ......

Sommario del corsoSommario del corso

Esempi di problemi di soddisfazione di Esempi di problemi di soddisfazione di vincolivincoli

Nozioni di base della programmazione con Nozioni di base della programmazione con vincolivincoli

Alcuni risolutori completiAlcuni risolutori completi Nozioni di consistenza localeNozioni di consistenza locale Alcuni risolutori incompletiAlcuni risolutori incompleti Algoritmi di propagazione di vincoliAlgoritmi di propagazione di vincoli Ricerca nello spazio delle soluzioniRicerca nello spazio delle soluzioni