Fondamenti dell'Informatica: Calcolabilità e Complessità A

Pierpaolo Degano      Tel. 0502212757

Il corso introduce le nozioni fondamentali della teoria della calcolabilità. e della complessità. La prima parte delinea i concetti e la natura dei problemi che hanno soluzione effettiva. La seconda parte caratterizza i problemi che sono risolvibili con risorse di calcolo limitate.

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.

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à.

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, 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.