Linguaggi di Nuova Concezione, A.A. 2008/2009

Orario

Programma Svolto

1. 2 Marzo 2009. Introduzione al corso. CSP/COP e loro sostanziale equivalenza. NP hardness di semplici CSP. Spazio e alberi di ricerca. Tecniche naive di ricerca. (LUCIDI)
2. 6 Marzo 2009. Tecniche (note) per risolvere CSP e COP. Local search, (Integer) Linear Programming, e SAT. (LUCIDI)
3. 13 Marzo 2009. Constraint Solver. Risolutori completi ed incompleti. Regole di risoluzione: domain reduction, transformation e introduction. Derivazioni e constraint propagation. Node consistency, e Arc consistency. (LUCIDI)
4. 16 Marzo 2009. Bounds Consistency. Directional Arc/Bounds Consistency. Hyperarc (e Bounds) consistency. Path Consistency. K-consistency. Cenni ai vincoli globali. (LUCIDI)
5. 20 Marzo 2009. Alberi di ricerca: prop labeling trees. Esempi ed effetti della scelta delle variabili sulle dimensioni degli alberi di ricerca. Constraint Programming (vari formalismi). (LUCIDI)
6. 23 Marzo 2009. Richiami di Prolog. Alfabeti, termini, formule. Clausole definite e di Horn. SLD derivazioni e unificazione.
7. 27 Marzo 2009. Lezione in laboratorio.
8. 30 Marzo 2009. Alberi SLD. Incompletezza di Prolog e completezza degli alberi. Ricerca con backtracking. Alcuni esempi di predicati extra logici. Predicati di secondo ordine. Primi cenni alla negazione in Prolog.
9. 03 Aprile 2009. (LUCIDI) Constraint Logic Programming. Stati. Stati di fallimento e di succeso. Regola di derivazione. Le funzioni simpl e solv. Embedding nella SLD risoluzione. Uso della libreria clpfd di SICStus Prolog. Metodologia constrain & generate in CLP. Codifica delle N-regine e dello knapsack.
10. 6 Aprile 2009. Esempi di CSP Modeling:
    • numeri di Schur,
    • codici di Hamming.
    Cenni all'eliminazione delle simmetrie mediante vincoli lessicografici.
11. 10 Aprile 2009. Codifica del
    • sudoku.
    • protein folding semplificato.
    Per approfondire.
12. 20 Aprile 2009. Codifica del problema del circuito hamiltoniano e un grafo per testing. Tecniche per la ricerca dell'ottimo in CLP(FD) usando labeling, ricerca bottom-up con timeout, e ricerca locale. (Esempio per SICStus 3, Esempio per SICStus 4, LUCIDI).
13. 27 Aprile 2009. Applciazione delle tre tecniche su un semplice esempio e sul problema del protein folding. 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. (LUCIDI)
14. 4 Maggio 2009. Tecniche per il filtering di vincoli all_different. Richiami della semantica osservazionale, modellistica e di punto fisso dei programmi definiti. Programmi generali. Principali problemi.
15. 8 Maggio 2009. La negazione in Prolog: CWA e NaF. (LUCIDI) Esempi e limiti della NaF. Implementazione con cut & fail. Completamento (regola di Herbrand) e relazioni tra le semantiche. Grounding e loro dimensione. Completamento di programmi generali. Cenni ai modelli del completamento e ai modelli well-founded.
16. 11 Maggio 2009. Esercitazione in laboratorio: modeling in CLP di un problema di rostering ospedaliero. Analisi di tre codifiche. Specifiche esercizio, Dati di input Per approfondire: lucidi Raffaele Cipriano e un lavoro:
    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
    
17. 15 Maggio 2009. Modelli stabili. Definizione, primi esempi e NP-completezza del problema dell'esistenza di un modello stabile. (LUCIDI) Uso di lparse e smodels su semplici esempi.
18. 18 Maggio 2009. Programmi e codici ASP. Tecniche di programmazione ASP. (LUCIDI) Codifica di CSP con codici ASP. Alcuni esempi:
    • Graph Coloring.
    • N-Queens.
19. 22 Maggio 2009.
    • Numeri Schur.
    • Hamilton Circuit.
    • Protein Folding.
    • La zebra evasa.
    • La capra e il cavolo.
20. 25 Maggio 2009. Cenni al funzionamento dei solver per answer set programming. Il solver GASP
    
21. 29 Maggio 2009. Esercitazione in laboratorio: codifica del problema della torre di Hanoi in ASP (Esempio)
22. 1 Giugno 2009. Linguaggi per il planning. Esempi di action theories. Soluzione usando ASP e CLP(FD) (LUCIDI) ( Per approfondire (codici, articoli, interpreti, esempi etc.)).
23. 5 Giugno 2009. Seminario di Schwartz Russell.
24. 8 Giugno 2009. Esempi di problemi espressi nel linguaggio B.
    • La capra e il cavolo
    • Le tre botti
    • Un puzzle
    • Il solitario Peg
    • La torre di Hanoi
    Un Traduttore da B ad ASP e un interprete CLP(FD) del B
25. 12 Giugno 2009. Esercitazione in laboratorio, assegnamenti per l'esame.