Linguaggi di Nuova Concezione, A.A. 2006/2007

Orario

LUN: 9:00-10:45 (44)
MAR: 13:15-15:00 (49 o lab bioinfo)
GIO: 9:00-10:45 (49)

Programma Svolto

  1. 19 Aprile 2007. Introduzione al corso.
  2. 23 Aprile 2007. Richiami di Programmazione in Prolog. Alfabeti, termini, formule. Clausole definite e di Horn. Esempi di programmi proposizionali e simil-DATALOG.
  3. 24 Aprile 2007. Principali predicati sulle liste. Turing completezza di Prolog. Unificatori, mgu, l'algoritmo di unificazione e il passo di SLD derivazione.
  4. 26 Aprile 2007. Alberi SLD e indipendenza dalle scelte non-deterministihce per la completezza. Ricerca con backtracking. Collezione delle soluzioni (manuale e con built-in). Cenni ai predicati aritmetici ed extralogici. Il cut.
  5. 3 Maggio 2007. Vincoli. Constraint Satisfaction Problems (CSP) e Constraint Optimization Problems (COP). Principali definizioni. Risolutori completi ed incompleti. Regole di risoluzione: domain reduction, transformation e introduction. Derivazioni e constraint propagation.
  6. 7 maggio 2007. Node consistency, Arc consistency, Bounds consistency, directional Arc e Bounds consistency, Hyperarc consistency. Procedure per la propagazione: AC1 e AC3.
  7. 8 Maggio 2007. Path consistency. Alberi di ricerca: prop labeling trees. Esempi ed effetti della scelta delle variabili sulle dimensioni degli alberi di ricerca.
  8. 10 Maggio 2007. Esercitazione in laboratorio sulla programmazione con vincoli in SICStus e in ECLIPSE. Primi programmi, differenze tra i due linguaggi, rilevamento di tempi, parametri del labeling.
  9. 14 Maggio 2007. Metodologia Generate & Test. Metodologia constrain & generate in CLP. Confronti su N-regine e coloring. La codifica del sudoku.
  10. 15 Maggio 2007. Programmazione logica con vincoli: procedura di risoluzione. Le funzioni simpl e solv. Codifica del Knapsack in CLPFD. COP, Branch & bound e confronti con la tecnica omonima (ma diversa) usata in ricerca operativa.
  11. 17 Maggio 2007. (lab) CLP(FD): esempi di programmazione con la metodologia constraint + generate: SEND+MORE=MONEY, Graph coloring, Numeri di Schur. (Per approfondire).
  12. 21 Maggio 2007. 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 Tecniche per il filtering di vincoli all_different.
  13. 22 Maggio 2007. Codifica di problemi di turni id lavoro in CLP(FD). In particolare, il problema del rostering ospedaliero. Cenni alla soluzione con tecniche miste di constraint programming e ricerca locale e al package GECODE. (intervento 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
  14. 24 Maggio 2007. Tecniche per la ricerca dell'ottimo in CLP(FD) usando labeling, ricerca bottom-up con timeout, limited discrepancy search, e ricerca locale. (Esempio)
  15. 28 Maggio 2007. Predizione di struttura: il problema del protein folding nel modello HP (codice). (Slides) Vincoli globali per problemi di orgine biologica (Per approfondire)
  16. 29 Maggio 2007. La ricerca locale. Spazio di ricerca, Vicinato, Funzione di costo. Metaeuristiche: hill climbing e varianti, Simulated Annealing e Tabu Search. (Lucidi a cura di Luca Di Gaspero)
  17. 31 Maggio 2007. Esercitazione in laboratorio.
  18. 4 Giugno 2007. Richiami della semantica osservazionale, modellistica e di punto fisso dei programmi definiti. Programmi generali. Principali problemi.
  19. 5 Giugno 2007. La negazione in Prolog: CWA, NaF, e (cenni) regola di Herbrand. Implementazione con cut & fail. Programmi e codici ASP.
  20. 7 Giugno 2007. Modelli minimali e modelli stabili. NP-completezza del problema dell'esistenza di un modello stabile.
  21. 11 Giugno 2007. Codifica di CSP con codici ASP. Alcuni esempi: Le N regine, Hamilton Path, K-coloring.
  22. 12 Giugno 2007. Altri esempi: Numeri di Schur, onesti e mentitori. Il problema della capra e del cavolo. Soluzione con ASP e CLP(FD).
  23. 14 Giugno 2007. Esercitazione in laboratorio. Uso di Smodels e Cmodels.
  24. 19 Giugno 2007. Linguaggi per il planning. Esempi di action theories. Soluzione usando ASP e CLP(FD) ( Per approfondire (codici, articoli etc.)).
Home Page