Zielstellung:

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht. Die Automatentheorie und die Theorie der formalen Sprachen (Thema des ersten Semesters) ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können. Die Berechenbarkeitstheorie befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen. Die Komplexitätstheorie untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

Berechenbarkeitsmodelle

• Turingmaschinen
• Registermaschinen
• Rekursive Funktionen
• Typ-0 Grammatiken
• Weitere Berechenbarkeitsmodelle
• Church'sche These


Berechenbarkeitstheorie

• Universelle Turingmaschinen
• Aufzählbarkeit und Entscheidbarkeit
• Diagonalisierung und Problemreduktion
• Unläsbare Probleme


Komplexitätstheorie

• Komplexitätsmaße
• Komplexität von Algorithmen (obere Schranken)
• Komplexität von Problemen (untere Schranken)
• NP-Vollständigkeit

• In der Vorlesung werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Die in der Vorlesung verwendeten Folien werden auf den Servern des Lehrgebiets (wenn möglich im Voraus) bereitgestellt.
• Die Übungen dienen der Vertiefung und Anwendendung der in der Vorlesung vorgestellten Themen. Dies geschieht durch Besprechung von Hausaufgaben und ad hoc Übungsaufgaben, einem 5-Minuten "Quiz" zur Überprüfung eigener Kenntnisse und durch Diskussion von Fragen zur Vorlesung.

• A. Asteroth, C. Baier: Theoretische Informatik, Pearson 2002
• J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson 2002
• Mitschriften von Kommilitonen früherer Semester liegen auf dem Server des Lehrgebiets "Didaktik der Informatik" bereit
  Theorie I   Theorie II
• Folien der Vorlesung

• I. Wegener: Theoretische Informatik, Teubner Verlag 1993
• U. Schöning: Theoretische Informatik - kurzgefaßt, Spektrum-Verlag 1994
• K. Erk, L. Priese: Theoretische Informatik, Springer Verlag 2000
• H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, Prentice-Hall 1998

• Zur Leistungserfassung wird ausschließlich eine abschliessende Klausur herangezogen.
  Die Klausur findet vorraussichtlich in der Woche nach Ende der Vorlesungen (Anfang Februar) statt.
  Eine Nachklausur wird angeboten für Studenten, die in der ersten Klausur durchgefallen sind.
  In dieser Nachklausur kann maximal die Note 4.0 erreicht werden
• Als Mittel der Selbstkontrolle wird eine Probeklausur während einer Vorlesungstunde Ende Dezember angeboten. Das Ergebnis der Probeklausur geht nicht in die Endnote ein. Die Teilnahme an der Probeklausur ist Voraussetzung für die Zulassung zur Klausur.
• Zur Klausur wird zugelassen, wer an der Probeklausur teilnimmt und mindestens 50% der Punkte in den Hausaufgaben erreicht.
• Hausaufgaben werden zwei-wöchentlich auf den Servern des Lehrgebiets bereitgestellt. Gruppen von bis zu 4 Studenten dürfen eine gemeinsame Lösung zur Korrektur einreichen. Die Gruppen müssen sich bis Ende Oktober gebildet haben.
  Zum Lesen der Übungsblätter kann der kostenlose Adobe Acrobat Reader verwendet werden.