| Inhalt | Organisation | Zeit und Ort | Chat | Material | Planung | Abgabe von Übungsblättern | Klausuren |
Theoretische Informatik für Studierende der Medieninformatik (TIMI, SoSe 2026)
Vorlesung, 2(+1)-std., Johannsen; Übungen 1-std., Lempa, Maio
Inhalt
Die Vorlesung behandelt Grundlagen der theoretischen Informatik: Sie gibt Einführungen in die Theorie der formalen Sprachen und Automaten sowie in die Berechenbarkeits- und Komplexitätstheorie. Die Veranstaltung orientiert sich inhaltlich und strukturell am Lehrbuch von Schöning (Theoretische Informatik – kurz gefasst). Themen sind:
Automaten und Formale Sprachen:
Deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, KellerautomatenBerechenbarkeit:
Turing-Maschinen, Churchsche These, Unentscheidbarkeit, Halteproblem, ReduktionenKomplexität:
Die Klassen P und NP, NP-vollständige Probleme, Polynomialzeit-Reduktionen
Neben der Vorlesung (2V) und den Übungen (1Ü) wird eine optionale Zentralübung (ca. alle 2 Wochen, 2-stündig) angeboten. Diese dient zum Wiederholen und zum Einüben des Stoffs, aber es wird kein neuer Stoff behandelt.
Organisation
Umfang: 2(+1)+1 Semesterwochenstunden
Vorlesung + Zentralübung: PD Dr. Jan Johannsen
Übung: Elisabeth Lempa, Luca Maio
Bitte melden Sie sich über das LSF zur Veranstaltung an, damit die Belegung und Leistungsverbuchung reibungslos ablaufen kann.
Die Abgabe der Übungsblätter erfolgt über Moodle. Der Einschreibeschlüssel für den Moodle-Kurs lautet TIMI26.
Zeit und Ort
Formale Sprachen und Komplexität Die Vorlesung findet integriert in der größeren Veranstaltung
Formale Sprachen und Komplexität(FSK) statt. Daher ist für die zweistündige Vorlesung ein dreistündiger Zeitslot reserviert, von dem nicht alle Stunden für die Theoretische Informatik für Studierende der Medieninformatik verwendet werden. Welche Vorlesungsteile relevant sind, ist der Planung zu entnehmen.
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| Vorlesung | Di 14‑17 | GSP 1 A 240 | 14.04.2026 |
| Zentralübung | Mi 12‑14, ca. 2‑wöchig | GSP 1 A 240 | 15.04.2026 |
| Übungsgruppe A | Do 16:00‑17:00 (s.t.) | GSP 1 E 006 | 16.04.2026 |
| Übungsgruppe B | Do 17:15‑18:15 (s.t.) | GSP 1 E 006 | 16.04.2026 |
Hinweis: An allen gesetzlichen Feiertagen sowie in der Pfingstwoche (25.05. – 29.05.) finden keine Tutorien statt.
Chat
Für die Vorlesung gibt es einen Zulip-Chatraum, in dem Sie sowohl organisatorische als auch inhaltliche Fragen stellen können. Bitte verwenden Sie wenn möglich diesen Chatraum, anstatt uns Emails zu schreiben, damit Ihre Mitstudierenden auch von den Antworten profitieren können.
Material
Die Klausuren von 2025:
Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)Die Klausuren von 2024:
Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)Die FSK-Klausuren von 2019:
Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)Die LMUcast-Playlist aus den SoSe 2021/2022 ist hier verfügbar. Die Nutzung dieser Videos erfolgt auf eigene Verantwortung der Studierenden. Der Inhalt der Vorlesung im SoSe 2026 kann von den Inhalten in den vorherigen Jahren abweichen. Insbesondere werden die Themen DFA-Minimierung und linear beschränkte Turingmaschinen anders behandelt. Allein der Inhalt der Vorlesung im SoSe 2026 ist für die Prüfung im SoSe 2026 verbindlich.
Übungsblätter
| Übungsblatt | Präsenzaufgaben (Besprechung / Lösung) | Klausurvorbereitungs-Aufgaben (Abgabe / Lösung) |
|---|---|---|
| Blatt 0 | Besprechung 16.04. Loesung | – |
| Blatt 1 | Besprechung 23.04. | Abgabe bis 05.05., 14:00 |
| Blatt 2 | Besprechung 30.04. | Abgabe bis 12.05, 14:00 |
| Blatt 3 | Besprechung 07.05. | Abgabe bis 19.05., 14:00 |
| Blatt 4 | Besprechung 15.05‑18.05. (*) | Abgabe bis 02.06., 14:00 |
| Blatt 5 | Besprechung 21.05. | Abgabe bis 09.06., 14:00 |
| Blatt 6 | Besprechung 05.06‑08.06. (*) | Abgabe bis 16.06., 14:00 |
| Blatt 7 | Besprechung 11.06. | Abgabe bis 23.06., 14:00 |
| Blatt 8 | Besprechung 18.06. | Abgabe bis 30.06., 14:00 |
| Blatt 9 | Besprechung 25.06. | Abgabe bis 07.07., 14:00 |
| Blatt 10 | Besprechung 02.07. | Abgabe bis 14.07., 14:00 |
| Blatt 11 | Besprechung 09.07. | Abgabe bis 21.07., 14:00 |
| Blatt 12 | Besprechung 16.07. | Abgabe bis 28.07., 14:00 |
(*) Aufgrund von Feiertagen entfallen die Übungen an einigen Donnerstagen. Sie können in diesen Wochen stattdessen die FSK-Übungen Montags oder Freitags besuchen.
Literatur
Uwe Schöning: Theoretische Informatik – kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008
Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002
John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3. Auflage, 2006
Ingo Wegener: Theoretische Informatik – eine algorithmenorientierte Einführung, 3. Auflage, Teubner Verlag, 2005
Nützliche Webseiten
Automata Tutor: ein Online-Werkzeug zum Lernen von Automatentheorie
Online Turing Machine Simulator: Online-Werzkeug zum Simulieren von Turingmaschinen
Planung
| Termin | Inhalte |
|---|---|
| 14.04. | Vorlesung 1a: Begrüßung, Organisatorisches, Inhaltsübersicht und Grundlagen Vorlesung 1b: Grammatiken und die Chomsky‑Hierarchie Vorlesung 1c: Weitere Grammatikbegriffe sowie Eigenschaften von Sprachen |
| 15.04. | Zentralübung 1: Wörter, Beweise, Grammatiken, Chomsky‑Hierarchie |
| 21.04. | Vorlesung 2b: Deterministische endliche Automaten Vorlesung 2c: Minimierung von deterministischen endlichen Automaten |
| 28.04. | Vorlesung 3a: Regularität von deterministischen endlichen Automaten und nichtdeterministische endliche Automaten Vorlesung 3b: Determinisierung von endlichen Automaten Vorlesung 3c: Nichtdeterministische endliche Automaten mit Epsilon‑Übergängen |
| 29.04. | Zentralübung 2: DFAs, NFAs, Äquivalenz |
| 05.05. | Vorlesung 4a: Reguläre Ausdrücke Vorlesung 4b: Das Pumping‑Lemma für reguläre Sprachen Vorlesung 4c: Eigenschaften von regulären Sprachen |
| 19.05. | Vorlesung 6b: Der CYK‑Algorithmus Vorlesung 6c: Kellerautomaten |
| 20.05. | Zentralübung 3: Reguläre Ausdrücke, Abschluss, Pumping‑Lemma |
| "Pfingstdienstag" (vorlesungsfrei) | |
| 02.06. | Vorlesung 7b: Turingmaschinen |
| 03.06. | Zentralübung 4: Minimierung, PDAs, Turingmaschinen |
| 09.06. | Vorlesung 8b: Intuitive und Turing‑Berechenbarkeit |
| 17.06. | Zentralübung 5: Berechenbarkeit, CYK, |
| 23.06. | Vorlesung 10a: Unentscheidbarkeit und das spezielle Halteproblem Vorlesung 10b: Reduktion und der Satz von Rice Vorlesung 11a: Das Postsche Korrespondenzproblem |
| 30.06. | Vorlesung 11a: Laufzeitkomplexität und die Klassen P und NP Vorlesung 11b: NP‑Vollständigkeit Vorlesung 11c: Eigenschaften der Klassen P und NP |
| 01.07. | Zentralübung 6: Reduktionen, Rice, PCP, |
| 07.07. | Vorlesung 12a: NP‑Vollständigkeit von SAT Vorlesung 12b: NP‑Vollständigkeit von 3‑CNF‑SAT Vorlesung 12c: NP‑Vollständigkeit von CLIQUE, INDEPENDENT‑SET und VERTEX‑COVER |
| 14.07. | Vorlesung 13b: NP‑Vollständigkeit von GRAPH‑COLORING, (UN)DIRECTED‑HAMILTON‑CYCLE und TRAVELING‑SALESPERSON Vorlesung 13c: Wiederholung und Fragestunde |
| 15.07. | Zentralübung 7: CLIQUE, GRAPH‑COLORING, |
Hinweis: Durchgestrichene Zeilen (z. B.
22.04.) gelten nur für die FSK‑Vorlesungen. Die TIMI‑Vorlesungen beginnen/enden später, jeweils etwa eine Stunde pro Teil.
Abgabe von Übungsblättern
Die Übungsblätter müssen jeweils bis 14:00 Uhr am angegebenen Tag auf Moodle abgegeben werden. Verspätete Abgaben sind nicht möglich. Lösungsvorschläge der Klausurvorbereitungs-Aufgaben werden jeweils nach Ende der Abgabefrist unter Material veröffentlicht.
Klausuren
Bei den Klausuren sind Hilfsmittel nicht erlaubt. Auch das Mitführen ausgeschalteter elektronischer Geräte wird als Betrugsversuch gewertet.
Falls Sie einen Nachteilsausgleich in Anspruch nehmen möchten, melden Sie sich bitte mindestens eine Woche im Voraus bei Jan Johannsen.
Reguläre Klausur
Die reguläre Klausur wird am 05.08.2026 ab 14:00 Uhr stattfinden. Zur Teilnahme ist eine Anmeldung über das LSF notwendig.
Wiederholungsklausur
Teilnahme an der Wiederholungsklausur ist auch ohne Teilnahme an der regulären Klausur möglich. Das Datum der Wiederholungsklausur ist noch nicht bekannt.