Links und Funktionen
Sprachumschaltung

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


Inhaltsbereich

Theoretische Informatik für Medieninformatiker

Vorlesung, 2-std., Sabel; Übungen 1-std., Kleen

Aktuelles

 

 

  • Die Nachholprüfung ist für den 08.10.2021 von 8 bis 13:30 Uhr als Online-Prüfung (OpenBook-Exam) geplant. Anmeldung und weitere Informationen sind hier zu finden.
  • Backup-Variante des Materials verfügbar (hier)

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

VeranstaltungZeitOrtBeginn
Vorlesung Di, 14-16 & 16-18 online 13.04.2021
Übung Mi 16-17 online 14.04.2021
Übung Do 9-10 online 16.04.2021


Material

Das Vorlesungsskript, die Vorlesungsfolien, die Übungsblätter und die Videos sind im Materialbereich in Uni2Workzu finden. Ein Backup als zip-Archive ist hier zu finden. Videos als große Playlisten sind hier zu finden:

 

TerminInhalte
13.04. Begrüßung, Einführung, Inhaltsübersicht, Grundlagen
Chomsky-Grammatiken und die Chomsky-Hierarchie
20.04. Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften
Endliche Automaten: DFAs
27.04 DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs
Typ-3-Grammatiken in NFAs, Determinisieriung (Potenzmengenkonstruktion)
04.05. NFAs mit Epsilon-Übergängen, reguläre Ausdrücke
Satz von Kleene
11.05. Pumping-Lemma
DFA-Minimierung
18.05. Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen
CFLs: Normalformen und Abschlusseigenschaften
25.05. CFLs: Wortproblem lösen mit dem CYK-Algorithmus
Kellerautomaten: Definition, Verwendung, Varianten
01.06. Deterministisch kontextfreie Sprachen
Turingmaschinen und Typ 1- und Typ 0-Sprachen
08.06. Intuitive Berechenbarkeit,  Mehrspuren- und Mehrbandmaschinen
Entscheidbarkeit, Unentscheidbarkeit, Halteproblem
15.06. Satz von Rice,
Postsches Korrespondenzproblem
22.06. Laufzeitkomplexität, die Klassen P und NP,
NP-Vollständigkeit,
29.06. Der Satz von Cook
NP-Vollständigkeit von 3-CNF-SAT
06.07. NP-Vollständigkeit von CLIQUE, INDEPENDENT SET und VERTEX COVER,
NP-Vollst.v. SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING
13.07. NP-Vollst. 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

Ersttermin für die Prüfung ist der 21.07.21 von 8-13:30 Uhr als Online-Prüfung (OpenBook-Exam).
Die Anmeldung zur Prüfung  ist hier möglich.

  • Bitte beachten Sie die Fristen und Termine:
    • Anmeldung bis Mi 14 Jul 2021 23:59
    • Abmeldung bis Di 20 Jul 2021 23:59
    • Prüfung: Mi 21 Jul 2021 08:00

Die Nachholprüfung ist für den 08.10.2021 von 8-14 Uhr als Online-Prüfung geplant.

Artikelaktionen


Funktionsleiste