Linguaggi di Nuova Concezione, A.A. 2003/2004

Orario lezioni

Programma Svolto

  1. 19 Aprile 2006. Introduzione al corso.
  2. 20 Aprile 2005. Vincoli. Constraint Satisfaction Problems (CSP) e Constraint Optimization Problems (COP). Principali definizioni. Risolutori completi ed incompleti. Regole di risoluzione: domain reduction, transformation e introduction.
  3. 26 Aprile 2006. Derivazioni e constraint propagation. Node consistency, Arc consistency, Bounds consistency, directional Arc consistency, Hyperarc consistency.
  4. 27 Aprile Maggio 2005. Path consistency, k-consistency. Procedure per la propagazione: AC1 e AC3.
  5. 3 Maggio 2006. Alberi di ricerca: prop labeling trees. Esempi ed effetti della scelta delle variabili sulle dimensioni degli alberi di ricerca. Metodi di propagazione: forward checking, partial e full look ahead (MAC). Algoritmi di costruzione/visita di alberi di ricerca:
  6. 4 Maggio 2006. Dal Logic Programming al constraint di logic programming. Richiami sui programmi definiti e relativa procedura di risoluzione.
  7. 8 Maggio 2006. Programmazione logica con vincoli: procedura di risoluzione. Le funzioni simpl e solv. Il backtracking.
  8. 10 Maggio 2006. Programmazione dichiarativa. Metodologia Generate & Test. Esempi di programmazione dichiarativa e ottimizzazione dello spazio di ricerca. Metodologia constrain & generate in CLP. Le N-regine.
  9. 11 Maggio 2006. Esercitazione in laboratorio sulla programmazione con vincoli. Le N-regine, il Sudoku ed altri problemi.
  10. 15 Maggio 2006. Approfondimenti circa gli alberi SLD (1) e i prop-labeling trees (2). (1) Primitive di secondo ordine di Prolog (findall, bagof, setof). Cut e fail. Uso del cut e fail per implementare la negazione.
  11. 16 Maggio 2006. (2) Opzioni per il labeling. Branch & bound e confronti con la tecnica omonima (ma diversa) usata in ricerca operativa.
  12. 17 Maggio 2006. (lab) CLP(FD): esempi di programmazione con la metodologia constraint + generate: Sito dove reperire dati per i problemi: CLPASP. Per approfondire:
    A. Dovier, A. Formisano, E. Pontelli.
    A comparison of CLP(FD) and ASP solutions to NP-complete problems.
    In M. Gabbrielli and G. gupta eds., Proc of ICLP 2005. LNCS 3668, pp. 67-82. Sitges, barcelona, October 2005.
  13. 22 Maggio 2006. Introduzione ai vincoli globali. Vincoli di all_different. Richiami sulle tecniche di risoluzione al problema di ricerca di un matching massimale in un grafo bipartito (Note).
  14. 24 Maggio 2006. Tecniche per il filtering di vincoli all_different. Cenni a CLP(Q/R). Predizione di struttura: il problema del protein folding nel modello HP (codice)
  15. 25 Maggio 2006. Aritmetica degli intervalli. Vincoli su intervalli e locate in Eclipse. Applicazioni del constraint programming al riconoscimento di immagini (seminario di Michela Farenzena). Si veda anche;
    M. Farenzena, A. Fusiello, and A. Dovier.
    Reconstruction with Interval Constraints Propagation
    In Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition New York, NY: June 17-22, 2006.
  16. 31 Maggio 2006. Concurrent Constraint Programming. Sistemi di vincoli e ASK & Tell. Semantica operazionale e esempi. Il linguaggio di coordinamento Linda ed il suo utilizzo in SICStus Prolog.
  17. 1 Giugno 2006. Programmazione con agenti (si veda anche: An Introduction to Multiagent System by M. Wooldridge). Un'applicazione della programmazione multiagente al problema del protein folding.
  18. 5 Giugno 2006. Richiami della semantica modellistica e di punto fisso dei programmi definiti. Programmi generali. Principali problemi. Modelli minimali e modelli stabili. NP-completezza del problema dell'esistenza di un modello stabile.
  19. 7 Giugno 2006. Soluzione del problema del rostering ospedaliero con tecniche di constraint programming e ricerca locale (seminario di Raffaele Cipriano). Per approfondire:
    R. Cipriano, L. Di Gaspero, and A. Dovier.
    Approcci ibridi al problema del rostering: un caso di studio nell'integrazione di programmazione con vincoli e ricerca locale
    In RCRA 2006.
  20. 8 Giugno 2006. Vincoli ASP. Esempi di programmi e codici ASP. Esempi di programmazione con ASP: Le N regine, Hamilton Path, K-coloring, Numeri di Schur.
  21. 14 Giugno 2006. Idee e uso di Smodels e Cmodels. Programmi tight.
  22. 15 Giugno 2006. Linguaggi per il planning. Esempi di action theories. Soluzione usando ASP e CLP(FD). Per approfondire:
    A. Dovier, A. Formisano, and E. Pontelli.
    Planning with Action Languages: Perspectives using CLP(FD) and ASP
    In Proc. of CILC 2006: convegno italiano di logica computazionale, Bari, 26-27 giugno 2006.
  23. 19 Giugno 2006 (2 ore + 2 ore di lab). L'algoritmo di unificazione. Complessità dell'algoritmo di Unificazione e sue principali implementazioni. Significato logico dell'unificazione. E-unificazione: Definizioni e problemi principali. Problema: la terminazione dell'algoritmo di unificazione per le liste compatte. Esercitazione su ASP. Indicazioni sull'esame e valutazione del corso.
Home Page