Theoretische Informatik I

• 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 vierten Semesters) befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.

• Die Komplexitätstheorie (Thema des vierten 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.

Inhaltliche Gliederung der Vorlesung

Einführung in die Theoretische Informatik

• 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 Grammatiken

• Pushdown Automaten

• Charakterisierung und Abschlusseigenschaften kontextfreier Sprachen

• Grenzen und Normalformen kontextfreier Sprachen

• Turingmaschinen

• Modelle für Typ-0 und Typ-1 Sprachen

• Eigenschaften von Typ-0 und Typ-1 Sprachen

Ablauf

• In der Vorlesung werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Sie werden ein grösseres Verständnis erreichen, wenn Sie jede Vorlesungsstunde vor- und nachbereiten. Daher werden die in der Vorlesung verwendeten Folien auf den Servern des Lehrgebiets im Voraus bereitgestellt.

• Es werden wöchentlich Übungsblätter herausgegeben, die von den Studierenden zu bearbeite sind schriftlich zur Bewertung durch das Tutorenteam abzugeben sind.

• Es werden wöchentliche Übungen angeboten (siehe Termine). Die Übungen dienen der Vertiefung und Anwendung der in der Vorlesung vorgestellten Themen in einer kleineren Gruppe unter Betreuung einer Tutorin oder eines Tutors. Hier werden Übungsaufgaben gemeinsam bearbeitet und Fragen und Probleme zu den Vorlesungsthemen und den Übungsblättern besprochen.

• Das zusätzliche Tutorium ist eine freiwillige Zusatzveranstaltung, die zur Besprechung allgemeiner Fragen mit dem Dozenten vorgesehen ist.

• Die Sprechstunden dienen der persönlichen Beratung: Hier können Sie spezifische Probleme oder individuelle Schwierigkeiten besprechen.

• Das wichtigste ist jedoch das Selbststudium: Sie werden nur dann wirklich etwas lernen und optimal auf die Abschlussklausur vorbereitet sein, wenn Sie sich selbstständig und regelmaßig mit den Vorlesungsthemen auseinandersetzen und die Übungsblätter bearbeiten.