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.
Die Veranstaltung ist prinzipiell für Studenten des ersten Semesters geeignet, setzt jedoch ein gutes Verständnis mathematischer Konzepte und Methoden voraus. Für die meisten Studenten ist es daher sinnvoller, zunächst an den entsprechenden Mathematikveranstaltungen teilzunehmen und die theoretische Informatik erst im dritten Semester zu belegen.
Gliederung der Theoretischen Informatik I
- Einführung in die Theoretische Informatik
- Endliche Automaten und Reguläre Sprachen
- Deterministische und nichtdeterministische endliche Automaten
- Reguläre Ausdrücke und Typ-3 Grammatiken
- Charakterisierung und Abschlusseigenschaften regulärer Sprachen
- Minimierung von Automaten
- Grenzen regulärer Sprachen (Pumping Lemma)
- Kontextfreie Sprachen
- Kontextfreie Grammatiken
- Pushdown Automaten
- Charakterisierung und Abschlusseigenschaften kontextfreier Sprachen
- Grenzen und Normalformen kontextfreier Sprachen
- Allgemeine und kontextsensitive Sprachen
- Turingmaschinen
- Modelle für Typ-0 und Typ-1 Sprachen
- Eigenschaften von Typ-0 und Typ-1 Sprachen
Lehrveranstaltungen
- 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.
