Computability: enumerability, computability, decidability; primitive recursive functions and relations; Ackermann function, mu-recursive functions, Church thesis; Turing machines, the halting problem, universal Turing machine; problem reduction, Rice theorem.
Complexity: tractability and intractability; the classes P and NP; polynomial-time reduction, NP-completeness; Cook theorem; NP-complete problems; further complexity classes; space complexity.
- Massimiliano Goldwurm, Introduzione ai Problemi NP-completi, http://homes.di.unimi.it/goldwurm/algo/npcomp.pdf.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley.
- Daniele Mundici, Dalla macchina di Turing a P/NP, McGraw-Hill.
- Michael Sipser, Introduzione alla teoria della computazione, Maggioli Editore.
KNOWLEDGE AND UNDERSTANDING - Scope of the course is to illustrate the notion of algorithm, describing different formalizations in detail (recursive dunctions and Turing machines). Moreover, the structural complexity of algorithms will be investigated, that is, for a given amount of resources, we will investigate the class of problems which can be solved algorithmically and using at most such an amount.
APPLYING KNOWLEDGE AND UNDERSTANDING - At the end of the course the student is going to acquire basic knowledge of computability and complexity theory and will be able to solve medium level problems in such disciplines. Moreover, the student will have enough tools to deepen her/his knowledge of the subject, in order to tackle more advanced problems.
Algorithms and Data Structures, Discrete Mathematics and Mathematical Logics, Programming, Computer Architecture
Office hours: by appointment, using email (email@example.com) or phone (055 2751484). Webpage of the teacher (including also information on the course): http://web.math.unifi.it/users/ferrari/
Type of Assessment
Written exam (one question concerning computability, one question concerning complexity); oral exam (one question concerning computability, one question concerning complexity). The final grades will be determined by the grades of the written exam (50%) and the oral exam (50%). Among the evaluation parameters there are: skill to reproduce and organize the
knowledge; skill for critical reasoning on the topics of the course; quality
of the presentation; competence in the use of the appropriate vocabulary.
Computability theory: enumerability, computability, decidability; primitive recursive function; primitive recursive relations; Ackermann function, mu-recursive functions, Church thesis; Turing machines, tau-recursive functions; Turing machines as language acceptors; multitrack, multitape, nondeterministic Turing machines; the halting problem, universal Turing machine; problem reduction, Rice theorem.
Complexity theory: time complexity of a Turing machine; tractable and intractable problems; the classes P and NP; polynomial-time reduction and NP-completeness; Cook theorem; examples of NP-complete problems (3-SAT, VERTEX COVER, CLIQUE, the Hamiltonian circuit problem); further complexity classes: the classes co-NP, EXP and NEXP; space complexity, Savitch theorem; complexity of counting: the classes FP and #P.