Stud.IP Uni Oldenburg
University of Oldenburg
08.06.2023 21:21:41
inf401 - Foundations of Theoretical Computer Science (Complete module description)
Original version English PDF Download
Module label Foundations of Theoretical Computer Science
Modulkürzel inf401
Credit points 6.0 KP
Workload 180 h
Institute directory Department of Computing Science
Verwendbarkeit des Moduls
  • Bachelor's Programme Computing Science (Bachelor) > Aufbaumodule
  • Bachelor's Programme Mathematics (Bachelor) > Nebenfachmodule
  • Dual-Subject Bachelor's Programme Computing Science (Bachelor) > Wahlpflicht Theoretische Informatik (30 KP)
  • Master of Education Programme (Gymnasium) Computing Science (Master of Education) > Pflichtmodule
  • Master of Education Programme (Hauptschule and Realschule) Computing Science (Master of Education) > Mastermodule
Zuständige Personen
Olderog, Ernst-Rüdiger (Module responsibility)
Lehrenden, Die im Modul (Prüfungsberechtigt)
Skills to be acquired in this module
Introduction to the theory of automata, formal languages, computability, and complexity

Professional competence
The students:
  • Know different classes of languages (e.g. regular and context-free languages)
  • Know automata models corresponding to the respective language classes (e.g. finite automata, pushdown automata, Turing machines)
  • Construct automata, Turing machines, and grammars for given tasks
  • Know equivalent formalisations of the concept of algorithm
  • Classify functions as algorithmically computable and problems as algorithmically decidable
  • Know and recognize undecidable problems
  • Evaluate the complexity of algorithms
  • Know problems that are solvable deterministically or nondeterministically in polynomial time

Methodological competence
The students:
  • Learn about the power of abstract models of computation

Social competence
The students:
  • Work together in small groups to solve problems
  • Present solutions to problems to groups of other students

The students:
  • Learn persistence in pursuing difficult tasks
  • Learn precision in writing down solutions
Module contents
In the first part of the course, different classes of languages are introduced (regular and context-free languages).
For each class a matching automata model is presented (finite automata, pushdown automata). Various properties are proven for the introduced classes of languages and models of automata.

In the second part of the course, we examine which functions are computable and which problems are decidable. To this end, the concept of algorithm is formalised. Turing machines and grammars turn out as equivalent approaches. We show that there are problems that are undecidable. Many of these problems are of practical interest.

The third part of the course deals with the complexity of algorithms, i.e. how much time and space is required to solve a problem. In particular, we consider problems that are solvable in polynomial time, either deterministically or non-deterministically. These problems are classified as P and NP.
- essentiell: Skript "Grundbegriffe der Theoretischen Informatik", jeweils in aktueller Ausgabe
- empfohlen: Schöning: "Theoretische Informatik kurzgefasst", 5. Auflage, Spektrum, 2008
- Gute Sekundärliteratur: Hopcroft, Motwani, Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie", Pearson, 2002 (ein Klassiker...)
Language of instruction German
Duration (semesters) 1 Semester
Module frequency jährlich
Module capacity unlimited
Modullevel / module level AC (Aufbaucurriculum / Composition)
Modulart / typ of module je nach Studiengang Pflicht oder Wahlpflicht
Lehr-/Lernform / Teaching/Learning method V+Ü
Vorkenntnisse / Previous knowledge
Form of instruction Comment SWS Frequency Workload of compulsory attendance
Lecture 3 WiSe 42
Exercises 1 WiSe 14
Präsenzzeit Modul insgesamt 56 h
Examination Prüfungszeiten Type of examination
Final exam of module
At the end of the lecture period
Written or oral exam