Theoretical Computer Science
7.5 ECTS creditsThe course deals with the fundamentals of automata theory, formal languages, computability and complexity theory. The course is central to the understanding of the potentials and limitations of the computer and why some problems are not computable whereas others are difficult or easy. The course comprises the following components:
Automata theory and formal languages:
-Regular languages and expressions and finite automata
-Context-free languages and grammars and pushdown automata
-Pumping lemma
Computability theory:
-Turing machines
-Church-Turing thesis
-Decidability of problems/languages
-Halting problem
-Recursion theorem (linking to computer virus)
Complexity theory:
-Complexity classes
-Time complexity of algorithms
-Cryptography
Automata theory and formal languages:
-Regular languages and expressions and finite automata
-Context-free languages and grammars and pushdown automata
-Pumping lemma
Computability theory:
-Turing machines
-Church-Turing thesis
-Decidability of problems/languages
-Halting problem
-Recursion theorem (linking to computer virus)
Complexity theory:
-Complexity classes
-Time complexity of algorithms
-Cryptography
Progressive specialisation:
G1F (has less than 60 credits in first鈥恈ycle course/s as entry requirements)
Education level:
Undergraduate level
Admission requirements
Programming Techniques 7.5 ECTS cr, Software Development Methodology 7.5 ECTS cr, and attended course Discrete Mathematics 7.5 ECTS cr, or equivalent.
Selection:
Selection is usually based on your grade point average from upper secondary school or the number of credit points from previous university studies, or both.
This course is included in the following programme
- Master of Science in Computer Engineering (studied during year 2)