MAT-73006 Theoretical Computer Science, 7 cr
Additional information
Suitable for postgraduate studies.
Person responsible
Tapio Elomaa
Lessons
| Implementation | Period | Person responsible | Requirements |
| MAT-73006 2017-01 | 3 - 4 |
Tapio Elomaa Henri Hansen |
- Examination. |
Learning Outcomes
The student knows the classical fundamental results in theoretical computer science.
Content
| Content | Core content | Complementary knowledge | Specialist knowledge |
| 1. | Basic understanding of regular expressions. Deterministic and nondeterministic finite automata, the ability to design a DFA and a RE for a given verbal or mathematical description of a regular language. Understanding the formulation of the pumping lemma. | Awareness of the Myhill-Nerode theorem, ability to apply the pumping lemma to prove that a language is not regular. | The ability to prove properties of regular languages. A complete understanding of the proofs of the central theorems about regular languages; the ability to prove variants of the main theorems. |
| 2. | Ability to design simple Context-free grammars and Push-down automata. Awareness of the pumping lemma for CFLs. | Understanding that CFLs are polynomial, that emptiness of CLF is polynomial but universality is undecidable. Ability to formulate and justify (or even prove) the pumping lemma for CFLs. | Ability to design syntax for programming languages. Parsing theory, and other applications of CFLs. |
| 3. | Ability to design simple Turing machines. Ability to state their relation to computers and programming languages. | ||
| 4. | Knowledge of undecidability and formulation of Rice's theorem. Ability to show undecidability of certain problems via reduction. Either universality of CFLs, emptiness of LBA, or the Post Correspondence problem. | Ability to formulate proofs of undecidability. A deeper understanding of undecidability. | |
| 5. | Stating the formulation and definition NP-completeness. The ability to apply this awareness to algorithmic problems. A rudimentary understanding of complexity classes P, NP, PSPACE, L and NL. | Ability to prove Cook and Levin theorem (NP-completeness of SAT), ability to apply reductions to the most well-known NP-complete problems. Formulation of Savitch-theorem. Awareness and a rudimentary understanding of probabilistic complexity classes, and of NC and "parallel" computation, P-complete problems | The ability to prove or disprove P=NP. :-) |
Study material
| Type | Name | Author | ISBN | URL | Additional information | Examination material |
| Book | Introduction to the Theory of Computation | Michael Sipser | Yes |
Prerequisites
| Course | Mandatory/Advisable | Description |
| MAT-02650 Algoritmimatematiikka | Mandatory | 1 |
| MAT-02656 Mathematics for Algorithms | Mandatory | 1 |
| TIE-02200 Ohjelmoinnin peruskurssi | Mandatory | 2 |
| TIE-02206 Basic Course on Programming | Mandatory | 2 |
| MAT-71000 Tieto ja laskenta | Advisable |
1 . This or an equivalent course.
2 . This or an equivalent course.
Correspondence of content
| Course | Corresponds course | Description |
| MAT-73006 Theoretical Computer Science, 7 cr | OHJ-2306 Introduction to Theoretical Computer Science, 6 cr |