Theoretical Computer Science

Course code

IFI6212.DT

old course code

Course title in Estonian

Teoreetiline informaatika

Course title in English

Theoretical Computer Science

ECTS credits

4.0

approximate amount of contact lessons

56

Teaching semester

spring

Assessment form

Examination

lecturer of 2019/2020 Spring semester

õppejõud on määramata

lecturer of 2020/2021 Autumn semester

lecturer not assigned

Course aims

The aim is to offer basic knowledge about the main structures of theoretical computer science – finite automata, formal languages, solvability, complexity – and their basic properties as well as skills to apply the knowledge acquired for solving various exercises.

Brief description of the course

Scope of theoretical computer science. Basic notions from graph theory and formal languages. Finite automata and recognizable languages. Regular expressions; correspondence between regular expressions and finite automata. Pumping-lemma for regular languages. Context-free grammars and their normal forms. Pumping-lemma for context-free languages. Pushdown automata. Turing machines and type 0 languages. Chomsky hierarchy. Solvability and complexity of algorithms. Petri nets.

Independent work

Acquiring lecture notes and solving exercises.

Learning outcomes in the course

The learner

- Knows basic concepts, results and problems of a problem area (finite automata and formal languages) of theoretical computer science;

- Is able to solve exercises related to finite automata and formal languages;

- Is able to analyse finite automata, grammars and languages.

- Knows basic concepts, results and problems of a problem area (finite automata and formal languages) of theoretical computer science;

- Is able to solve exercises related to finite automata and formal languages;

- Is able to analyse finite automata, grammars and languages.

Assessment methods

Exam. The score has two components: solving exercises (50%) and theoretical questions (50%).

Teacher

Peeter Normak, PhD

Study literature

Peeter Normak, Teoreetiline informaatika. Loengukonspekt. TLÜ informaatika instituut 2010

Replacement literature

1. Michael Sipser (1997), Introduction to the Theory of Computation, ISBN 0-534-94728-X.

2. John C. Martin (2011), Introduction to Languages and the Theory of Computation, ISBN 9780071289429.

3. John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman (2007), Introduction to automata theory, languages and computation, Addison-Wesley, (www-db.stanford.edu/~ullman/ialc.html).

2. John C. Martin (2011), Introduction to Languages and the Theory of Computation, ISBN 9780071289429.

3. John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman (2007), Introduction to automata theory, languages and computation, Addison-Wesley, (www-db.stanford.edu/~ullman/ialc.html).