| Aktuelles | Inhalt | Organisation | Zeit und Ort | Vorlesungs-Chat | Planung | Material | Übungen | Klausur |
Theoretische Informatik für Medieninformatiker
Vorlesung, 2-std., Blanchette; Übungen 1-std., Kondylidou, Limperg
Aktuelles
-
Wichtig: Die Nachholklausur findet am Montag, 25. September, ab 15 Uhr statt und wird 90 Minuten dauern. Wenn Sie an der Nachholklausur teilnehmen möchten, müssen Sie sich bis zum 13. September anmelden.
-
Die Klausur von 2022 sowie die FSK-Klausuren von 2019 sind jetzt unter Material verfügbar.
-
Die Klausur wird am 02.08. ab 16 Uhr stattfinden und 90 Minuten dauern. Siehe die Seite der Studiengangskoordination für Details.
-
Bitte melden Sie sich zum Vorlesungs-Chat an und stellen Sie Fragen bevorzugt dort, anstatt uns Emails zu schreiben.
-
Im Rahmen der Lehrveranstaltung Formale Sprachen und Komplexität gibt es ca. alle zwei Wochen eine Zentralübung, die für FSK gemeint ist. TIMI-Teilnehmer sind trotzdem auch willkommen. Siehe die FSK-Seite für Details.
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 nicht-deterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Kellerautomaten -
Berechenbarkeit:
Turing-Maschinen, Churchsche These, Unentscheidbarkeit, Halteproblem, Reduktion -
Komplexitätstheorie:
Die Klassen P und NP, NP-vollständige Probleme
Organisation
-
Umfang: 2+1 Semesterwochenstunden
-
Vorlesung: Prof. Dr. Jasmin Blanchette
-
Übung: Lydia Kondylidou, Jannis Limperg
Zeit und Ort
Die Vorlesung findet integriert in der größeren Veranstaltung Formale Sprachen und Komplexität statt. Daher ist für die 2-stündige Vorlesung ein dreistündiger Zeitslot reserviert, von dem nicht alle Stunden für die Theoretische Informatik für die Medieninformatik verwendet werden. Welche (Teil-)Vorlesungen relevant sind, sind der Planung zu entnehmen.
Für die Übungsgruppen müssen Sie sich über Moodle registrieren.
| Veranstaltung | Zeit | Ort | Datum |
|---|---|---|---|
| Vorlesung | Di 14-17 | M 018, Geschw.-Scholl-Pl. 1 | ab 18.04.2023 |
| Ersatzvorlesung | Mi 12-14 | A 240, Geschw.-Scholl-Pl. 1 | am 31.05.2023 |
| Übungsgruppe 1 | Do 14-15 s.t. | D Z005, Geschw.-Scholl-Pl. 1 | ab 20.04.2023 |
| Übungsgruppe 2 | Do 15-16 s.t. | D Z005, Geschw.-Scholl-Pl. 1 | ab 20.04.2023 |
Vorlesungs-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-23S-FSK-TIMI
Material
-
Die Vorlesungsfolien und die Übungsblätter finden Sie unten.
-
Die LMU-Cast-Playlist aus den SoSe 2021/2022 ist hier verfügbar. Die Nutzung der Videos aus dem Vorjahr erfolgt auf eigene Verantwortung der Studierenden. Der Inhalt der Vorlesung im SoSe 2023 kann von den Inhalten in den vorherigen Jahren abweichen. Allein der Inhalt der Vorlesung im SoSe 2023 ist für die Prüfung im SoSe 2023 verbindlich.
-
Die Klausur von 2022: Klausur, Klausur mit Lösungen. Die Klausur dieses Jahr wird sich strukturell und inhaltlich an der von 2022 orientieren, aber wir behalten uns natürlich beliebige Änderungen vor. Die Klausur wird wieder 90 Minuten dauern.
-
Die FSK-Klausuren von 2019: Klausur, Klausur mit Lösungen, Nachholklausur, Nachholklausur mit Lösungen.
Literatur (Auswahl)
-
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
Übungen
Die Übungsblätter müssen jeweils bis 10:00 Uhr am angegebenen Tag auf Moodle abgegeben werden. Verspätete Abgaben sind nicht möglich.
| Blatt | Abgabe am | Aufgaben | Lösungen |
|---|---|---|---|
| 0 | keine Abgabe | timi_blatt00.pdf | timi_loesung_blatt00.pdf |
| 1 | 26.04. | timi_blatt01.pdf | timi_loesung_blatt01.pdf |
| 2 | 03.05. | timi_blatt02.pdf | timi_loesung_blatt02.pdf |
| 3 | 10.05. | timi_blatt03.pdf | timi_loesung_blatt03.pdf |
| 4 | 17.05. | timi_blatt04.pdf | timi_loesung_blatt04.pdf |
| 5 | 24.05. | timi_blatt05.pdf | timi_loesung_blatt05.pdf |
| 6 | 31.05. | timi_blatt06.pdf | timi_loesung_blatt06.pdf |
| 7 | 07.06. | timi_blatt07.pdf | timi_loesung_blatt07.pdf |
| 8 | 14.06. | timi_blatt08.pdf | timi_loesung_blatt08.pdf |
| 9 | 21.06. | timi_blatt09.pdf | timi_loesung_blatt09.pdf |
| 10 | 28.06. | timi_blatt10.pdf | timi_loesung_blatt10.pdf |
| 11 | 05.07. | timi_blatt11.pdf | timi_loesung_blatt11.pdf |
| 12 | 12.07. | timi_blatt12.pdf | timi_loesung_blatt12.pdf |
| 13 | keine Abgabe | timi_blatt13.pdf | timi_loesung_blatt13.pdf |
Klausur
Die Nachholklausur findet am Montag, 25. September 2023 statt. Die Raumaufteilung teilen wir vor der Klausur über Moodle mit. Hilfsmittel sind nicht erlaubt.
Sie können sich bis zum 13. September 2023 auf Moodle zur Nachholklausur anmelden. Sie können nur an der Nachholklausur teilnehmen, wenn Sie sich rechtzeitig angemeldet haben. Wenn Sie sich angemeldet haben und es sich anders überlegen, können Sie sich bis zum 21. September 2023 wieder abmelden.
Die reguläre Klausur fand am 02. August 2023 statt.
Artikelaktionen