Theoretical Computer Science
A.Y. 2024/2025
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.
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
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
· 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.
Teaching Resources
Textbooks:
· Handouts and slides 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.
Website:
- myAriel https://myariel.unimi.it/course/view.php?id=2431
· Handouts and slides 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.
Website:
- myAriel https://myariel.unimi.it/course/view.php?id=2431
Assessment methods and Criteria
The final examination consists in an oral colloquium 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. About forty minutes will be devoted to the oral colloquium. The exam will be rated from 1 to 30. An evaluation between 18 and 23 indicates an appropriate level of knowledge of basics of theoretical computer science, an evaluation between 24 and 27 indicates a good knowledge of such basics, higher evaluations indicate a very good knowledge and originality in applying basics in theoretical computer science.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Mereghetti Carlo
Shifts:
Turno
Professor:
Mereghetti CarloEducational website(s)
Professor(s)
Reception:
On appointment, via email
Uff. S 6008, VI floor, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy