Stud.IP Uni Oldenburg
University of Oldenburg
19.09.2020 11:02:59
inf401 - Foundations of Theoretical Computer Science (Course overview)
Department of Computing Science 6 KP
Module responsibility
  • Annegret Habel
  • Ernst-Rüdiger Olderog
Authorized examiners
  • Die im Modul Lehrenden
module components Semester courses Wintersemester 2020/2021 Examination
Lecture
  • Unlimited access 2.01.401 - headache
    • Prof. Dr. Ernst-Rüdiger Olderog
    • Elke Wilkeit

    Tuesday: 10:00 - 12:00, weekly (from 20/10/20), V/Ü
    Thursday: 14:00 - 16:00, weekly (from 22/10/20), V

  • No access 2.01.401-A - headache
    • Prof. Dr. Ernst-Rüdiger Olderog
    • Elke Wilkeit

    Monday: 08:00 - 10:00, weekly (from 19/10/20)

  • No access 2.01.401-B - headache
    • Prof. Dr. Ernst-Rüdiger Olderog
    • Elke Wilkeit

    Monday: 16:00 - 18:00, weekly (from 19/10/20)

  • No access 2.01.401-C - headache
    • Prof. Dr. Ernst-Rüdiger Olderog
    • Elke Wilkeit

    Tuesday: 12:00 - 14:00, weekly (from 20/10/20)

  • No access 2.01.401-D - headache
    • Prof. Dr. Ernst-Rüdiger Olderog
    • Elke Wilkeit

    Wednesday: 08:00 - 10:00, weekly (from 21/10/20)

Exercise or tutorial
  • No access 2.01.401-E - headache
    • Prof. Dr. Ernst-Rüdiger Olderog
    • Elke Wilkeit

    Thursday: 08:00 - 10:00, weekly (from 22/10/20)

  • No access 2.01.401-F - headache
    • Prof. Dr. Ernst-Rüdiger Olderog
    • Elke Wilkeit

    Thursday: 16:00 - 18:00, weekly (from 22/10/20)

Notes for the module
Time of examination
At the end of the lecture period
Module examination
Written or oral exam
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


Self-competence
The students:
  • Learn persistence in pursuing difficult tasks
  • Learn precision in writing down solutions