Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2022 / Theoretische Informatik für Medieninformatiker


Inhaltsbereich

Theoretische Informatik für Medieninformatiker

Vorlesung, 2-std., Sabel; Übungen 1-std., Vaupel, Barth

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:

  1. Automaten und Formale Sprachen
    Deterministische und nicht-deterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Pushdown-Automaten
  2. Berechenbarkeit
    Turing-Maschinen, Church'sche These, Unentscheidbarkeit, Halteproblem, Reduktion
  3. 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

VeranstaltungZeitOrtBeginn
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

Nützliche Webseiten

TerminInhalte
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



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

Die Erstklausur findet am 17.08.2022 von 12-14 Uhr statt, die Nachklausur findet am 21.09.2022, 12-14 Uhr statt.
Anmeldungen zu den Klausuren sind ab 01.06.2022 10 Uhr über uni2work möglich: [Erstklausur | Nachklausur]
Bitte beachten Sie die An- und Abmeldefristen (sie sind in uni2work auffindbar).

Artikelaktionen


Funktionsleiste