Docente
|
LENZERINI MAURIZIO
(programma)
Sezione 1: Logica e informatica
Prof. Maurizio Lenzerini
La prima parte del corso ha l’obiettivo di introdurre la logica matematica come potente strumento per modellare e ragionare formalmente su diversi aspetti dell’informatica, come i requisiti di un progetto, i dati, i programmi, gli automi e la computazione in generale. Vengono studiati i principali sistemi formali della logica, in primis la logica proposizionale e la logica dei predicati. Viene affrontato il tema dell’uso della logica nello specificare argomenti, dimostrare o confutare la loro validità ed inferire le loro conseguenze, anche in modo automatico. Vengono poi approfonditi alcuni temi che riguardano l’uso della logica nell’informatica, in particolare nella gestione dei dati, nell’interrogazione di basi di dati, nella specifica di programmi e nel ragionamento sulle proprietà dei programmi e degli automi.
1. La logica proposizionale
Sintassi e semantica della logica proposizionale. Potere espressivo della logica proposizionale. “Satisfiability”: problema, complessità e algoritmi di decisione. L’inferenza nella logica proposizionale. Problemi e algoritmi di decisione relativi all’inferenza.
2. La logica dei predicati del primo ordine
Sintassi e semantica della logica dei predicati del primo ordine. Potere espressivo della logica dei predicati. L’inferenza nella logica dei predicati: deduzione, induzione e abduzione. Sistemi formali per la deduzione. Problemi di decisione nella logica dei predicati. Cenno alle logiche modali e temporali.
3. Applicazione della logica nell’informatica
La logica nello sviluppo e nell’analisi dei programmi. Logica e automi. La logica nella gestione dei dati. Logica e linguaggi di interrogazione nelle basi di dati. La logica nella rappresentazione della conoscenza. Linguaggi di programmazione basati sulla logica: il linguaggio Prolog.
Sezione 2: Algoritmi e apprendimento automatico
Prof. Stefano Leonardi
La seconda parte del corso intende illustrare alcune importanti applicazioni dei metodi probabilistici e dell’ottimizzazione dinamica in informatica quali, ad esempio, la soluzione efficiente di problemi numerici e combinatorici, l’apprendimento automatico, la sicurezza, le strategie sequenziali di decisione, la codifica dell’informazione, e l’analisi dei dati e delle reti ad ampia scala.
1. Analisi di algoritmi e probabilità
Analisi di algoritmi probabilistici (Quicksort, Hashing). Algoritmi probabilistici per problemi numerici (test di primalità, cryptography). Il Metodo Monte Carlo. Le catene di Markov e le loro applicazioni alla reti
2. La programmazione dinamica
Problemi su sequenze. Cammini minimi. Processi sequenziali di decisione (backward induction) e hidden Markov models (algoritmo di Viterbi).
3. Apprendimento e Classificazione
Modelli bayesiani e apprendimento automatico. La classificazione lineare. Algoritmi di classificazione e clustering. Apprendimento stocastico online e modelli ad esperti.
DIspense del docente
|