Theoretical Computer Science - Anno Accademico 2012/2013
=== Clicca qui per visitare la pagine Web dell'Anno Accademico corrente ===
Indice
Informazioni generali
Settore scientifico disciplinare: INF/01 - Informatica.
Numero di crediti ECTS: 10 (di cui 4 relativi ad attività di laboratorio).
Prerequisiti: Nessuno.
Attività di apprendimento e metodologie didattiche: Lezioni frontali ed esercitazioni.
Metodi e criteri di accertamento del profitto: Prova scritta più prova orale, entrambe obbligatorie.
Orario ricevimento studenti
Docente: Il Prof. Nicola Leone riceve per appuntamento .
Esercitatore: Il Dr. Marco Manna riceve ogni lunedì dalle 10:30 alle 12:30 presso il cubo 30B .
Obiettivi formativi
- La prima parte del corso si propone di fornire le conoscenze di base dell'Informatica Teorica con particolare attenzione alla teoria della calcolabilità. 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.
- Nella seconda parte del corso, l'accento è posto sulla teoria della complessità. Gli studenti saranno, quindi, in grado di distinguere tra problemi trattabili, computazionalmente difficili ed intrattabili. Essi saranno inoltre in grado di determinare formalmente l'esatta complessità computazionale di svariati problemi d'interesse.
Avvisi
L'orale relativo alla prova scritta del 06.09.2013 si terrà giorno 12.09.2013 alle ore 16.00 presso l'ufficio del Prof. Leone. La visione compiti si terrà giorno 12.09.2013 alle ore 15.15 presso l'ufficio del Dr. Manna. Risultati prova scritta (leggi)
Programma del corso
Parte 1: Macchine di Turing e Calcolabilità
- Introduzione.
- Nozioni matematiche di base (insiemi, relazioni, funzioni, cardinalità, grafi).
- Linguaggi formali (alfabeti, linguaggi, rappresentazioni finite di linguaggi, automi a stati finiti e linguaggi regolari).
- Macchine di Turing (TM a singolo nastro, TM deterministiche, Computabilità secondo Turing, TM multinastro).
- Calcolabilità e decidibilità (Tesi di Church-Turing, codifica di una TM; TM universale, il problema della fermata, linguaggi indecidibili, enumerazione di funzioni ricorsive, funzioni non calcolabili, Teoremi di Kleene e Rice, insiemi decidibili e semi-decidibili).
- Indecidibilità ed incompletezza nella logica del primo ordine (assiomi per la teoria dei numeri, indecidibilità e incompletezza).
Parte 2: Complessità Computazionale
- Introduzione (problemi e algoritmi: Reachability, MST, TSP).
- Classi di complessità deterministiche (P, problemi P-completi).
- Macchine di Turing nondeterministiche. La classe NP. Certificati polinomiali. NP-completezza. Teorema di Cook-Levin.
- Complessità spaziale e teoremi di gerarchia (L, problemi L-completi, NL, problemi NL-completi, PH, PSPACE).
Testi di riferimento
Testo ufficiale
Elaine A. Rich. Automata, Computability and Complexity: Theory and Applications. Addison-Wesley.
Molto utile
Papadimitriou, Computational complexity. Addison-Wesley.
Potenzialmente utili
Ghezzi, Mandrioli, Informatica teorica. Città-Studi.
Kleinberg, Tardos, Algorithm Design. Addison-Wesley.
Ausiello, d’Amore, Gambosi, Linguaggi, Modelli, Complessità (leggi)
Arora, Barak, Complexity Theory: A Modern Approach (leggi)
Nozioni di base
Lewis, Harry, Papadimitriou, Elements of the theory of computation. Prentice-Hall.
Esami
Appello del 17 febbraio 2014
Risultati prova scritta (leggi)
- Visione compiti: venerdì 28 febbraio 2014, ore 12.00, ufficio Dr. Manna
Appello del 06 settembre 2013
Risultati prova scritta (leggi)
- Visione compiti: giovedì 12 settembre 2013, ore 15.15, ufficio Dr. Manna
- Prova orale: giovedì 12 settembre 2013, ore 16.00, ufficio Prof. Leone
Appello del 09 luglio 2013
Risultati prova scritta (leggi)
- Visione compiti: giovedì 11 luglio 2013, ore 11.30, ufficio Dr. Manna
- Prova orale: venerdì 12 luglio 2013, ore 11.30, ufficio Prof. Leone
Appello del 20 giugno 2013 (solo matematici)
Risultati prova scritta - (leggi)
- Visione compiti: martedì 25 giugno 2013, ore 9.30, ufficio Dr. Manna
- Prova orale: venerdì 28 giugno 2013, ore 9.30, ufficio Prof. Leone