Automated Deduction (2005/2006)

Learning outcomes

Il corso assume conoscenze di logica ed algoritmi quali quelle impartite dai corsi dei primi tre anni, e presenta problemi, metodi e sistemi di ragionamento automatico, combinando fondamenti teorici con questioni pratiche di natura algoritmico-implementativa, in modo da preparare lo studente a progettare, valutare ed applicare metodi e sistemi di ragionamento automatico.

la nozione di procedura di prova come combinazione di sistema di inferenza e piano di ricerca; il teorema di Herbrand; strategie basate sulla generazione di istanze: dal metodo di Gilmore alla combinazione di hyperlinking con l'algoritmo di Davis-Putnam-Logemann-Loveland; strategie basate sugli ordinamenti ben fondati: schemi di inferenza di espansione (risoluzione, paramodulazione, sovrapposizione) e di contrazione (sussunzione, riscrittura) e piani di ricerca per il ragionamento in avanti; strategie basate sulla riduzione di goals: risoluzione lineare, tableaux, eliminazione di modelli e piani di ricerca per il ragionamento all'indietro; progetto e uso di dimostratori di teoremi; cenni di costruzione di modelli; cenni sulle applicazioni del ragionamento automatico alla matematica e alla verifica.

per l'esame lo studente svolge un progetto e lo presenta in forma sia scritta che orale. Lo studente può scegliere tra un progetto pratico e un progetto teorico. Una lista di progetti tra cui scegliere sarà presentata a lezione. Un progetto pratico consiste nello studiare ed usare un sistema di ragionamento automatico (e.g., dimostratore di teoremi) allo stato dell'arte. Un progetto teorico consiste nello studiare un soggetto teorico non trattato a lezione. In entrambi i casi il progetto applica ed estende gli argomenti trattati nel corso. Lo studente che sceglie il progetto pratico dovrà scaricare il sistema dal suo sito web, compilarlo, imparare ad usarlo, ovvero capire come presentare un problema in ingresso e come interpretare il risultato in uscita, e valutarlo empiricamente. Per far questo studierà il manuale del sistema ed articoli apparsi in letteratura sul sistema stesso. Lo studente che sceglie il progetto teorico dovrà studiare una collezione di articoli sull'argomento. In entrambi i casi lo studente dovrà preparare una breve relazione scritta e dare una presentazione orale del suo soggetto. Il voto d'esame sarà determinato al 50% dalla relazione scritta e al 50% dalla presentazione orale.