| | | corso | | | |
Fondamenti dell'Informatica: Calcolabilitą e Complessitą A
(Corso di Laurea in Informatica (quinquennale))
Codice: | 4I038 | Crediti: | 6 | Semestre: | 1 | Sigla: | FCC | |
Docente
Pierpaolo Degano
Tel. 0502212757Descrizione
Il corso introduce le nozioni fondamentali della teoria della
calcolabilità.
e della complessità. La prima parte delinea i concetti e la natura d=
ei
problemi che hanno soluzione effettiva. La seconda parte caratterizza i
problemi che sono risolvibili con risorse di calcolo limitate.
English Description
We will introduce the basics of computability and complexity theory. The
first part studies the concepts and the nature of effectively solvable
problems. The second part characterizes the problems that are solvable with
limited computing resources.
Programma
Introduzione (5h + 3h)
Programmi for/while e macchine di Turing.
Funzioni calcolabili e non; problemi solubili e non; il problema della
fermata.
Calcolabilità (10h + 6h)
Le funzioni calcolabili e la tesi di Church.
Funzioni ricorsive primitive e generali.
La forma normale di Kleene.
Funzioni universali e interpreti.
Il teorema s-m-n.
Insiemi ricorsivi e ricorsivamente enumerabili; riducibilità.
Il teorema di Rice.
Complessità (10h + 6h)
Complessità di problemi e sue misure: tempo e spazio.
Classi di complessità e loro robustezza; problemi ardui e problemi
completi.
Funzioni polinomiali e riducibilità polinomiale.
La classe P-time e la P-completezza; principali problemi P-completi.
La classe NP-time e la NP-completezza.
Teorema di Cook e principali problemi NP-completi.
Altre classi di complessità.
Gerarchie di classi di complessità.
Ore lezione: | 25 | Ore esercitazione: | 15 | | | |
Bibliografia
Testi di riferimento
- Ch.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
- R.J. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag,
1988.
Testi di consultazione
- E. Boerger, 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, M=
IT
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
Ulteriore pagina web del corso: