Calcolabilità e complessità

Pierpaolo Degano      Tel. 0502212757

Un po' di teoria degli insiemi e delle strutture algebriche; un po' di logica; la nozione di funzione.

Comprendere quali sono i problemi risolvibili meccanicamente, in assenza e in presenza di vincoli sulle risorse di calcolo

Conoscenze. Conoscenze di base

Capacità. Capacità di comprensione, apprendimento e ragionamento logico-deduttivo

Comportamenti. Comportamenti razionali

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.

• Macchine di Turing (deterministiche e non, a più nastri, I/O)
• Linguaggi calcolabili, MdT universale
• Funzioni ricorsive e linguaggi di programmazione,
• Totalità e diagonalizzazione
• Riducibilità, problemi insolubili
• Funzioni di misura di tempo e spazio
• Classi di complessità (tempo/spazio) deterministiche e non, P- e NP-completezza
• Altre classi (co-NP, caso, approssimazione, parallelismo)

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.

Organizzare il processo di apprendimento in sequenza logica

• Turing machines (deterministic, non-deterministic, k-tapes, I/O)
• Computable languages, Universal Turing machine
• Recursive functions and programming languages
• Total functions and diagonalization
• Reducibility, unsolvable problems
• Time and space measures
• Deterministic and non-deterministic complexity classes (time/space), P- e NP-completeness
• Other classes (co-NP, random, approximation, parallelism)

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.

Scritto e orale