Links und Funktionen


Inhaltsbereich
Inhalt | Organisation | Zeit und Ort | Chat | Material | Planung | Abgabe von Übungsblättern | Klausuren

Theoretische Informatik für Studierende der Medieninformatik (TIMI)

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, Kellerautomaten

  • Berechenbarkeit:
    Turing-Maschinen, Churchsche These, Unentscheidbarkeit, Halteproblem, Reduktionen

  • Komplexitä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

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

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

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

Übungsblätter

Übungsblatt Präsenzaufgaben Klausurvorbereitungs-Aufgaben
Blatt 0 Besprechung 24.04. -
Blatt 1 Besprechung 02.05.-05.05.* Abgabe bis 12.05., 10:00
Blatt 2 Besprechung 08.05. Abgabe bis 19.05., 10:00
Blatt 3 Besprechung 15.05. Abgabe bis 26.05., 10:00
Blatt 4 Besprechung 22.05. Abgabe bis 02.06., 10:00
Blatt 5 Besprechung 30.05.-02.06.* Abgabe bis 09.06., 10:00
Blatt 6 Besprechung 05.06. Abgabe bis 23.06., 10:00
Blatt 7 Besprechung 20.06.-23.06.* Abgabe bis 30.06, 10:00
Blatt 8 Besprechung 26.06. Abgabe bis 07.07., 10:00
Blatt 9 Besprechung 30.06. Abgabe bis 14.07., 10:00
Blatt 10 Besprechung 10.07. Abgabe bis 21.07., 10:00
Blatt 11 Besprechung 17.07. Abgabe bis 27.07., 10: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

Planung

Durchgestrichene Vorlesungsteile sind nur für FSK relevant. Die TIMI-Vorlesungsteile beginnen entsprechend später, wobei jeder Vorlesungsteil ca. eine Stunde dauert.

Termin Inhalte
22.04. "Osterdienstag" (vorlesungsfrei)
29.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
30.04. Zentralübung 1: Wörter, Beweise, Grammatiken, Chomsky Hierarchie
06.05. Vorlesung 2a: Grammatikbeispiele, Mehrdeutigkeit und Entfernen von Epsilon-Produktionen
Vorlesung 2b: Deterministische endliche Automaten
Vorlesung 2c: Minimierung von deterministischen endlichen Automaten
13.05. 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
20.05. Vorlesung 4a: Reguläre Ausdrücke
Vorlesung 4b: Das Pumping-Lemma für reguläre Sprachen
Vorlesung 4c: Eigenschaften von regulären Sprachen
21.05. Zentralübung 2: DFAs, NFAs, Äquivalenz
27.05. Vorlesung 5a: Der Satz von Myhill und Nerode
Vorlesung 5b: Die Chomsky-Normalform
Vorlesung 5c: Das Pumping-Lemma für kontextfreie Sprachen
28.05. Zentralübung 3: Reguläre Ausdrücke, Abschluss, Pumping-Lemmas
03.06. Vorlesung 6a: Die Greibach-Normalform und Eigenschaften von kontextfreien Sprachen
Vorlesung 6b: Der CYK-Algorithmus
Vorlesung 6c: Kellerautomaten
10.06. "Pfingstdienstag" (vorlesungsfrei)
17.06. Vorlesung 7a: Äquivalenz von kontextfreien Sprachen und von Kellerautomaten
Vorlesung 7b: Deterministische Kellerautomaten
Vorlesung 7c: Turingmaschinen
18.06. Zentralübung 4: Minimierung, PDAs, Turingmaschinen
24.06. Vorlesung 8a: Linear beschränkte Turingmaschinen (Fortsetzung)
Vorlesung 8b: Entscheiden des Wortproblems für Typ 1-Grammatiken
Vorlesung 8c: Intuitive und Turing-Berechenbarkeit
25.06. Zentralübung 5: Berechenbarkeit, CYK, Myhill-Nerode
01.07. Vorlesung 09a: Primitiv und my-rekursive Funktionen
Vorlesung 09b: Unentscheidbarkeit und das Halteproblem
Vorlesung 09c: Reduktion und der Satz von Rice
08.07. Vorlesung 10a: Das Postsche Korrespondenzproblem
Vorlesung 10b: Laufzeitkomplexität und die Klassen P und NP
Vorlesung 10c: NP-Vollständigkeit
09.07. Zentralübung 6: Reduktionen, Rice, PCP, Rekursion
15.07. Vorlesung 11a: NP-Vollständigkeit von SAT
Vorlesung 11b: NP-Vollständigkeit von 3-CNF-SAT
Vorlesung 11c: NP-Vollständigkeit von CLIQUE, INDEPENDENT-SET und VERTEX-COVER
22.07. Vorlesung 12a: NP-Vollständigkeit von SET-COVER, SUBSET-SUM, KNAPSACK, PARTITION und BIN-PACKING
Vorlesung 12b: NP-Vollständigkeit von GRAPH-COLORING, (UN)DIRECTED-HAMILTON-CYCLE und TRAVELING-SALESPERSON
Vorlesung 12c: Wiederholung und Fragestunde
23.07. Zentralübung 7: CLIQUE, GRAPH-COLORING, KNAPSACK

Korrespondenz zwischen Vorlesungsteilen und Skript

Vorlesungsteil Abschnitte im Skript
1a1, 2.1 (Hausaufgabe: 2.2–2.5)
1b3.1, 3.2 bis Anfang 3.2.2
1c3.2.2, 3.3–3.6
2b4.1
2c4.11
3a4.2, 4.3
3b4.4, 4.5
3c4.6
4a4.7, 4.8
4b4.12, 4.13
4c4.9
6b5.2 bis Anfang 5.2.1, 5.6
6c5.7 bis Anfang 5.7.2, 5.7.2.2
7b5.8
7c6.2, 6.3 bis Anfang 6.3.1, 7
8c8, 9.1, 9.2
09b13.1, 13.2 bis Anfang 13.2.2
09c13.2.2–13.2.4, 13.3
10a13.4, 13.5
10b14
10c15 bis Anfang 15.2
11a15.2
11b16 bis Anfang 16.2
11c16.2–16.4
12b16.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.

Die reguläre Klausur findet am Donnerstag 31.07.2025 ab 16:00 Uhr statt.

Der Termin für die Wiederholungsklausur wird hier bekanntgegeben, sobald er feststeht.

Falls Sie einen Nachteilsausgleich in Anspruch nehmen möchten, melden Sie sich bitte mindestens eine Woche im Voraus bei Prof. Dr. Jasmin Blanchette.

Artikelaktionen


Funktionsleiste