Computer Science - Informatica

LORENZO CARLUCCI
GIUSEPPE PERELLI

Obiettivi generali:
Il corso ha l'obiettivo di introdurre gli studenti ai risultati e ai metodi fondamentali della Logica Matematica con particolare attenzione alla loro applicazione nell'ambito dell'Informatica.

Obiettivi specifici:
L'obiettivo del corso è duplice. In primo luogo si intende dotare lo studente di una conoscenza rigorosa e di una capacità di applicare quei risultati e metodi della Logica Matematica che trovano applicazione in numerose aree dell'Informatica. D'altra parte si intende offrire allo studente una strumenti e conoscenze fondamentali per intraprendere un percorso di ricerca in Informatica Teorica.

Conoscenza e comprensione:
Il corso mira a dotare lo studente di una conoscenza rigorosa degli argomenti del corso attraverso lo studio delle dimostrazioni e la produzione di argomenti rigorosi nello svolgimento degli esercizi. Particolare attenzione è data alla motivazione concettuale, alla dimostrazione rigorosa e alla applicabilità dei risultati trattati nel corso.

Applicazione di conoscenza e comprensione:
I metodi della logica matematica hanno un ruolo fondamentale in diverse aree dell'Informatica quali la Teoria della Complessità, la Teoria delle Basi di Dati, l'Intelligenza Artificiale. Si mira a stimolare nello studente la capacità di applicare in vari contesti dell'informatica i metodi e i risultati studiati.

Autonomia di giudizio:
Viene stimolata la partecipazione attiva alle lezioni ed esercitata l'autonomia di giudizio attraverso l'assegnazione di esercizi e problemi.

Abilità comunicative:
Lo studente può scegliere di dare l'esame finale in forma di presentazione seminariale davanti alla classe di un risultato concordato con il docente.

Capacità di apprendimento successivo:
I metodi di analisi e formalizzazione acquisiti durante il corso trovano applicazione in diverse aree dell'Informatica. L'esercizio di formalizzazione e problem-solving durante il corso rinforza le capacità di apprendimento e acquisizione di nuove competenze.

Conoscenza e comprensione di alcuni concetti, metodi e risultati fondamentali della Logica applicata all'Informatica.
Capacità di formalizzare problemi di vario tipo come problemi logici. Capacità di svolgere dimostrazioni
rigorose nell'ambito della Logica applicata all'Informatica. Capacità di orientarsi nella ricerca attuale.

Nozioni base sui connettivi logici, familiarità con il concetto informale di algoritmo.

Fondamenti: Logica predicativa, strutture e modelli. Teorie. Definibilità, completezza, decidibilità, esempi di teorie
complete, eliminazione dei quantificatori, isomorfismo ed equivalenza elementare di strutture.

Teoria dei Modelli Finiti: esprimibilità di query in varie logiche. Metodi per dimostrare la non-esprimibilità
di query, giochi di Ehrenfeucht-Fraissé, condizioni di back and forth, località di Gaifman, caratterizzazione logica
di classi di complessità (Teorema di Fagin su NP).

Indecidibilità: indecidibilità della validità (Teoremi di Church e Trakhtenbrot), indecidibilità della verità aritmetica
(Teoremi di Gödel), Gerarchia Aritmetica, computazione con oracoli, Teoremi di Post, teoremi con istanze calcolabili
senza soluzioni calcolabili (Teoremi di König, Ramsey, Hindman).

Miscellanea: argomenti di ricerca scelti.

Dispense fornite dal docente.

1. Introduction to Mathematical Logic, Elliot Mendelson
2. A concise introduction to Mathematical Logic, W. Rautenberg
3. Elements of Finite Model Theory, L. Libkin

Lezione frontale. La partecipazione dello studente è stimolata attraverso un approccio dialogico che favorisca l'interazione.
Ampio spazio è dato all'approfondimento dei concetti introdotti attraverso esempi ed esercizi.

La partecipazione al corso è fortemente consigliata. Chi intende dare l'esame da non frequentante è invitato a contattare il docente prima dell'inizio del corso al fine di stabilire una modalità adeguata di partecipazione.

Homework: 4/5 assegnamenti di homework durante il corso.

Esame Finale: A scelta tra una prova scritta e una presentazione seminariale di un argomento/articolo.

Voto finale: 40% homework e 60% esame finale.

Presentazione di un articolo di ricerca o progetto.