Theoretische Informatik II
- Vorlesung, Prof. Dr. Kreitz, Fr. 08:00-10:00, 3.06.H04 (am 14.06. im HPI.HS1)
- Übung G1, Tutor Stefan Neubert, Mo. 9:15-10:45, HPI.A-1.1
- Übung G2, Tutor Tina Beigel, Mo. 9:15-10:45, HPI.A-1.2
- Übung G3, Tutor Anne Gropler, Mo. 13:30-15:00, HPI-A2.1
- Übung G4, Tutorn Hannes Schröder, Mo. 13:30-15:00, HPI-A2.2
- Übung G5, Tutor Charlotte Gerlitz, Di. 10:00-12:00, 3.04.0.02
- Übung G6, Tutor Hannes Schröder, Di. 12:00-14:00, 3.04.0.02
- Übung G7, Tutor Meike Baumgärtner, Mi. 08:00-10:00, 3.01.2.31
- Übung G8, Tutor Charlotte Gerlitz, Mi. 12:00-14:00, 3.06.H01
- Zusatzübung, Prof. Dr. Kreitz, Sebastian Böhne, Do. 10:00-12:00, HPI.HS3 (am 20.06. im H-E.51/52 am 4.7. im 3.06.H06)
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 o NP-vollständige Problem
- Jenseits von NP-vollständigkeit
- Pseudopolynomielle und approximierende Algorithmen
- Probabilistische Lösung nichthandhabbarer Probleme
Literatur
- Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005
- J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson 2002