Theoretische Informatik (Lecture)

Die Vorlesung gibt eine Einführung in die theoretische Informatik. Sie führt in die Themen endliche Automaten, formale Sprachen und Grammatiken ein und liefert eine präzise Fassung des Berechenbarkeitsbegriffs. 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 präzise definiert werden.

Course Type	Vorlesung
Instructors	Prof. Dr. Andreas Podelski, Frank Schüssele, Marcel Ebbinghaus
Lecture	Dienstag 16:00-18:00, Gebäude 101 Raum HS 00-026
Exercises	Mittwoch 12:00 - 14:00, Gebäude 101 Raum SR 01-009/13 Donnerstag 08:00 - 10:00, Gebäude 051 Raum SR 00-006 Donnerstag 12:00 - 14:00, Gebäude 101 Raum SR 00-010/14 Freitag 08:00 - 10:00, Gebäude 101 Raum SR 01-016/18 Freitag 10:00 - 12:00, Gebäude 051 Raum R 03-026 Freitag 12:00 - 14:00, Gebäude 101 Raum SR 01-009/13
Exam	Schriftliche Klausur am 7. August 2025, 9:00 Uhr, in Gebäude 101 Sie haben 2 Stunden für die Bearbeitung der Klausur. Es sind keinerlei Hilfsmittel zugelassen.
Language	Deutsch
ILIAS	(Link folgt) In HisInOne angemeldete Studierende werden von uns zum ILIAS-Kurs hinzugefügt. Sollten Sie bis zum 22. April nicht hinzugefügt worden sein, senden Sie bitte eine Email an Frank Schüssele oder Marcel Ebbinghaus.
Course Catalog	Theoretische Informatik (Vorlesung) Theoretische Informatik (Übung)

Aktuelles

23./24./25. April: Erste Tutorate
22. April: Vorlesungsbeginn
16. April ILIAS-Kurs online
10. April 2025: Website online

Vorlesungsmaterialien

Ein Skript mit den Inhalten der Vorlesung ist auf ILIAS verfügbar.

Sprache

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

Lernziel und Vorlesungsinhalt

Die Vorlesung gibt eine eingehende Einführung in die Theoretische Informatik. Neben einer formalen Präzisierung 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, intuitive Konzepte wie Algorithmen, Berechenbarkeit, Komplexität formal und präzise zu fassen und deren grundsätzliche Bedeutung für die Lösbarkeit von Problemen mit Hilfe von Rechnern zu verstehen.

Voraussetzungen

Die Vorlesung richtet sich an Informatik-Studenten im Bachelor-Studiengang. Vorausgesetzt werden informatische und mathematische Grundkenntnisse entsprechend den Vorlesungen Informatik I, Informatik II, Logik für Informatiker und Diskrete algebraische Strukturen/Mathematik II für Informatiker.

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.

Bitte geben Sie Ihre Lösungen zu den Übungsblättern einzeln ab, Gruppenabgaben sind nicht erlaubt. Sie dürfen sich gerne mit Ihren Kommiliton*innen über die Übungen, Lösungsansätze etc austauschen und diskutieren. Das Abschreiben der Lösungen ist hingegen nicht erlaubt.

Ablauf der Veranstaltung

Die Vorlesung findet jeden Dienstag von 16:00 - 18:00 Uhr in Präsenz statt. Wir werden dabei immer ein Live-Quiz mit Fragen zur Vorlesung der vorangegangen Woche durchführen. Diese Quiz werden auf der Plattform QuizAcademy gehostet und sind über einen Browser oder über Smartphone-Apps erreichbar. Die Teilnahme ist völlig anonym.

Jede Woche wird am Mittwoch Vormittag ein Übungsblatt auf ILIAS veröffentlicht. Sie haben bis am darauffolgenden Dienstag 16:00 Zeit, die Aufgaben auf dem Übungsblatt zu bearbeiten und Ihre Lösungen auf ILIAS hochzuladen.

Mittwoch, Donnerstag und Freitag finden Tutorate statt, in denen die Lösungen der Aufgabenblätter besprochen werden, und auf Fragen zum Stoff der Vorlesung eingegangen wird. Wir möchten Sie dazu ermutigen, in den Präsenzübungen Ihre Lösungen zu präsentieren, und aktiv an der Diskussion teilzunehmen. Die Tutorate finden als reine Präsenzveranstaltungen statt, ohne Möglichkeit zur online-Teilnahme und ohne Aufzeichnungen.

Bitte beachten Sie: Die Tutorate beginnen bereits in der ersten Vorlesungswoche, d.h. am 23./24./25. April!

Literatur

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