Informatica avanzata
(Offerta Formativa fino all'A.A. 2014/15)
Numero di crediti ECTS: 5
SSD di riferimento: INF/01
Docente: Nicola Leone
Prerequisiti
Nessuno.
Obiettivi
Il corso si propone di fornire le conoscenze di base dell’Informatica Teorica con particolare attenzione alla teoria della calcolabilità ed alla teoria della complessità. Al termine, gli studenti saranno in grado di capire cos’è un problema indecidibile o intrinsecamente difficile ed eventualmente dimostrarne tali proprietà mediante l’applicazione dei teoremi studiati durante il corso o mediante l’uso di tecniche basate sulla riduzione tra problemi.
Programma
- Introduzione (problemi ed algoritmi: Reachability, MST, TSP)
- Insiemi, relazioni, e linguaggi (insiemi, relazioni, funzioni, grafi, insiemi infiniti,cardinalità di insiemi infiniti, numerabilità, notazione asintotica, alfabeti, linguaggi, rappresentazioni finite di linguaggi, automi a stati finiti e linguaggi regolari, linguaggi context-free)
- Macchine di Turing (TM a nastro singolo, TM deterministiche, calcolabilità secondo Turing, TM multi nastro, TM non deterministiche)
- Decidibilità (tesi di Church-Turing, descrizione linearizzata delle TM; TM universale, il problema della terminazione; Linguaggi indecidibili)
- Indecidibilità in logica (assiomi per la teoria dei numeri, indecidibilità ed incompletezza)
- Teoria generale della calcolabilità (Enumerazione di proprietà ricorsive, Proprietà di enumerazioni di funzioni ricorsive, Funzioni non calcolabili, Indecidibilità in matematica ed informatica, Teoremi di Kleene e di Rice, Insiemi decidibili e semidecidibili)
Bibliografia
- Elaine A. Rich. Automata, Computability and Complexity: Theory and Applications. Addison-Wesley.
- Giorgio Ausiello, Fabrizio d’Amore, Giorgio Gambosi. Linguaggi, Modelli, Complessità. Franco Angeli.
- Harry R. Lewis, Christos H. Papadimitriou. Elements of the Theory of Computation.Prentice Hall PTR.
- Christos H. Papadimitriou. Computational Complexity. Addison Wesley.
- Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press.
- Carlo Ghezzi, Dino Mandrioli. Informatica Teorica, UTET.
Tipologia di attività didattiche
Lezioni frontali ed esercitazioni
Metodi di valutazione
Prova scritta + prova orale, entrambe obbligatorie