Per le informazioni generali riguardanti il corso, consultare la pagina web mantenuta da Moggi. Qui di seguito si trovano informazioni, dispense etc. relative alle lezioni svolte da Palamidessi.

Programmazione Logica

Libri consigliati:

• "Programming Languages", di Ravi Sethi, Seconda edizione, pubblicato da Addison Wesley. Disponibile in biblioteca DISI-DIMA.
  E' disponibile anche la prima versione, tradotta in italiano e pubblicata dalla Zanichelli, ed e' abbastanza equivalente alla seconda per quanto riguarda la parte su Programmazione Logica.
• "The art of Prolog", di Leon Sterling e Ehud Shapiro, pubblicato da The MIT Press, disponibile in biblioteca DISI-DIMA.
• "From Logic Programming to Prolog", di Krzysztof Apt, pubblicato dalla Prentice Hall, disponibile in biblioteca DISI-DIMA.

Per le esercitazioni di laboratorio sul Prolog: E' disponibile sulle macchine Linux l'interprete Swi-Prolog, che si attiva col comando pl. Per il suo funzionamento vedi il Reference Manual di Jan Wielemaker Swi-Prolog.

• Lezione 1, 23/10/97. Introduzione alla programmazione logica. Sintassi e Semantica dichiarativa delle clausole di Horn. [dispense]
• Lezione 2, 24/10/97. Semantica operazionale della programmazione logica. Sostituzioni, unificatori, most general unifiers. Derivazioni di successo e di fallimento. [dispense]
• Lezione 3, 27/10/97. Teoremi di correttezza e completezza della semantica operazionale rispetto a quella dichiarativa. Esempio dell'albero genealogico. [dispense]
• Lezione 4, 28/10/97. Alberi di derivazione SLD. Strategia di ricerca del Prolog. [dispense]
• Lezione 5, 4/11/97. Liste in Prolog. Esempi di programmi su liste: append, occur, sublist, permutazioni, quicksort. Cenni di aritmetica Prolog. Conseguenze dell'uso di predicati extra-logici (come quelli aritmetici). Liste differenza. Definizione di append e reverse con liste differenza. [Materiale di consultazione: Sethi o Sterling-Shapiro]
• Lezione 6, 5/11/97. Negazione in Programmazione Logica. Closed Word Assumpion. Ragionamento non monotono. Problema della ineffettivita' della CWA. Negation As Failure. Correttezza della NAF rispetto alla CWA. Mancanza di Completezza della NAF rispetto alla CWA, dovuta ai problemi della non-terminazione e del "floundering". Ulteriore incompletezzza della NAF in Prolog a causa della regola di selezione unfair. [Materiale di consultazione: Sethi o Sterling-Shapiro]
• Lezione 7, 6/11/97. Negazione in Prolog. Uso della NAF su goal non ground. Esempio: Ricerca di cammini in un grafo, evitando i cicli. La direttiva "cut". Definizione del not e dell'if_then_else tramite il cut. Assert e retract. Cenni a tecniche di memoizzazione. [Materiale di consultazione: Sethi o Sterling-Shapiro]
• Lezione 8, 10/11/97. Torre di Hanoy e Fibonacci con tecniche di memoizzazione. Alcuni esempi dell'uso del Prolog per risolvere problemi di Intelligenza Artificiale: Analogy e State-space graphs. [Materiale di consultazione: Sterling-Shapiro. Dispense sul programma Analogy]
• Lezione 9, 11/11/97. Algoritmo di unificazione di Martelli-Montanari. Problema dell'occur check in Prolog. Il predicato findall. Esempio: ricerca di cammino di costo minimo. [Materiale di consultazione: Apt (paragrafo 2.6) per l'unificazione. Apt o Sterling-Shapiro per il problema dell'occur check e il findall]
• Lezione 10, 12/11/97. Metaprogrammazione in Prolog. Esempi: Metainterprete di base, metainterprete con regola di selezione rightmost, metainterprete che restituisce l'albero di derivazione SLD. [Materiale di consultazione: Sterling-Shapiro (paragrafo 17.2)]
• Lezione 11, 13/11/97. Metainterprete per gerarchie isa. Implementazione dell'Occurr check. [Materiale di consultazione: Dispense sul metainterprete per gerarchie isa, Sterling-Shapiro (paragrafo 10.2) per l'occur check]
• Lezione 12, 14/11/97. Controllo del nondeterminismo: dichiarazioni di Delay. [Dispense]
• Lezione 13, 17/11/97. Constraint Logic Programming (CLP). [Dispense]
• Lezione 14, 18/11/97. Cenni a tecniche di Constraint Solving. CLP con dichiarazioni di Delay. Introduzione a Concurrent Constraint Programming. [Dispense su Constraint Solving]
• Lezione 15, 19/11/97. Concurrent Constraint Programming. [Dispense: insieme a quelle della lezione 13]
• Lezione 16, 20/11/97. Esempio: Il processo merge in Concurrent Constraint Programming. Nondeterminismo dipendente dallo scheduling. Incompatibilita' del backtracking.

