Theoretical Computer Science

Education facts

Code: DVGA17

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

Entry requirements

Programming techniques (7.5 credits). Discrete mathematics (7.5 credits), or Software development methodology (7.5 credits). Equivalence assessment may be made.

Education offerings

Each offering has its own dates and conditions. Closed offerings are retained as history and do not mean that a new application is open.

• Theoretical Computer Science

  Karlstad University

  Karlstad

  Start date: 9 November 2026

  End date: 17 January 2027

  Pace of study: 50 %