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

Orario

Programma Svolto

1. 21 Aprile 2008. 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. 22 Aprile 2008. Tecniche (note) per risolvere CSP e COP. Local search, (Integer) Linear Programming, e SAT. (LUCIDI)
3. 24 Aprile 2008. 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. 28 Aprile 2008. Bounds Consistency. Directional Arc/Bounds Consistency. Hyperarc (e Bounds) consistency. Path Consistency. K-consistency. Cenni ai vincoli globali. (LUCIDI)
5. 29 Aprile 2008. 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. 5 Maggio 2008. Richiami di Prolog. Alfabeti, termini, formule. Clausole definite e di Horn. SLD derivazioni e alberi SLD. Incompletezza di Prolog e completezza degli alberi. Ricerca con backtracking. Alcuni esempi di predicati extra logici.
7. 6 Maggio 2008. Lezione mutuata dal corso di dottorato Vincoli e NMR: CSP e metodi di risoluzione.
8. 8 Maggio 2008. Lezione mutuata dal corso di dottorato Vincoli e NMR: Overview del constraint programming.
9. 12 Maggio 2008. (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. Forma dei risultati e collezione degli stessi con predicati di secondo ordine.
10. 13 Maggio 2008. Metodologia constrain & generate in CLP. Codifica delle N-regine e della ricerca di codici di Hamming. Parametri del labeling. Eliminazione di simmetrie mediante vincoli lessicografici.
11. 15 Maggio 2008. Lezione in laboratorio. Codifica del sudoku.
12. 26 Maggio 2008. Esempi di CSP Modeling:
    • numeri di Schur,
    • knapsack,
    • circuito hamiltoniano e un grafo per testing,
    • protein folding semplificato.
    Per approfondire.
13. 27 Maggio 2008. 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
    
14. 29 Maggio 2008. 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. (LUCIDI)
15. 3 Giugno 2008. 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).
16. 4 Giugno 2008. Esercitazione in laboratorio. Applicazione delle tecniche della lezione precedente ai vari esempi gia' codificati nel corso (e in particolare a quello del rostering).
17. 5 Giugno 2008. Richiami della semantica osservazionale, modellistica e di punto fisso dei programmi definiti. Programmi generali. Principali problemi. La negazione in Prolog: CWA e NaF. (LUCIDI)
18. 9 Giugno 2008. Esempi e limiti della NaF. Implementazione con cut & fail. Completamento (regola di Herbrand) e relazioni tra le semantiche.
19. 10 Giugno 2008. Completamento di programmi generali. Cenni ai modelli del completamento e ai modelli well-founded. Modelli stabili. Definizione, primi esempi e NP-completezza del problema dell'esistenza di un modello stabile. (LUCIDI)
20. 11 Giugno 2008. Programmi e codici ASP. Tecniche di programmazione ASP. Uso di lparse e smodels. Cenni ai vari sat solver. (LUCIDI)
21. 12 Giugno 2008. Codifica di CSP con codici ASP. Alcuni esempi:
    • Marriage Problem.
    • Graph Coloring.
    • N-Queens.
    • Numeri Schur.
    • Hamilton Circuit.
    • Protein Folding.
    • La zebra evasa.
    • La capra e il cavolo.
22. 16 Giugno 2008. Linguaggi per il planning. Esempi di action theories. Soluzione usando ASP e CLP(FD) (LUCIDI) ( Per approfondire (codici, articoli, interpreti, esempi etc.)).
23. 17 Giugno 2008. Esempi di problemi espressi nel linguaggio B.
    • Le 3 botti
    • La capra e il cavolo
    • Un problema di auto
    • Un puzzle
    • Il mondo dei blocchi
24. 18 Giugno 2008. Esercitazione in laboratorio.