MAT-73006 Theoretical Computer Science, 7 cr

Lisätiedot

Suitable for postgraduate studies.

Vastuuhenkilö

Tapio Elomaa

Opetus

Toteutuskerta Periodi Vastuuhenkilö Suoritusvaatimukset
MAT-73006 2017-01 3 - 4 Tapio Elomaa
Henri Hansen
- 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   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.



Vastaavuudet

Opintojakso Vastaa opintojaksoa  Selite 
MAT-73006 Theoretical Computer Science, 7 cr OHJ-2306 Introduction to Theoretical Computer Science, 6 cr  

Päivittäjä: Elomaa Tapio, 26.03.2018