Formale Sprachen und Komplexität
Vorlesung, 3+1-std., Sabel; Übungen 2-std., Barth
Aktuelles
Inhalt
Die Vorlesung behandelt Grundlagen der theoretischen Informatik: Sie gibt Einführungen in die Theorie der formalen Sprachen und Automaten sowie in die Berechenbarkeits- und Komplexitätstheorie. Die Veranstaltung orientiert sich inhaltlich und strukturell am Lehrbuch von Schöning (Theoretische Informatik - kurz gefasst).
Organisation
- Umfang: 3+1+2 Semesterwochenstunden
- Vorlesung + Zentralübung: Prof. Dr. David Sabel
- Übung: Stephan Barth, Gregor Kleen
Zeit und Ort
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| Vorlesung und Zentralübung | Di 14-18 Uhr | online | 13.04.2021 |
| Übung | Mi 8-10 | online | 14.04.2021 |
| Übung | Mi 12-14 | online | 14.04.2021 |
| Übung | Do 10-12 | online | 15.04.2021 |
| Übung | Do 16-18 | online | 15.04.2021 |
| Übung | Fr 10-12 | online | 16.04.2021 |
| Übung | Fr 12-14 | online | 16.04.2021 |
Material
- Das Vorlesungsskript, die Vorlesungsfolien, die Übungsblätter und die Videos sind im Materialbereich in Uni2Work zu finden. Ein Backup als zip-Archive ist hier zu finden. Videos als große Playlisten sind hier zu finden:
Literatur
- [AB02] Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002.
- [HMU06] John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3. Auflage, 2006
- [IW05] Ingo Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 3.Auflage, Teubner Verlag, 2005.
- [US08] Uwe Schöning: Theoretische Informatik - kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008.
- ...
Nützliche Webseiten
- Automata Tutor ein Online-Werkzeug zum Lernen von Automatentheorie
- Grammar Online ein Online-Werkzeug zum Lernen von Formalen Grammatik (Normalformen berechnen, etc.)
- Online Turing Machine Simulator Online-Werzkeug zum Simulieren von Turingmaschinen
| Termin | Inhalte |
|---|---|
| 13.04. | Begrüßung, Einführung, Inhaltsübersicht, Grundlagen Chomsky-Grammatiken und die Chomsky-Hierarchie Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften |
| 20.04. | Entfernen von Epsilon-Produktionen Entscheidbarkeit des Wortproblems Endliche Automaten: DFAs |
| 27.04 | DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs Typ-3-Grammatiken in NFAs, Determinisieriung (Potenzmengenkonstruktion) Größe von DFAs und NFAs, NFAs mit Epsilon-Übergängen |
| 04.05. | NFAs mit Epsilon-Übergängen, reguläre Ausdrücke Satz von Kleene Pumping-Lemma |
| 11.05. | Nerode-Relation Satz von Myhill-Nerode, Nerode-Automat DFA-Minimierung Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen |
| 18.05. | CFLs: Normalformen und Abschlusseigenschaften CFLs: Herstellen von Normalformen Das Pumpinglemma für CFLs |
| 25.05. | CFLs: Wortproblem lösen mit dem CYK-Algorithmus Kellerautomaten: Definition, Verwendung, Varianten Äquivalenz von PDAs und CFLs |
| 01.06. | Deterministisch kontextfreie Sprachen Turingmaschinen und Typ 1- und Typ 0-Sprachen Entscheidbarkeiten bei CFLs und Kuroda-Normalform für CSLs |
| 08.06. | Beweise des Satz von Kuroda, LBA-Probleme Intuitive Berechenbarkeit, Mehrspuren- und Mehrbandmaschinen TM-Konstruktionen und LOOP-Programme |
| 15.06. | WHILE- und GOTO-Berechenbarkeit Ackermannfunktion Primitive Rekursion und mu-Rekursion |
| 22.06. | entscheidbar, semi-entscheidbar, rekursiv aufzählbar, Halteproblem Satz von Rice, Postsches Korrespondenzproblem |
| 29.06. | Laufzeitkomplexität, die Klassen P und NP, NP-Vollständigkeit, der Satz von Cook |
| 06.07. | NP-Vollständigkeit von 3-CNF-SAT, 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-14 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.
https://www.tcs.ifi.lmu.de/lehre/ss-2021/fsk/material/material/view
Artikelaktionen