| Inhalt | Organisation | Zeit und Ort | Chat | Material | Planung | Abgabe von Übungsblättern | Klausuren |
Theoretische Informatik für Studierende der Medieninformatik (TIMI, SoSe 2025)
Vorlesung, 2(+1)-std., Blanchette; Ü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: Prof. Dr. Jasmin Blanchette
Übung: Elisabeth Lempa, Luca Maio
Die Abgabe der Übungsblätter und die Anmeldung zu den Klausuren erfolgt über Moodle. Der Einschreibeschlüssel für den Kurs lautet TIMI25.
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 A 240 | 29.04.2025 |
| Zentralübung | Mi 12‑14, ca. 2‑wöchig | GSP B 201 | 30.04.2025 |
| Übungsgruppe A | Do 16:00‑17:00 (s.t.) | Richard‑Wagner‑Str. 10 D 105 | 24.04.2025 |
| Übungsgruppe B | Do 17:00‑18:00 (s.t.) | Richard‑Wagner‑Str. 10 D 105 | 24.04.2025 |
Hinweis: An allen gesetzlichen Feiertagen sowie in der Pfingstwoche (09.06. – 13.06.) 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.
Zulip-Server: https://chat.ifi.lmu.de
Stream: TCS-25S-FSK-TIMI
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 Klausuren von 2023:
Reguläre Klausur (Lösungen), Wiederholungsklausur (Lösungen)Die Reguläre Klausur von 2022:
Reguläre Klausur (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 2025 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 2025 ist für die Prüfung im SoSe 2025 verbindlich.
Übungsblätter
| Übungsblatt | Präsenzaufgaben | Klausurvorbereitungs-Aufgaben |
|---|---|---|
| Blatt 0 | Besprechung 24.04. Loesung | - |
| Blatt 1 | Besprechung 02.05.-05.05.* Loesung | Abgabe bis 12.05., 10:00 Loesung |
| Blatt 2 | Besprechung 08.05. Loesung | Abgabe bis 19.05., 10:00 Loesung |
| Blatt 3 | Besprechung 15.05. Loesung | Abgabe bis 26.05., 10:00 Loesung |
| Blatt 4 | Besprechung 22.05. Loesung | Abgabe bis 02.06., 10:00 Loesung |
| Blatt 5 | Besprechung 30.05.-02.06.* Loesung | Abgabe bis 09.06., 10:00 Loesung |
| Blatt 6 | Besprechung 05.06. Loesung | Abgabe bis 23.06., 10:00 Loesung |
| Blatt 7 | Besprechung 20.06.-23.06.* Loesung | Abgabe bis 30.06, 10:00 Loesung |
| Blatt 8 | Besprechung 26.06. Loesung | Abgabe bis 07.07., 10:00 Loesung |
| Blatt 9 | Besprechung 30.06. Loesung | Abgabe bis 14.07., 10:00 Loesung |
| Blatt 10 | Besprechung 10.07. Loesung | Abgabe bis 21.07., 10:00 Loesung |
| Blatt 11 | Besprechung 17.07. Loesung | Abgabe bis 28.07., 10:00 Loesung |
(*) 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
Hinweis: Durchgestrichene Zeilen (z. B.
~~22.04.~~) gelten nur für die FSK‑Vorlesungen. Die TIMI‑Vorlesungen beginnen 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 |
| 09b | 13.1, 13.2 bis Anfang 13.2.2 |
| 09c | 13.2.2–13.2.4, 13.3 |
| 10a | 13.4, 13.5 |
| 10b | 14 |
| 10c | 15 bis Anfang 15.2 |
| 11a | 15.2 |
| 11b | 16 bis Anfang 16.2 |
| 11c | 16.2–16.4 |
| 12b | 16.10–16.13 |
Abgabe von Übungsblättern
Die Übungsblätter müssen jeweils bis 10: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 Betrug gewertet. Die Klausuren werden sich strukturell und inhaltlich an denen von 2024 orientieren, aber wir behalten uns natürlich beliebige Änderungen vor. Die Bearbeitungszeit beträgt 120 Minuten.
Falls Sie einen Nachteilsausgleich in Anspruch nehmen möchten, melden Sie sich bitte mindestens eine Woche im Voraus bei Prof. Dr. Jasmin Blanchette.
Reguläre Klausur
Die reguläre Klausur fand am Donnerstag 31.07.2025 ab 16:00 Uhr statt.
Wiederholungsklausur
Die Wiederholungsklausur fand am Dienstag 30.09.2025 ab 10:00 Uhr statt.