Theoretical Computer Science
A.Y. 2020/2021
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 cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Instructions for lecturing amid pandemics will be immediately posted on the websites dedicated to the course (see url's below).
in case of online lecturing, lectures will be provided via Zoom either syncronously and recorded for an asyncronous attendance. The contents of the course as well as the resources for preparing the final exam will not modify. The final exam will take place via Zoom according to modality and criterions adopted for the traditional exam, described below.
in case of online lecturing, lectures will be provided via Zoom either syncronously and recorded for an asyncronous attendance. The contents of the course as well as the resources for preparing the final exam will not modify. The final exam will take place via Zoom according to modality and criterions adopted for the traditional exam, described below.
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. 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
Textbooks:
· 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.
Websites:
- ARIEL https://cmereghettiit.ariel.ctu.unimi.it/v5/home/Default.aspx
- ONLINE LECTURES: https://vc.di.unimi.it/
· 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.
Websites:
- ARIEL https://cmereghettiit.ariel.ctu.unimi.it/v5/home/Default.aspx
- ONLINE LECTURES: https://vc.di.unimi.it/
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.
Professor(s)
Reception:
On appointment, via email
Room S 6008, VI floor, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy