Theoretical Computer Science
Course code
IFI6019.DT
old course code
IFI6019
Course title in Estonian
Teoreetiline informaatika
Course title in English
Theoretical Computer Science
ECTS credits
5.0
Assessment form
Examination
lecturer of 2024/2025 Autumn semester
Not opened for teaching. Click the study programme link below to see the nominal division schedule.
lecturer of 2024/2025 Spring semester
Not opened for teaching. Click the study programme link below to see the nominal division schedule.
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. Algebraic treatment of finite automata and regular languages. 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.
Learning outcomes in the course
Upon completing the course the student:
- 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 analyze 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 analyze finite automata, grammars and languages.
Teacher
prof Peeter Normak
Prerequisite course 1
Study programmes containing that course