Theoretical Computer Science

A.Y. 2021/2022
Overall hours
Learning objectives
The course aims at introducing basics of computability and complexity theory, suitably presenting theoretical tools also useful to rigorously approach several other issues in computer science. The notion of algorithmically solvable problem is formally investigated, as well as the class of unsolvable problems. Next, the classification of problems into complexity classes is presented, depending on the amount of required computational resources for their automatic solution. The notion of efficiently solvable problem is formally settled.
Expected learning outcomes
The student will be able to apply approaches and formal methods presented along the course into the analysis of problems from several realms. She/he will be able first to correctly formulate and model the problem, then to formally analyze proposed algorithmic solutions, not only focusing on feasibility and efficiency, but also investigating any other issue relevant to the problem under consideration. Moreover, the student will acquire specific knowledge on computability and complexity, fundamental in any computer science research path.
Course syllabus and organization

Single session

Lesson period
Second semester
Instructions for lecturing amid pandemics will be immediately posted on the websites dedicated to the course (see url's below).

Given social distancing which prevents lecture room full usage, lecturing will take place both in presence and online. Online lecturing, will be provided via Zoom either synchronously and recorded for an asynchronous attendance.

The contents of the course, the resources for preparing the final exam and the final exam itself will remain unique, and not affected by the way lecturing will be provided.
Course syllabus
Computability Theory
· Mathematical basics
· Cantor's pair function
· RAM and while programming languages
· Syntax and operational semantics
· Compilers
· Program encoding by numbers
· Interpreter and universal function
· "goto" elimination
· Partial recursive functions
· Church's thesis
· Undecidable problems
· Authomatic parameter passing
· Acceptable programming systems
· Recursion theorem
· Recursive and recursively enumerable sets
· Closure properties
· Rice's theorem

Complexity Theory
· Introducing complexity theory
· Mathematical basics: "big O" notation
· Deterministic Turing machines
· Computational resources: time and space
· Time and space complexity classes
· The classes L, P, PSPACE
· Restricted Church's thesis
· Noneterministic Turing machines: time and space
· The classes NL, NP, NPSPACE
· Savitch's theorem
· Reductions among problems and completeness
· NP, P, PSPACE-complete problems
· Cook's theorem and examples of reductions
Prerequisites for admission
No particular prerequisite required.
Teaching methods
The course consists of traditional lectures in which, first of all, mathematical basics are presented. Such basics will enable a precise formalizations of the foundation of Computability Theory and Complexity Theory. Beside notions related to these two disciplines, exercises and problems will be illustrated aiming at consolidating theory and stimulating the interest in more advanced topics which require and develop a certain scientific maturity. In addition to traditional lectures, online lectures have also been prepared, which can be of help to those unable to attend traditional lectures.
Teaching Resources
· Handouts available at the course website (see below)
· Computability Theory:
- A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986. (Available also in English)
· Complexity Theory:
- M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979.

Assessment methods and Criteria
The final examination equivalently consists either in a written or in an oral exam (to be decided by the responsible of the course) which covers the whole span of topics proposed during the course of Theoretical Computer Science. Questions will be proposed, on both parts characterizing the course, i.e., Computability Theory and Complexity Theory. Questions will aim to check students' knowledge of basic concepts as well as the ability of provide precise formalization of problems and solutions. In addition, some problems will be issued requiring "original" ideas from the students, in order to appreciate a certain level of scientific maturity. Two hours will be devoted for written exam, while about forty minutes for oral exam. During exams, no reference consultation will be allowed. The exam will be rated from 1 to 30.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Mereghetti Carlo
Educational website(s)
On appointment, via email
Uff. S 6008, VI floor, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy