Formale Sprachen und Komplexität
Vorlesung, 3+1-std., Sabel; Übungen 2-std., Barth, Vaupel
Aktuelles
- Aufgrund von uni2work-Problemen wird die Abgabefrist für Blatt 4 auf Donnerstag 26.05. 08 Uhr verlängert.
- Räume für die Präsenzübungen würden hinzugefügt!
- Raumänderung für die Zentralübung: Diese findet aufgrund des besseren Platzangebots nun in A 240, Geschw.-Scholl-Pl.1 statt (Ausnahme am 27.Juli findet sie in A 140, Geschw.-Scholl-Pl.1 statt.
- Vorlesung und Zentralübung finden 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
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).
Neben der Vorlesung (3V) und den Übungen (2Ü) wird eine optionale Zentralübung (ca alle 2 Wochen, 2-stündig) angeboten. Diese ist "freiwillig" und dient zum Wiederholen / Einüben des Stoffs, aber es wird kein neuer Stoff behandelt.
Organisation
- Umfang: 3+1+2 Semesterwochenstunden
- Vorlesung + Zentralübung: Prof. Dr. David Sabel
- Übung: Stephan Barth, Sarah Vaupel
Zeit und Ort
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| Vorlesung | Di 14-17 Uhr | M 018, Geschw.-Scholl-Pl.1 | 26.04.2022 |
| Zentralübung | Mi,12-14 Uhr, ca 2-wöchig | A 240, Geschw.-Scholl-Pl.1 (am 27.07. in 023, Kaulbachstr. 37) | 27.04.2022 |
| Übung (Präsenz) | Montag 10-12 | B 106, Geschw.-Scholl-Pl.1 | 02.05.2022 |
| Übung (Präsenz) | Montag 12-14 | M 014, Geschw.-Scholl-Pl.1 | 02.05.2022 |
| Übung (Präsenz) | Montag 14-16 | E 216, Geschw.-Scholl-Pl.1 | 02.05.2022 |
| Übung (Präsenz) | Donnerstag 8-10 | A 125, Geschw.-Scholl-Pl.1 | 28.04.2022 |
| Übung (Präsenz) | Donnerstag 16-18 | M 018, Geschw.-Scholl-Pl.1 | 28.04.2022 |
| Übung (Online) | Montag 16-18 | Link im uni2work | 02.05.2022 |
| Übung (Online) | Montag 18-20 | Link im uni2work | 02.05.2022 |
| Übung (Online) | Donnerstag 10-12 | Link im uni2work | 28.04.2022 |
| Übung (Online) | Donnerstag 18-20 | Link im uni2work | 28.04.2022 |
| Übung (Online) | Freitag 10-12 | Link im uni2work | 29.04.2022 |
| Übung (Online) | Freitag 12-14 | 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
Literatur (Auswahl)
- [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 |
|---|---|
| 26.04. | Begrüßung, Einführung, Inhaltsübersicht, Grundlagen Chomsky-Grammatiken und die Chomsky-Hierarchie Entfernen von Epsilon-Produktionen |
| 27.04 | Zentralübung |
| 03.05. | Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften Endliche Automaten: DFAs Entscheidbarkeit des Wortproblems |
| 10.05. | DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs Typ-3-Grammatiken in NFAs umformen, Determinisierung (Potenzmengenkonstruktion) Größe von DFAs und NFAs, NFAs mit Epsilon-Übergängen |
| 11.05. | Zentralübung |
| 17.05. | NFAs mit Epsilon-Übergängen, reguläre Ausdrücke Satz von Kleene Pumping-Lemma |
| 18.05. | Zentralübung |
| 24.05. | Nerode-Relation, Satz von Myhill-Nerode, Nerode-Automat DFA-Minimierung Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen |
| 25.05. | Zentralübung |
| 31.05. | CFLs: Normalformen und Abschlusseigenschaften CFLs: Herstellen von Normalformen Das Pumpinglemma für CFLs |
| 07.06. | Pfingstdienstag: Vorlesungsfrei (wird am 08.06. z.T. nachgeholt) |
| 08.06. | CFLs: Wortproblem lösen mit dem CYK-Algorithmus Kellerautomaten: Definition, Verwendung, Varianten |
| 14.06. | Äquivalenz von PDAs und CFLs Deterministisch kontextfreie Sprachen Turingmaschinen und Typ 1- und Typ 0-Sprachen |
| 15.06. | Zentralübung |
| 21.06. | Entscheidbarkeiten bei CFLs und Kuroda-Normalform für CSLs Beweis des Satz von Kuroda, LBA-Probleme Intuitive Berechenbarkeit, Mehrspuren- und Mehrbandmaschinen |
| 28.06. | TM-Konstruktionen und LOOP-Programme WHILE- und GOTO-Berechenbarkeit Ackermannfunktion |
| 05.07. | Primitive Rekursion und mu-Rekursion entscheidbar, semi-entscheidbar, rekursiv aufzählbar, Halteproblem Satz von Rice, |
| 06.07. | Zentralübung |
| 12.07. | Postsches Korrespondenzproblem Laufzeitkomplexität, die Klassen P und NP NP-Vollständigkeit |
| 19.07. | Der Satz von Cook NP-Vollständigkeit von 3-CNF-SAT NP-Vollständigkeit von CLIQUE, INDEPENDENT SET und VERTEX COVER |
| 20.07. | Zentralübung |
| 26.07. | NP-Vollständigkeit von SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING NP-Vollständigkeit von HAMILTONCYCLE, TRAVELLINGSALESMAN und GRAPH-COLORING Wiederholung und Fragestunde |
| 27.07. | Zentralübung (Reserve / bei Bedarf) |
Ü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
TBA
Artikelaktionen