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 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 (Thema des zweiten Semesters) befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen. Die Komplexitätstheorie (Thema des zweiten Semesters) 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.

Einführung in die Theoretische Informatik

• Automaten, Sprachen und Berechenbarkeit
• Informale und formale Beweisführung


Endliche Automaten und Reguläre Sprachen

• Deterministische und nichtdeterministische endliche Automaten
• Reguläre Ausdrücke und Typ-3 Grammatiken
• Lexikalische Analyse
• Charakterisierung und Abschlusseigenschaften regulärer Sprachen
• Minimierung von Automaten
• Grenzen regulärer Sprachen (Pumping Lemma)


Kontextfreie Sprachen

• Kontextfreie Grammatiken
• Syntaxanalyse und Semantik
• Pushdown Automaten
• Charakterisierung und Abschlusseigenschaften kontextfreier Sprachen
• Grenzen und Normalformen kontextfreier Sprachen

• 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. Die Übungsblätter werden wöchentlich herausgegeben.