Links und Funktionen


Inhaltsbereich
Aktuelles | Inhalt | Organisation | Zeit und Ort | Vorlesungs-Chat | Planung | Material | Übungen | Prüfung

Theoretische Informatik für Medieninformatiker

Vorlesung, 2-std., Blanchette; Übungen 1-std., Kondylidou, Limperg

Aktuelles

  • Die Klausur wird am 02.08. ab 16 Uhr stattfinden und 90 Minuten dauern. Siehe die Seite der Studiengangskoordination für Details.

  • Die Klausuren von 2022 sind jetzt unter Material verfügbar.

  • 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

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

  • Skript (zuletzt aktualisiert am 17.05.2023)

  • 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 Klausuren von 2022: Klausur, Klausur mit Lösungen, Nachholklausur, Nachholklausur 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.

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

Planung

Termin Inhalte
18.04. 14-16 Uhr 01. Begrüßung, Organisatorisches, Inhaltsübersicht und Grundlagen
02. Grammatiken und die Chomsky-Hierarchie
25.04. 14-16 Uhr 04. Grammatiken: Abschlusseigenschaften und Entscheidungsprobleme
05. Deterministische endliche Automaten
02.05. 14-16 Uhr 07. DFAs akzeptieren reguläre Sprachen, Nichtdeterministische endliche Automaten
08. Determinisierung von endlichen Automaten
09.05. 10. Reguläre Ausdrücke
11. Der Satz von Kleene
12. Das Pumping-Lemma für reguläre Sprachen
16.05. 15-17 Uhr 14. Minimierung von deterministischen endlichen Automaten
15. Reguläre Sprachen: Abschlusseigenschaften und Entscheidbarkeitsresultate
23.05. Keine Vorlesung
30.05. Pfingstdienstag: Vorlesungsfrei (wird am 31.05. z.T. nachgeholt)
31.05. 12-14 Uhr
A 240
19. Der CYK-Algorithmus zum effizienten Entscheiden des Wortproblems für kontextfreie Sprachen
20. Kontextfreie Sprachen: Kellerautomaten
06.06. 15-17 Uhr 22. Deterministisch kontextfreie Sprachen und Eigenschaften
23. Turingmaschinen und Typ 1- und Typ 0-Sprachen
13.06. 16-17 Uhr 26. Intuitive und Turing-Berechenbarkeit
20.06. Keine Vorlesung
27.06. 15-17 Uhr 31. Entscheidbarkeit, Unentscheidbarkeit und das Halteproblem
32. Reduktion und der Satz von Rice
04.07. 14-17 Uhr 33. Das Postsche Korrespondenzproblem
34. Laufzeitkomplexität und die Klassen P und NP
35. NP-Vollständigkeit
11.07. 14-17 Uhr 36. Der Satz von Cook
37. NP-Vollständigkeit von 3-CNF-SAT
38. NP-Vollständigkeit von CLIQUE, INDEPENDENT-SET und VERTEX-COVER
18.07. 14-17 Uhr 39. NP-Vollständigkeit von SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING
40. NP-Vollständigkeit von (UN-)DIRECTED-HAMILTON-CYCLE, TRAVELING-SALESPERSON und GRAPH-COLORING
41. Wiederholung und Fragestunde

Ü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 bald™
8 14.06. bald™ bald™
9 21.06. bald™ bald™
10 28.06. bald™ bald™
11 05.07. bald™ bald™
12 12.07. bald™ bald™
13 keine Abgabe bald™ bald™

Klausur

Wird noch bekanntgegeben.

Artikelaktionen


Funktionsleiste