| | | corso | | | | | |
Calcolabilità e complessità
Codice: | 268AA | Crediti: | 9 | Semestre: | 1 | Sigla: | CC | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Pierpaolo Degano
Tel. 0502212757Ultima versione disponibile: programma da confermare per l’a.a. 2012/2013
Prerequisiti
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. Inoltre si intendono presentare i risultati piú importanti della teoria dei linguaggi formali e degli automi. 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
- Riducibilità, problemi insolubili
- Linguaggi formali
- Grammatiche e automi
- 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)
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 introduces the main results of the theory of formal languages and automata. The third part characterizes the problems that
are solvable with limited computing resources. Finally, we will show the impact on computer science of the theoretical results presented.
Indicazioni metodologiche
Organizzare il processo di apprendimento in sequenza logica
Programma
- 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
- Formal languages
- Grammars and Automata
- Time and space measures
- Deterministic and non-deterministic complexity classes
(time/space), P- e NP-completeness
- Other classes (co-NP, random, approximation, parallelism)
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