Calcolabilita' e Complessita' (LS in Informatica) - a.a. 2006/07
Matematica Discreta (Logica Matematica), Programmazione, Algoritmi e
Strutture Dati.
Fornire nozioni e risultati fondamentali di calcolabilita' e
complessita' computazionale.
L'esame si suddivide in una prova scritta ed una orale. Per la prova
scritta si danno in genere 2 ore. Durante lo scritto e' possibile
consultare dispense e libri. E' possibile conservare il voto dello
scritto negli appelli successivi, basta non ritentarlo (o non
cosegnarlo). Tuttavia, alla fine di ogni anno accademico (dopo
l'appello di Settembre) viene fatto un reset dei voti.
- modelli di calcolo:
TM, RAM, funzioni calcolabili, complessita' tempo e spazio, relazione
tra i due modelli di calcolo, Tesi di Church e Tesi di Church estesa.
- calcolabilita':
funzioni calcolabili, problemi/sottoinsiemi decidibili e
semidecidibili, riducibilita' tra problemi, codifica delle TM, TM
universale, esempi di problemi non (semi)decidibili, proprieta' di
chiusura dei sottoinsiemi (semi)decidibili.
- complessita':
classi di complessita', relazioni tra classi di complessita' ed
O-notazione, classi naturali di complessita' (P, NP), teorema di Cook,
esempi di problemi NP-completi.
- panoramica su altri argomenti di complessita':
accenni ad altri modelli di calcolo (per algoritmi probabilistici e
paralleli), e relative classi di complessita'.
- [P94] C.Papadimitriou. Computational Complexity.
Addision-Wesley, 1994.
(CH 1-3, 7-9)
Altri testi, (*) indica che puo' rimpiazzare [P94]
- R.J. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1988.
- E. Börger, Computability, Complexity, Logic, North-Holland, 1989.
- *A. Bernasconi, B. Codenotti, Introduzione alla Complessità Computazionale, Springer, 1998.
- T.H. Cormen, C.E. Leiserson, L.R. Rivest, Introduction to Algorithms, MIT Press, 1990.
- M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman & Co., 1979.
- H.R. Lewis, Ch.H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
- N.D. Jones, Computability and Complexity, MIT Press, 1997.
- R. Sommerhalden, S.C. van Westrhenen, The Theory of Computability, Addison-Wesley, 1988.