| | | |  corso | | | | | |
Elementi di calcolabilità e complessità
| Codice: | 246AA | Crediti: | 6 | Semestre: | 1 | Sigla: | ECC | |
| |
| Settore disciplinare: | INF/01 - Informatica |
Docente
Pierpaolo Degano
Tel. 0502212757Prerequisiti
Un po' di teoria degli insiemi e delle strutture algebriche; un po' 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. Si avrà cura di legare i risultati della teoria introdotta ad applicazioni
pú strettamente legarte alla nostra disciplina.
Conoscenze. Conoscenze di base
Capacità. Capacità di comprensione, apprendimento e ragionamento logico-deduttivo
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.
- Macchine di Turing (deterministiche e non, a più nastri, I/O)
- Linguaggi calcolabili, MdT universale
- Funzioni ricorsive e linguaggi di programmazione,
- Totalità e diagonalizzazione
- Teoremi fondamentali
- Riducibilità, problemi insolubili
- Funzioni di misura di tempo e spazio
- Classi di complessità (tempo/spazio) deterministiche e non, P- e NP-completezza
- Cenni si altre classi (co-NP, caso, approssimazione, parallelismo)
Programma
- Turing machines (deterministic, non-deterministic, k-tapes, I/O)
- Computable languages, Universal Turing machine
- Recursive functions and programming languages
- Total functions and diagonalization
- Main theorems
- 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) -- outline
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