Programmazione Object-Oriented

Libro consigliato: "Programming Languages", di Ravi Sethi. Meglio la seconda edizione, pubblicata da Addison Wesley.
Il paradigma Object Oriented e' trattato nella parte terza (capitoli 6 e 7) della seconda edizione. Tale materiale si trova anche nella prima edizione (tradotta in italiano), ma e' organizzato meno bene.

• Lezione 1, 20/11/97. Introduzione alla programmazione object oriented. Gli oggetti come entita' contenenti sia componenti passive (lo stato), sia componenti attive (i metodi) e interagenti fra loro tramite scambio di messaggi (attivazione di metodi). Concetto di classe. Creazione di un oggetto.
• Lezione 2, 21/11/97. Concetto di sottoclasse, inheritance, overriding. Accenno al concetto di multiple inheritance (ma nel corso considereremo solo la single inheritance).
• Lezione 3, 24/11/97. Esempio: disegno di diagrammi in programmazione Object Oriented. Confronto con lo stile procedurale.
• Lezione 4, 25/11/97. Esempio: Aggiunta di figure complesse alla classe shape. Metodi che restituiscono valori e oggetti. Il concetto di self.
• Lezione 5, 26/11/97. Esempio: Generazione di numeri primi col metodo del Crivello di Eratostene. Metodo "demand driven" e metodo "data driven".
• Lezione 6, 27/11/97. Metodi e costruttori in C++. Restrizioni sull'uso di self (this). Cenni al concetto di thread.
• Lezione 7, 28/11/97. I threads in Java. Runnable objects. Esempio: il Crivello di Eratostene "parallelo" (metodo data driven). Information hiding in C++. Public, Private e Protected. Esempio: definizione di coda e pila come sottoclassi di lista.

Compitino

Attenzione: Gli interessati sono pregati di iscriversi, scrivendo il loro nome e cognome nell'apposito foglio appeso alla porta dell'aula 710.

Nei giorni 1, 2 e 4 dicembre, durante le ore di lezione, si svolgera' attivita' di preparazione al compitino. Cio' consistera' nello svolgimento di esercizi simili a quelli che verranno dati nel compitino. Si consiglia gli studenti interessati a cercare di svolgere per conto loro tali esercizi, prima di vedere lo svolgimento del docente.
Nota: Gli esercizi del gruppo (A) saranno svolti in classe il primo dicembre, quelli del gruppo (B) il 2 dicembre, e quelli del gruppo (C) il 4 dicembre.

I candidati che riportano un voto sufficiente possono decidere di far valere il compitino come parte integrante dell'esame finale del corso. In altre parole, il candidato che ha ottenuto un voto sufficiente, ed e' soddisfatto di tale voto, puo' chiedere di essere esonerato dallo svolgimento delle parti su Programmazione Logica sia allo scritto che all'orale dell'esame finale. Per tali parti varra' allora il voto del compitino (ovviamente normalizzato).

Note:
1) Per "voto sufficiente" si intende "almeno 18".
2) Durante il compitino e' permesso consultare testi e appunti.
3) Nel compitino ci saranno esercizi di programmazione e domande "di teoria", quali ad es.
- Dire qual'e' il minimo universo di Herbrand del programma P = ...
- Costruire l'albero SLD con regola di selezione rightmost per il goal G =...
- Il secondo teorema di completezza dice che ... . Esibire un esempio che mostri che in generale non si puo' ottenere proprio sigma come cas, ma solo una sostituzione piu' generale.
4) Gli esercizi e le domande potranno vertere su tutti gli argomenti trattati nelle lezioni 1-16 della parte di Programmazione Logica (quindi anche LP con delay, CLP, e CCP).
5) Oltre agli esercizi "normali", valevoli ai fini del voto, ci saranno uno o piu' esercizi "difficili". Questi ultimi non avranno valore ai fini del voto, ma solo ai fini dell'eventuale lode. In altre parole, il candidato puo', se vuole, provare a risolvere tali esercizi (naturalmente si consiglia di farlo solo dopo aver svolto gli altri). Se lo svolgimento di tali esercizi risultera' brillante, ne sara' tenuto conto al momento dell'esame finale per l'assegnazione dell'aventuale lode.

I candidati dovranno dichiarare al professor Moggi la loro decisione riguardo al valersi o meno del voto del compitino prima del sostenimento dell'esame finale.

Per commenti e suggerimenti su questa pagina si prega di scrivere a Catuscia Palamidessi: catuscia@disi.unige.it

Ultima modifica: 30 novembre 1997.