Calcolabilita' e Complessita' (Laurea Specialistica) - a.a. 2004/05
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 Gennaio-Febbraio) 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.