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

Orario lezioni

• Mar. IV fascia, aula 48
• Mer. II fascia, aula 48
• Ven. 14:00-16:00 in laboratorio.

Programma Svolto

1. 19 Aprile 2005. Introduzione al corso. Sintassi e Semantica della logica del prim'ordine. Richiami alle interpretazioni di Herbrand. Programmi con clausole definite. Fatti, regole e goals. Quantificatori nelle regole.
2. 20 Aprile 2005. Esempi di programmi proposizionali, con dominio finito, con dominio infinito. Turing completezza (e incompletezza).
3. 22 Aprile 2005. Esercitazione sugli esempi visti la lezione precedente.
4. 26 Aprile 2005. Sostituzioni. Preordine tra queste. Varianti. Unificatori e mgu. Il problema dell'Unificazione. L'algoritmo di unificazione alla Herbrand. Correttezza, completezza e non-determinismo. Buoni ordini (lessicografico-multiset) e terminazione.
5. 26 Aprile 2005. Complessità dell'algoritmo di Unificazione e sue principali implementazioni. Significato logico dell'unificazione. E-unificazione: esempi di base. E-unificazione. Definizioni e problemi principali.
6. 3 Maggio 2005. ACI con costanti e generale: limiti di complessità. Problema: la terminazione dell'algoritmo di unificazione per liste compatte. SLD Risoluzione
7. 4 Maggio 2005. Alberi di derivazione SLD. Indipendenza dalla scelta non-deterministiche. Il backtracking. Incompletezza di Prolog. Cut e Fail. Ripasso sulla semantica logica e denotazionale di prolog e loro equivalenza con la semantica operazionale.
8. 6 Maggio 2005 (lab). Utilizzo del SICStus Prolog. Predicati su liste e grafi. Visite di grafi. Permutazioni di una lista. Ordinamento di una lista. Alcuni esempi.
9. 10 Maggio 2005. Alcuni predicati extra-logici di Prolog. Programmazione dichiarativa. Metodologia Generate & Test. Esempi di programmazione dichiarativa e ottimizzazione dello spazio di ricerca. Le N-regine.
10. 11 Maggio 2005. Ottimizzazione delle N regine. Il problema delle M-N regine. Il map coloring. Il TSP. Il problema dei numeri di Schur.
11. 13 Maggio 2005 (lab). Esercitazione sulla soluzione generate & test dei problemi NP della lezione precedente. Verifica dei tempi di esecuzione. Un sito inetessante dove reperire dati per i problemi: CLPASP.
12. 17 Maggio 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.
13. 18 Maggio 2005. Derivazioni e constraint propagation. Node consistency, Arc consistency, Bounds consistency, directional Arc consistency, Hyperarc consistency.
14. 20 Maggio 2005. Path consistency, k-consistency. Alberi di ricerca: prop labeling trees.
15. 24 Maggio 2005. 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: Branch and Bound con constraints. Dispense relative a questa parte. Programmazione logica con vincoli: procedura di risoluzione.
16. 25 Maggio 2005. Il risolutore clpfd di SICStus: parametri del labeling. CLP(FD): esempi di programmazione con la metodologia constraint + generate:
    • N-regine
    • SEND+MORE=MONEY
    • Graph coloring
    • Hamilton Path
    • Numeri di Schur
    • Protein Folding.
17. 27 Maggio 2005. Esercitazione su programmazione constrain + generate.
18. 31 Maggio 2005. Programmi generali. Principali problemi. SLDNF e sua implementazione con cut e fail. Modelli minimali e modelli stabili. Esempi.
19. 1 Giugno 2005. Esempi di programmi e vincoli ASP. NP-completezza del problema di stabilire se un programma ASP con vincoli ammetta un modello stabile. Esempi di programmazione con ASP: Le N regine.
20. 3 Giugno 2005. Uso di Smodels e Cmodels. Implementazione di N-regine, Hamilton Path, e k-coloring. Si veda anche:
    • A. Dovier, A. Formisano, and E. Pontelli.
      A comparison of CLP(FD) and ASP solutions to NP-complete problems
      CILC 2005: Convegno Italiano di Logica Computazionale. 21--22 giugno 2005, Roma.
21. 7 Giugno 2005. Ottimizzazione di programmi ASP e discussione. I numeri di Schur. Planning: generalità e risoluzione del problema della capra e del cavolo in asp e in clpfd).
22. 8 Giugno 2005. Presentazione di alcune tematiche di ricerca sviluppate o attive in area CLP. Valutazione del corso.
23. 15 Giugno 2005. Introduzione alla programmazione logica concorrente: CCP. Gli operatori ASK e TELL. Il linguaggio di coordinamento LINDA.
24. 17 Giugno 2005. Esercitazione su vari argomenti in vista dell'esame.