| 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
Übungsblätter werden hier zur Verfügung gestellt. (*) 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.
Korrespondenz zwischen Vorlesungsteilen und Skript
| Vorlesungsteil | Abschnitte im Skript |
|---|---|
| 1a | 1, 2.1 (Hausaufgabe: 2.2–2.5) |
| 1b | 3.1, 3.2 bis Anfang 3.2.2 |
| 1c | 3.2.2, 3.3–3.6 |
| 2b | 4.1 |
| 2c | 4.11 |
| 3a | 4.2, 4.3 |
| 3b | 4.4, 4.5 |
| 3c | 4.6 |
| 4a | 4.7, 4.8 |
| 4b | 4.12, 4.13 |
| 4c | 4.9 |
| 6b | 5.2 bis Anfang 5.2.1, 5.6 |
| 6c | 5.7 bis Anfang 5.7.2, 5.7.2.2 |
| 7b | 5.8 |
| 7c | 6.2, 6.3 bis Anfang 6.3.1, 7 |
| 8c | 8, 9.1, 9.2 |
| 10b | 13.1, 13.2 bis Anfang 13.2.2 |
| 10c | 13.2.2–13.2.4, 13.3 |
| 11a | 13.4, 13.5 |
| 11b | 14 |
| 11c | 15 bis Anfang 15.2 |
| 12a | 15.2 |
| 12b | 16 bis Anfang 16.2 |
| 12c | 16.2–16.4 |
| 13b | 16.10–16.13 |
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
Informationen zur regulären Klausur werden hier bekanntgegeben.
Wiederholungsklausur
Informationen zur Wiederholungsklausur werden hier bekanntgegeben.