Vorlesung Theoretische Informatik SoSe 2024

Die Vorlesung gibt eine Einführung in die theoretische Informatik. Sie führt in die Themen endliche Automaten, formale Sprachen und Grammatiken ein und diskutiert den Berechenbarkeitsbegriff. Es schließt sich eine Einführung in die Komplexitätstheorie, speziell die Theorie der NP-Vollständigkeit, an. Behandelt werden abstrakte Modelle von Maschinen und Sprachen, mit deren Hilfe Komplexitätsmaße wie Schrittzahl (Laufzeit) und Speicherbedarf von Algorithmen definiert werden.

Aktuelles

16.04.2024: Veröffentlichung erstes Übungsblatt
17.04.2024: Für die Studierende ohne Account sind die Vorlesungsaufnahmen, Folien und Übung hier verfügbar. Das ist nur eine Übergangslösung.

Vorlesungsmaterialien

Die Vorlesungsmaterialien (Vorlesungsaufzeichnungen, Folien, Übungsaufgaben, Bibliographie) wird über ILIAS bereitgestellt.

Sprache

Die Vorlesung wird auf Deutsch gehalten. Übungen und Klausur sind in deutscher oder englischer Sprache zu bearbeiten.

Lernziel und Vorlesungsinhalt

Die Vorlesung gibt eine eingehende Einführung in die Theoretische Informatik. Neben verschiedenen formalen Präzisierungen des Berechenbarkeitsbegriffs, werden als Themen endliche Automaten, formale Sprachen und Grammatiken, Entscheidbarkeit und Komplexitätstheorie behandelt. Das Lernziel der Vorlesung ist es, Studierende dazu zu befähigen, Konzepte wie Algorithmen, Berechenbarkeit, Komplexität und deren grundsätzliche Bedeutung für die Lösbarkeit von Problemen zu verstehen.

Die Vorlesung richtet sich an Informatik-Studenten im Bachelor-Studiengang. Die Veranstaltung hat einen Umfang von 6 ECTS Punkten.

Kriterien für die Studienleistung

Während des Semesters werden wöchentliche Aufgabenblätter ausgegeben. Um die Studienleistung zu erlangen, müssen mindestens 50% der Übungspunkte erreicht werden. Die Übungsblätter können in Gruppen von drei Studierenden bearbeitet werden. Es ist möglich durch aktive Beteiligung in der Übungsgruppe (z.B. Vorrechnen) Extrapunkte zu erhalten.

Ablauf der Veranstaltung

Die Veranstaltung wird in Präsenz organisiert; Aufzeichnungen der Vorlesung werden zur Verfügung gestellt.

Vorlesung Montag, 16:00 - 18:00 Uhr in 101-00-026
Übungen
- Übungsgruppe 1: Mittwoch 8-10 Uhr, 051-00-006, Christoph Ullinger
- Übungsgruppe 2: Mittwoch 8-10 Uhr, 106-00-007, Julian Schur
- Übungsgruppe 3: Donnerstag 8-10 Uhr, 051-00-031, Sebastian Friedrich
- Übungsgruppe 4: Donnerstag 16-18 Uhr, 051-00-006, Hans Albert
- Übungsgruppe 5: Donnerstag 16-18 Uhr, 051-00-034, Ahmet Ercem Bulut (englisch)
- Übungsgruppe 6: Freitag 8-10 Uhr, 101-01-016/18, Sebastian Friedrich

In der ersten Vorlesungswoche findet kein Übungsbetrieb statt. Jeden Dienstag Abend wird ein Übungsblatt veröffentlicht. Sie haben bis Montag 16:00 Uhr Zeit, die Aufgaben auf dem Übungsblatt zu bearbeiten und Ihre Lösungen auf ILIAS hoch zu laden.

Literatur

M. Sipser: Introduction to the Theory of Computation, Cengage India, 3rd Edition, 2014, ISBN 8131771865
I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9
U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Taschenbuch, 5. Auflage, 2008, Spektrum Akademischer Verlag, Heidelberg. ISBN 3-8274-1824-0
H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, 2. Auflage, 1997, 361 Seiten, kart., Prentice Hall, New Jersey. ISBN 0-13-262478-8
J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, 461 Seiten, kart., Addison Wesley, Bonn. ISBN 3-89319-744-3