LEA

Introduction to Theory of Computation

News

  • 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.

Course

  • 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

April: April 13, 2015 Recording April 16, 2015 Recording
April 20, 2015 Recording April 23, 2015 Recording
April 27, 2015 Recording April 30, 2015 Recording
May: May 4, 2015 Recording May 7, 2015 Recording
May 11, 2015 Recording
May 18, 2015 Recording May 21, 2015 Recording
May 28, 2015 Recording
June: June 1, 2015 Recording
June 8, 2015 Recording June 11, 2015 Recording
June 15, 2015 Recording June 18, 2015 Recording
June 22, 2015 Recording June 25, 2015 Recording
June 29, 2015 Recording
July: July 2, 2015 Recording
July 13, 2015 Recording July 16, 2015 Recording

And here you get everything in one file! 
(Some hints for using the above slides)

Literature

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