Theoretische Informatik für Medieninformatiker
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:
- 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: Gregor Kleen, Stephan Barth
Zeit und Ort
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| 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:
Protokoll / Planung
| Termin | Inhalte |
|---|---|
| 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 |
Ü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
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