|
|
|||||||||||||||||
Course Catalog 2013-2014
MAT-73006 Theoretical Computer Science, 7 cr |
Additional information
Suitable for postgraduate studies
Person responsible
Henri Hansen, Antti Valmari
Lessons
| Study type | P1 | P2 | P3 | P4 | Summer | Implementations | Lecture times and places |
|
|
|
|
|
|
|
|
|
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 | Edition, availability, ... | Examination material | Language |
| Book | Introduction to the Theory of Computation | Michael Sipser | Yes | English |
Prerequisites
| Course | Mandatory/Advisable | Description |
| MAT-02650 Mathematics for Algorithms | Mandatory | |
| MAT-71000 Introduction to Information and Computation | Advisable | |
| TIE-02200 Basic course on programming | Mandatory |
Prerequisite relations (Requires logging in to POP)
Correspondence of content
| Course | Corresponds course | Description |
|
|
|
More precise information per implementation
| Implementation | Description | Methods of instruction | Implementation |