Calcolabilità e Complessità

Calcolabilità e Complessità
Sigla Corso:	CC
Nome Docente/i:	Pierpaolo Degano
Corso di laurea:	Informatica
Anno di corso:	3
Home page del corso:	[1]

Programma

• Macchine di Turing (deterministiche, non deterministiche, a k nastri, I/O)
• Linguaggi calcolabili, macchina di Turing universale
• Funzioni ricorsive e linguaggi di programmazione, funzioni totali e diagonalizzazione
• Riducibilità, problemi insolubili
• Misure in spazio e in tempo
• Classi di complessità (in tempo/spazio) deterministiche e non deterministiche. P- e NP-completezza.
• Altre classi di complessità (co-NP, random, approssimate, parallele)

Bibliografia

Ch.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
R.J. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1988.
P. Degano, Notes.
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.

Modalità di esame

Generalmente solo orale, quando viene fatto lo scritto gli esercizi sono perlopiù standard per scremare dall'orale la gente che non ci ha proprio capito niente.

Materiale aggiuntivo

Appunti del corso: Parte 1 (calcolabilità), Parte 2 (linguaggi formali), Parte 3 (complessità).

Vedi anche

Problemi CC - una lista di alcuni problemi di calcolabilità/complessità con annessa discussione.