elenco   
        corso   

Calcolabilitą e complessitą

Codice: AA025Crediti: 9Semestre: 1Sigla: CC 
 
Settore disciplinare: INF/01 - Informatica

Docente

Pierpaolo Degano   degano@di.unipi.it  Stanza 285  Tel. 0502212757

Prerequisiti

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

Obiettivi di apprendimento

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

Descrizione

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.

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

     

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

Scritto e orale

home


email