MAT-73006 Theoretical Computer Science, 7 cr
Lisätiedot
Suitable for postgraduate studies.
Vastuuhenkilö
Henri Hansen, Tapio Elomaa, Antti Valmari
Opetus
| Toteutuskerta | Periodi | Vastuuhenkilö | Suoritusvaatimukset |
| MAT-73006 2016-01 | 3 - 4 |
Henri Hansen |
- Learning diary and presentation - Examination. |
Osaamistavoitteet
The student knows the classical fundamental results in theoretical computer science.
Sisältö
| Sisältö | Ydinsisältö | Täydentävä tietämys | Erityistietämys |
| 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. :-) |
Oppimateriaali
| Tyyppi | Nimi | Tekijä | ISBN | URL | Lisätiedot | Tenttimateriaali |
| Book | Introduction to the Theory of Computation | Michael Sipser | Yes |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| MAT-02650 Algoritmimatematiikka | Mandatory | |
| MAT-71000 Tieto ja laskenta | Advisable | |
| TIE-02200 Ohjelmoinnin peruskurssi | Mandatory |
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
| MAT-73006 Theoretical Computer Science, 7 cr | OHJ-2306 Introduction to Theoretical Computer Science, 6 cr |