Corso di Sistemi con Vincoli

A. A. 2010/2011

Laurea Magistrale in Informatica, Universita' di Padova

Docente: Francesca Rossi

• Introduzione al corso, esempi di problemi di vincoli.
• Nozioni di base della programmazione con vincoli.
• Alcuni risolutori completi.
• Nozioni di consistenza locale.
• Alcuni risolutori incompleti.
• Algoritmi di propagazione di vincoli.
• Metodi di ricerca nello spazio delle soluzioni.
• Argomenti avanzati di programmazione con vincoli:
  • vincoli soft
  • vincoli bipolari
  • vincoli con incertezza
  • preferenze condizionali

Altri libri di riferimento:

• Constraint processing, R. Dechter, Morgan Kaufmann, 2003.
• Handbook of Constraint Programming, F. Rossi, P. Van Beek, T. Walsh, editors, Elsevier, 2006.
• Constraint networks: Techniques and Algorithms, C. Lecoutre, Wiley, 2009.

• Introduzione (capitolo 1)
• Esempi di problemi con vincoli (capitolo 2)
• L'idea della programmazione con vincoli (capitolo 3)
• Alcuni risolutori completi (capitolo 4)
• Nozioni di consistenza locale (capitolo 5)
• Alcuni esempi di risolutori incompleti (capitolo 6)
• Algoritmi di propagazione di vincoli (capitolo 7)
• Algoritmi AC1, AC3, AC4, AC2001, PC1, PC2
• Altre nozioni di consistenza locale
• Problemi generati casualmente e transizione di fase
• Algoritmi di ricerca di una soluzione (capitolo 8)
• Preferenze: vincoli soft e CP-net
• Linee guida per i progetti

• sulla implementazione di risolutori: articolo "Finite domain constraint programming systems" di Christian Schulte e Mats Carlsson
• sul vincolo globale "all-different": articolo "The alldifferent constraint: a survey" di W.-J. van Hoeve
• sulla propagazione con vincoli: articolo di Christian Bessiere che descrive in modo preciso vari algoritmi di propagazione di vincoli
• sui vincoli soft:
  • articolo sulle basi algebriche dei vincoli soft
• sulla risoluzione di problemi di vincoli:
  • un survey di Vipin Kumar sugli algoritmi per la propagazione e soluzione dei problemi di vincoli, apparso su AI Magazine Vol.13, n.1, 1992 ( kumar.ps ).
    Semplice e ben organizzato, chiarisce i concetti e il ruolo della propagazione di vincoli nella ricerca della soluzione di un problema di vincoli, mettendo in evidenza i compromessi da considerare.

  • un capitolo di David McAllester sulle euristiche per risolvere problemi di vincoli ( dmac.ps ).
    Meno standard di quello di Vipin Kumar, leggerlo solo dopo, per un punto di vista alternativo alle tecniche di propagazione di vincoli.

• sulla programmazione con vincoli:
  • un articolo di Dick Pountain sulla programmazione logica con vincoli, apparso su BYTE Magazine nel Febbraio 1995.
    Breve articolo non tecnico che da' l'idea dei principali vantaggi della programmazione logica con vincoli sulla programmazione logica.

  • un survey pubblicato dall'ACM sulla programmazione con vincoli, apparso su ACM Computing Surveys vol.28, n.4, 1996 ( survey.ps ).
    Scritto a piu' mani dai principali esperti del campo, da' un'idea abbastanza completa e non tecnica dei concetti fondamentali della programmazione con vincoli e delle sue applicazioni.

Nota: nell'orario ci sono 8 ore di lezione ogni settimana, mentre per avere 48 ore di lezione in totale ne servirebbero solo 6. Il motivo e' che molte lezioni non verranno tenute per vacanze accademiche o impegni del docente. Le lezioni che saranno tenute sono:

• 11, 12, 18, 19, 20, 21, 28 Aprile
• 2, 9 (3 ore), 11, 12, 16 (3 ore), 17, 18, 19, 23 (3 ore) Maggio
• 6 (3 ore), 7, 8, 9, 14, 15 Giugno

• Le lezioni di Lunedi' 9, Lunedi' 16, Lunedi' 23 Maggio, Lunedi' 6 Giugno dureranno 3 ore (14:30-17:30). Questo permette di annullare le lezioni di Martedi' 10 e Martedi' 24 Maggio (per le quali ci sono problemi di sovrapposizione con altri corsi).
• Le ultime 4 lezioni saranno dedicate alla discussione dei progetti.

Appelli: due a fine corso, due a Settembre, uno a Dicembre.

• primo appello: scritto 20 Giugno 1BC45 10:00, orale 27 Giugno 1BC45 10:00
• secondo appello: scritto 4 Luglio 1BC45 15:00, orale 11 Luglio 1BC45 10:00
• terzo appello: scritto 6 Settembre 1BC50 15:00, orale su appuntamento
• quarto appello: scritto 20 Settembre 1BC45 15:00, orale su appuntamento

• Esempi di compiti d'esame (1, 2, 3, 4).

Gruppi e argomenti per il progetto:

• Gruppo 1: Mattia Gamba, Stefano Grasselli.
  Metodo dei tagli per vincoli fuzzy, con backtracking con o senza propagazione per vincoli classici
• Gruppo 2: Deborah Rizzi, Alessandro Daniele.
  Algoritmi di propagazione di vincoli e ricerca per il problema del Sudoku (presentazione progetto).
• Gruppo 3: Virgulin Marco, Turato Daniele.
  Ricerca con backtracking con FC o con AC, e confronto tra i tempi e il numero di nodi visitati
• Gruppo 4: Mirko Polato, Stefano Bonetta
  Creazione di una libreria Java per: wizard per la creazione di CP-net; risoluzione di CP-net acicliche; risoluzione di CP-net cicliche. Con risoluzione si intende la possibilita' di restituire: la/le soluzioni ottime; l'ordine parziale delle soluzioni; confronto tra soluzioni.