CdSINFORMATICA
Codice246AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
Moduli | Settore/i | Tipo | Ore | Docente/i | |
ELEMENTI DI CALCOLABILITA' E COMPLESSITA' | INF/01 | LEZIONI | 48 |
|
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 piú strettamente legate alla nostra disciplina.
The student who successfully completes the course will be able to demonstrate a solid knowledge of foundations of computability theory and abstract complexity theory.
Verifiche intermedie e finali
In the written exam the student will be required to solve excercises about computability and formal languages (see the course website for examples). In the oral exam the student will be required to manage the definitions and the theoretical results
Methods:
- Final oral exam
- Final written exam (if Covid permits)
- Periodic written tests (if Covid permits)
È richiesta la capacità di comprensione, apprendimento e ragionamento logico-deduttivo
Understanding, learning and reasoning in a deductive world
Scritto e orale, covid permettendo
Written and oral (if Covid permits)
Educati
Good
I soliti
The usual ones
Un po' di teoria degli insiemi e delle strutture algebriche; un po' di logica (i quantificatori!!); la nozione di funzione; capacità logiche-deduttive
Naive set theory, algebra, logics (especially meaning and use of quantifiers); basic mathematics; reasoning capabilities
Lezioni ed esercitazioni tradizionali, covid permettendo
Delivery: face to face (covid permitting)
Learning activities:
- attending lectures
- participation in discussions
Attendance: Advised
Teaching methods:
- Lectures
Delivery: face to face
Attendance: Advised
Learning activities:
- attending lectures
- participation in discussions
Teaching methods:
- Lectures
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)
The course introduces the basic notions of computability and complexity. The first part presents and formalises the needed concepts and the nature of those problems admitting an effective solution. The second part characterises the problems solvable when the computational resources are bounded.
- 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
- 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.
- Note del docente
- 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.
- Notes by the professor
Scritto e orale, covid permettendo
Writen and oral (if Covid permits)
https://www.di.unipi.it/it/didattica/inf-l/insegnamenti/lista-dei-corsi?cds=inf31&anno=2017