Theoretical Computer Science

The 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

Progressive specialisation: G1F (has less than 60 credits in first‐cycle 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)