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 mehrere äquivalente präzise Fassungen 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. Bernhard Nebel, Prof. Dr. Andreas Podelski, Rolf-David Bergdoll, Dominik Klumpp
Lecture	Mittwoch 16:00-16:45 Fragestunde, Gebäude 101 Raum HS 00-026 oder via Zoom
Exercises	Montag 14:00 - 15:00, Gebäude 051 Raum SR 00-006 (Tilo) Montag 15:00 - 16:00, Gebäude 051 Raum SR 00-006 (Ioannis) Dienstag 12:00 - 13:00, Gebäude 101 Raum SR 00-010/014 (Simon) Dienstag 13:00 - 14:00, Gebäude 101 Raum SR 00-010/014 (Jonathan) Mittwoch 12:00 - 13:00, Gebäude 106 Raum 00-007 (Kerstin) Mittwoch 13:00 - 14:00, Gebäude 106 Raum 00-007 (Christina)
Exam	TBA
Language	Deutsch
ILIAS	https://ilias.uni-freiburg.de/goto.php?target=crs_2604000&client_id=unifreiburg
Course Catalog	Theoretische Informatik (Vorlesung) Theoretische Informatik (Übung)

Aktuelles

11. 04. 2022: Website online

Vorlesungsmaterialien

Die Vorlesungsmaterialien (Vorlesungsaufzeichnungen, Folien, Übungsaufgaben, Bibliographie) werden ab 22.4.2022 über ILIAS bereitgestellt.

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 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, 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. Die Übungsblätter können in Gruppen von 2 Studierenden bearbeitet werden. Zum Finden von Übungsaufgabenpartern bieten wir ein Partnerroulette an, an dem Sie, wenn gewünscht, teilnehmen können.

Ablauf der Veranstaltung

Wir werden in diesem Semester die Lehre wieder in Teilen als Präsenzlehrveranstaltung organisieren. Die online-Studierbarkeit bleibt aber gewährleistet.

Die Veranstaltung folgt dabei dem Prinzip des inverted classroom. Das heißt, wir werden jede Woche (am Freitag um 8 Uhr vor der aktuellen Vorlesungswoche, erstmals am 22.4.) die Vorlesungsfolien und Videos zur Verfügung stellen. Dies werden 8 Videos von ca. 10-15 Minuten Länge sein. Zusätzlich wird es zu jedem Video ein Quiz mit rund 4 Fragen geben, das Sie zur Reflektion über den Stoff nutzen können. Diese Quiz werden auf der Plattform QuizAcademy gehostet und sind über einen Browser oder über Smartphone-Apps erreichbar. Die Teilnahme ist völlig anonym.

Jeden Mittwoch von 16:00 bis 16:45 werden wir eine Fragestunde durchführen. Diese wird in Präsenz stattfinden, aber auch die Teilnahme per Zoom-Videokonferenz wird möglich sein. Wir werden dabei immer ein Live-Quiz durchführen, bei dem Sie über die o.g. Plattform teilnehmen können. Der wesentliche Aspekt der Fragestunde ist jedoch, dass Fragen aus der Vorlesung geklärt werden können. Dabei werden wir auf Fragen zurück greifen, die im ILIAS-Forum gestellt werden (bis Mittwochmorgen um 10:00). Zusätzlich gehen wir natürlich auf Fragen ein, die während der Fragestunde gestellt werden.

Es gibt wie jedes Semester Übungen, die Sie bearbeiten sollten. Die Veröffentlichung in ILIAS erfolgt immer am Freitag um 8:00 Uhr. Die Abgabe erfolgt über ILIAS, jeweils am Freitag der folgenden Woche bis 23:00. Wenn möglich sollten Sie in Gruppen von zwei Studierenden arbeiten.

Montag (14:00 - 15:00, 15:00 - 16:00), Dienstag (12:00 - 13:00, 13:00 - 14:00) sowie Mittwoch (12:00 - 13:00, 13:00 - 14:00) werden Tutorien angeboten, in denen die Musterlösungen vorgestellt werden und auf Fragen zu dem Stoff der Vorlesung eingegangen wird. Die Tutorien sind als reine Präsenzveranstaltungen geplant, ohne Möglichkeit zur online-Teilnahme.

Sowohl beim ILIAS-Forum als auch bei den QuizAcademy-Quiz sowie in den Zoom-Videokonferenzen können Sie mit Pseudonymen teilnehmen. Ihre personenbezogenen Daten werden also in diesem Kontext nicht gespeichert. Es werden weder die Fragestunde noch die Tutorien aufgezeichnet.

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