MAT-73006 Theoretical Computer Science, 7 cr
Additional information
Suitable for postgraduate studies
Person responsible
Henri Hansen, Antti Valmari
Lessons
Implementation 1: MAT-73006 2015-01
| Study type | P1 | P2 | P3 | P4 | Summer |
|
|
|
|
|
|
|
Requirements
Examination.
Completion parts must belong to the same implementation
Learning Outcomes
The student knows the classical fundamental results in theoretical computer science.
Content
| Content | Core content | Complementary knowledge | Specialist knowledge |
| 1. | Regular expressions. Deterministic and nondeterministic finite automata. | ||
| 2. | Backus-Naur format. Context-free grammars. Push-down automata. | ||
| 3. | Turing machines and their relation to computers and programming languages. | ||
| 4. | Undecidability. Rice's theorem. | ||
| 5. | NP-completeness. A glimpse to other complexity classes. |
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 | |
| MAT-71000 Tieto ja laskenta | Advisable | |
| TIE-02200 Ohjelmoinnin peruskurssi | Mandatory |
Correspondence of content
| Course | Corresponds course | Description |
| MAT-73006 Theoretical Computer Science, 7 cr | OHJ-2306 Introduction to Theoretical Computer Science, 6 cr |