Laurea magistrale in Ingegneria e scienze informatiche

Ragionamento automatico

Codice insegnamento
4S02796
Docente
Maria Paola Bonacina
Coordinatore
Maria Paola Bonacina
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
I semestre dal 1-ott-2019 al 31-gen-2020.

Orario lezioni

Vai all'orario delle lezioni

Obiettivi formativi

Il corso si propone di fornire le seguenti conoscenze: a) metodi per la dimostrazione di teoremi e costruzione di modelli; b) sistemi di inferenza basati su ordinamenti (risoluzione), per generazione di istanze, basati su riduzione di sotto-goal (tableaux); c) piani di ricerca; d) procedure di decisione per la soddisfacibilità proposizionale (SAT) e modulo teorie (SMT). Al termine del corso la studentessa dovrà dimostrare di saper comprendere sistemi di inferenza, piani di ricerca, procedure di decisione, valutarne proprietà di correttezza, completezza ed efficienza, anche tramite implementazione di un prototipo. Queste conoscenze le consentiranno di usare ragionatori esistenti, svilupparne di nuovi, e sceglierne uno appropriato per un problema o applicazione. Alla fine del corso la studentessa sarà in grado di proseguire gli studi o sviluppare una tesi magistrale nell’ambito del ragionamento automatico e dell’intelligenza artificiale.

Programma

Fondamenti del ragionamento automatico: dimostrazione di teoremi e costruzione di modelli. Il problema della soddisfacibilità proposizionale (SAT): le procedure DPLL e CDCL. Il problema della validità in logica del primo ordine: sistemi di inferenza e piani di ricerca. Il teorema di Herbrand. Sistemi di inferenza per generazione di istanze: iper-nessi. Sistemi di inferenza basati su ordinamenti: risoluzione e paramodulazione/sovrapposizione. Sistemi di inferenza basati su riduzione di sotto-goal: eliminazione di modelli, tableaux. Piani di ricerca: algoritmo della clausola data; ricerca per profondità con approfondimento iterativo. Procedure di decisione per soddisfacibilità modulo teorie ed assegnamenti (SMT/SMA). Combinazione di teorie. Implementazione di un dimostratore o risolutore come progetto individuale.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Daniel Kroening, Ofer Strichman Decision Procedures. An algorithmic point of view Springer 2008 978-3-540-74104-6
John Harrison Handbook of Practical Logic and Automated Reasoning (Edizione 1) Cambridge University Press 2009 9780521899574
Chin-Liang Chang, Richard Char-Tung Lee Symbolic Logic and Mechanical Theorem Proving (Edizione 1) Academic Press 1973 0121703509
Aaron R. Bradley, Zohar Manna The Calculus of Computation - Decision Procedures with Applications to Verification (Edizione 1) Springer 2007 9783540741
Alexander Leitsch The Resolution Calculus (Edizione 1) Springer 1997 3540618821
Martin Davis The Universal Computer. The Road from Leibniz to Turing. Turing Centenary Edition. Taylor and Francis Group 2012 978-1-4665-0519-3

Modalità d'esame

I appello (mediante prove parziali) : il voto è dato da 25% PI + 25% PF + 50% P, dove PI è la Prova Intermedia, PF è la Prova Finale, e P è un progetto.
Appelli successivi: il voto è dato da 100% E, dove E è un unico compito scritto, di difficoltà tale da uguagliare l'unione delle prove parziali.
Frequentare il corso è fondamentale, tuttavia le modalità d'esame sono le stesse per chi frequenta e chi non frequenta.
Non è previsto il "rifiuto" del voto e tutti i voti saranno registrati. E' possibile ritirarsi informando la docente.





© 2002 - 2019  Università degli studi di Verona
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234