INTRODUCTION TO COMPUTABILITY AND ABSTRACT COMPLEXITY
Academic year2022/23
CourseCOMPUTER SCIENCE
Code246AA
Credits6
PeriodSemester 1
LanguageItalian
| Modules | Area | Type | Hours | Teacher(s) |
| ELEMENTI DI CALCOLABILITA' E COMPLESSITA' | INF/01 | LEZIONI | 48 | |
Obiettivi di apprendimento
Conoscenze
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.
Knowledge
The student who successfully completes the course will be able to demonstrate a solid knowledge of foundations of computability theory and abstract complexity theory.
Modalità di verifica delle conoscenze
Verifiche intermedie e finali
Assessment criteria of knowledge
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)
Capacità
È richiesta la capacità di comprensione, apprendimento e ragionamento logico-deduttivo
Skills
Understanding, learning and reasoning in a deductive world
Modalità di verifica delle capacità
Scritto e orale, covid permettendo
Assessment criteria of skills
Written and oral (if Covid permits)
Modalità di verifica dei comportamenti
I soliti
Assessment criteria of behaviors
The usual ones
Prerequisiti (conoscenze iniziali)
Un po' di teoria degli insiemi e delle strutture algebriche; un po' di logica (i quantificatori!!); la nozione di funzione; capacità logiche-deduttive
Prerequisites
Naive set theory, algebra, logics (especially meaning and use of quantifiers); basic mathematics; reasoning capabilities
Indicazioni metodologiche
Lezioni ed esercitazioni tradizionali, covid permettendo
Teaching methods
Delivery: face to face (covid permitting)
Learning activities:
- attending lectures
- participation in discussions
Attendance: Advised
Teaching methods:
Delivery: face to face
Attendance: Advised
Learning activities:
- attending lectures
- participation in discussions
Teaching methods:
Programma (contenuti dell'insegnamento)
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)
Syllabus
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
Bibliografia e materiale didattico
- 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
Bibliography
- 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
Modalità d'esame
Scritto e orale, covid permettendo
Assessment methods
Writen and oral (if Covid permits)
Altri riferimenti web
https://www.di.unipi.it/it/didattica/inf-l/insegnamenti/lista-dei-corsi?cds=inf31&anno=2017
Updated: 03/08/2022 14:27
