Theoretische Informatik für Medieninformatiker
Aktuelles
- Aufgrund von uni2work-Problemen wird die Abgabefrist für Blatt 4 auf Donnerstag 26.05. 08 Uhr verlängert.
- Die Online-Übung wird von Fr 10-11 auf Fr 15-16 verschoben, da sie zuvor mit einer Pflichtveranstaltung kollidierte.
- Die Vorlesung findet als Präsenzveranstaltungen statt, als Digitale Alternative zur Vorlesung werden Screencasts (zum Großteil aus dem SoSe 2021) bereitgestellt.
- Übungen finden zum Teil in Präsenz und zum Teil online statt.
- Weitere Informationen zur Veranstaltung werden nach und nach vervollständigt, sobald sie bekannt sind.
Inhalt
Es wird eine Einführung in die zentralen Konzepte und Ergebnisse der Theoretischen Informatik gegeben, mit Anwendungsbeispielen. Themen sind:
- Automaten und Formale Sprachen
Deterministische und nicht-deterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Pushdown-Automaten - Berechenbarkeit
Turing-Maschinen, Church'sche These, Unentscheidbarkeit, Halteproblem, Reduktion - Komplexitätstheorie
Die Klassen P und NP, NP-vollständige Probleme
Organisation
- Umfang: 3 Semesterwochenstunden
-
Vorlesung: Prof. Dr. David Sabel
- Übung: Sarah Vaupel, Stephan Barth
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
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| Vorlesung | Di, 14-17 | M 018, Geschw.-Scholl-Pl.1 | 26.04.2022 |
| Übung (Präsenz) | Mo 10-11 | M 209, Geschw.-Scholl-Pl.1 | 02.05.2022 |
| Übung (Online) | Fr 15-16 | Link im uni2work | 29.04.2022 |
Material
-
Das Vorlesungsskript, die Vorlesungsfolien, die Übungsblätter und die Videos sind im Materialbereich in Uni2Work zu finden.
- Ein Backup des Materials (Folien,Skript,Aufgaben) (z.B. wenn uni2work ausfällt) ist hier.
- Die LMU-Cast Playliste ist hier
Planung
| Termin | Inhalte |
|---|---|
| 26.04. 14-16 Uhr | Begrüßung, Einführung, Inhaltsübersicht, Grundlagen Chomsky-Grammatiken und die Chomsky-Hierarchie |
| 03.05. 14-16 Uhr | Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften Endliche Automaten: DFAs |
| 10.05. 14-16 Uhr | DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs Typ-3-Grammatiken in NFAs umformen, Determinisierung (Potenzmengenkonstruktion) |
| 17.05. 14-17 Uhr | NFAs mit Epsilon-Übergängen, reguläre Ausdrücke Satz von Kleene Pumping-Lemma |
| 24.05. 15-17 Uhr | DFA-Minimierung Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen |
| 31.05. | keine Vorlesung! |
| 07.06. | Pfingstdienstag: Vorlesungsfrei (wird am 08.06. nachgeholt) |
| 08.06. 12-14 Uhr | CFLs: Wortproblem lösen mit dem CYK-Algorithmus Kellerautomaten: Definition, Verwendung, Varianten |
| 14.06. 15-17 Uhr | Deterministisch kontextfreie Sprachen Turingmaschinen und Typ 1- und Typ 0-Sprachen |
| 21.06. 16-17 Uhr | Intuitive Berechenbarkeit, Mehrspuren- und Mehrbandmaschinen |
| 28.06. | keine Vorlesung! |
| 05.07. 15-17 Uhr | entscheidbar, semi-entscheidbar, rekursiv aufzählbar, Halteproblem Satz von Rice, |
| 12.07. 14-17 Uhr | Postsches Korrespondenzproblem Laufzeitkomplexität, die Klassen P und NP NP-Vollständigkeit |
| 19.07. 14-17 Uhr | Der Satz von Cook NP-Vollständigkeit von 3-CNF-SAT NP-Vollständigkeit von CLIQUE, INDEPENDENT SET und VERTEX COVER |
| 26.07. 14-17 Uhr | NP-Vollständigkeit von SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING NP-Vollständigkeit von HAMILTONCYCLE, TRAVELLINGSALESMAN und GRAPH-COLORING Wiederholung und Fragestunde |
Übungen
Die Übungsblätter werden über Uni2work verteilt. Die Abgabe und Korrektur wird ebenfalls über Uni2work abgewickelt, die Abgabefrist ist jeweils auf dem Übungsblatt angegeben.
Klausur / Prüfung
TBA
Artikelaktionen