Introduction to Theory of Computation


  • For students studying under the FPO of June 12, 2012, it might be possible to improve their grade. For details, see the corresponding email from the SB-S on 2015-08-20.


  • Lecturer:
    Prof. Dr. Ernst W. Mayr
  • Module: IN0011, TUMonline
  • Time and Place:
    Monday, 10:15–12:00, lecture hall MI HS 1
    Thursday, 16:00–17:45, lecture hall MI HS 1
  • Exercises:
    2 hours/wk (obligatory) tutor sessions; location and time: see Exercises
    2 hours/wk (supplemental, voluntary) lab, Thursday, 14:30–15:55, MI HS 1
    Teaching Assistant: Dr. Werner Meixner
  • ECTS: 8 credits
  • Exams:
    See here for more information.
    The exams are closed book, only one A4 format sheet of handwritten notes is allowed.
  • Course Certificate:
    To successfully complete the module students must obtain at least 40% of the points in the final (written) exam.
    Our experience from past years suggests that, in order to pass the written exam, it is very helpful to work on and turn in the weekly homework assignments as well as to attend the supplemental central lab session!
    For information concerning the possibility to voluntarily repeat the exam see here, at bottom.
  • Audience:
    Students in Bachelor of Science in Computer Science (compulsory course)
    Students in Bachelor of Science in Bioinformatics (compulsory course)
    Students in Bachelor of Science in Naturwissenschaftliche Bildung Informatik/Mathematik (compulsory course)
    Students in Bachelor of Science in Information Systems
    Students in Bachelor of Science in Mathematics
  • Prerequisites:
    Module IN0015: Discrete Structures
    Module MA0901: Linear Algebra for Informatics
    Module MA0902: Analysis for Informatics
  • Related and more advanced lectures:
    Complexity Theory (Module IN2007)
  • Office hours:
    see here

Course Contents and Literature

see here.

Slides / Recordings


Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
The design and analysis of computer algorithms
Addison-Wesley Publishing Company, Reading (MA), 1976
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Cliff Stein:
Introduction to algorithms, 2nd ed
MIT Press, 2001
Karin Erk, Lutz Priese:
Theoretische Informatik: Eine umfassende Einführung
Springer-Verlag, Berlin-Heidelberg-New York, 2000
Volker Heun:
Grundlegende Algorithmen
Vieweg, 2000
John E. Hopcroft, R. Motwani, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 2. Ed.
Pearson Education, 2002
Thomas Ottmann, Peter Widmayer:
Algorithmen und Datenstrukturen, 3. Ed.
Spektrum Akademischer Verlag GmbH, Heidelberg-Berlin, 1996
Uwe Schöning:
Theoretische Informatik --- kurzgefasst
Spektrum Akademischer Verlag GmbH, Heidelberg-Berlin, 1997
Ingo Wegener:
Theoretische Informatik
B.G. Teubner, Stuttgart, 1993