Theoretische Informatik für Medieninformatiker
Vorlesung, 2-std., Sabel; Übungen 1-std., Kleen
Aktuelles
- Online-Hausarbeit: Angaben:
Die Abgabesyntax für Grammatiken war nicht allgemein genug, deswegen wird sie erweitert zu:
<Grammatik> -> <Startsymbol> <Zeilenumbruch> <Produktion> {<Zeilenumbruch> <Produktion>}
<Startsymbol> -> start <Nichtterminal-Bezeichner>
<Produktion> -> <RegelLinks> -> \epsilon | (<RegelRechts> {|<RegelRechts>})
<RegelLinks> -> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>) {<Leerzeichen> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>)}
<RegelRechts> -> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>) {<Leerzeichen> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>)}
<Nichtterminal-Bezeichner> -> (A|...|Z){a|...|z|A|...|Z|0|...|9}
<Terminal-Symbol> -> a|...|z|0|...|9 - Online-Hausarbeit: Die Angaben wurden per Email verschickt, und die Abgabefrist um eine Stunde verlängert.
- Online-Hausarbeit: Uns sind die Probleme mit uni2work bewusst, wir arbeiten an einer Lösung!
- Backup-Variante des Materials verfügbar (hier)
- Die Nachholprüfung ist für den 08.10.2021 von 8-14 Uhr als Online-Prüfung geplant.
- Die Anmeldung zur Online-Hausarbeit 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
-
Verspätete Abgaben werden nicht mehr akzeptiert
Ab inkl. dem aktuellen Übungsblatt 5 werden verspätete Abgaben außerhalb von Uni2work nicht mehr akzeptiert. Ebenso werden wir bei technischen oder anderweitigen Problemen mit der Abgabe nicht mehr nach der jeweiligen Abgabefrist helfen.
Überprüfen Sie, dass Sie die korrekten Dateien hochgeladen haben und Sie diese auch wieder herunterladen und öffnen können. Bitte planen Sie dafür selbstständig einen zeitlichen Sicherheitsabstand vor dem Ende der Abgabefrist ein, damit Sie noch rechtzeitig reagieren können.
Denken Sie auch daran, dass Sie vor der Abgabefrist so oft eine neue Lösung hochladen können, wie Sie wollen, es also nichts dagegen spricht, vorzeitig eine unvollständige Lösung hochzuladen. Falls Probleme auftreten, kontaktieren Sie uns frühzeitig. Die Prüfung ist geplant am 21.07.2021 von 8-14 Uhr als Online-Prüfung (OpenBook-Exam). Details usw. folgen. Melden Sie sich bei uni2work für die Veranstaltung an.
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