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.
Gliederung der Theoretischen Informatik II
- Berechenbarkeitstheorie
- Turingmaschinen
- Rekursive Funktionen
- Lambda-Kalkül und arithmetische Repräsentierbarkeit
- Die Churchsche These
- Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit
- Unlösbare Probleme
- Komplexitätstheorie
- Konkrete Komplexitätsanalyse
- Komplexitätsklassen
- Handhabbarkeit: das P - NP Problem
- NP-vollständige Probleme
- Jenseits von NP-vollständigkeit
- Pseudopolynomielle und approximierende Algorithmen
- Probabilistische Lösung nichthandhabbarer Probleme
Lehrveranstaltungen
- 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 (Gruppen-)Übungen dienen der Vertiefung und Anwendung der in der Vorlesung vorgestellten Themen. Dies geschieht durch Bearbeitung von ad hoc Übungsaufgaben unter Betreuung von Tutoren, einem 5-Minuten "Quiz" zur Überprüfung eigener Kenntnisse, durch Diskussion von Fragen zur Vorlesung, und durch die Korrektur von Lösungen zu Hausaufgaben. Die Übungsblätter werden wöchentlich herausgegeben.
- In der Hörsaalübung werden Lösungen zu den Hausaufgaben vorgestellt und ausführlich besprochen.
- Das Tutorium ist eine freiwillige Zusatzveranstaltung, die zur Besprechung allgemeiner Fragen vorgesehen ist.
- Im Kontrast zum Tutorium dienen die Sprechstunden der persönlichen Beratung. Das Ziel ist dabei vor allem Optimierung des individuellen Lernstils und die Klärung von spezifischen Schwierigkeiten.
