Formale Sprachen und Komplexität
Aktuelles
- Einsichtstermin um 1 Stunde verschoben: Mittwoch, 16.Oktober 16-18 Uhr in der Oettingenstraße, Raum 151
- Vorläufige Klausurergebnisse der Nachholklausur sind im Uni2work veröffentlicht.
Statistik zur Klausur:Note 1 2 3 4 5 Schnitt Anteil 1% 12% 24% 20% 44% 3,94 - Einsicht in die Klausur: Mittwoch, 16.Oktober 16-18 Uhr (Oe, 151)
- Im Material-Bereich im Uni2work ist die Aufgabenstellung der Klausur vom 30.Juli zu finden.
- Vorläufige Klausurergebnisse sind nun im Uni2work veröffentlicht!
Statistik zur Klausur:
Note 1 2 3 4 5 Schnitt Anteil 7% 15% 24% 17% 38% 3,66 - Einsicht in die Klausur: Mittwoch, 7.August 10-12 Uhr in Raum L 109 (Oettingenstraße 67)
- Die Klausur findet am Dienstag, 30. Juli um 16:00 Uhr statt!
- Klausuranmeldung zu beiden Klausuren: Die Anmeldung ist ab sofort im Uni2work möglich. Beachten Sie die Anmeldefristen!
- Pfingsmontag (10.6.) und Dienstag der 11.6. sind vorlesungsfrei. Es finden daher keine Übungen statt. Im Uni2Work finden Sie klausurähnliche Aufgaben (zum ersten Teil der Vorlesung), die sie stattdessen bearbeiten können. DIese Aufgaben werden nicht abgegeben und nicht besprochen.
- Update Skript und Foliensatz 02: Die Definition der epsilon-Hülle war nicht richtig. Diese ist nun verbessert.
- Montagsübung, 18-20, beginnt auf Wunsch der Teilnehmenden ab sofort um 18 s.t.
- Bitte melden Sie sich bei Uni2work zur Vorlesung an.
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, Sebastian Sturm
- Tutoren + Korrektoren: Elisabeth Lempa, Xingyu Long, David Tellenbach
- Email-Verteiler (geht an alle Organisierenden): fsk-ss19@tcs.ifi.lmu.de
Zeit und Ort
Veranstaltung | Zeit | Ort | Beginn |
---|---|---|---|
Vorlesung | Mi 12-14 Uhr | Schellingstr. 3 (S), S 002 | 24.04.2019 |
Vorlesung / Zentralübung | Do 16-18 Uhr | Schellingstr. 3 (S), S 002 | 25.04.2019 |
Übung (Stephan Barth) | Mo 10-12 Uhr | Geschw.-Scholl-Pl. 1 (A), A 022 | 29.04.2019 |
Übung (Sebastian Sturm) | Mo 16-18 Uhr | Geschw.-Scholl-Pl. 1 (A), A 022 | 29.04.2019 |
Übung (Elisabeth Lempa) | Mo 18:00 - 19:30 Uhr | Geschw.-Scholl-Pl. 1 (A), A 022 | 29.04.2019 |
Übung (David Sabel) | Di 16-18 Uhr | Geschw.-Scholl-Pl. 1 (M), M 203 | 30.04.2019 |
Übung (David Tellenbach) | Di 18-20 Uhr | Geschw.-Scholl-Pl. 1 (M), M 203 | 30.04.2019 |
Material
Folien
- Foliensatz 00 zur Begrüßung und zum Organisatorischen [Bildschirmversion,Druckversion]
(Besprechung: 24. April) - Foliensatz 01 zu Worten, Formalen Sprachen, Grammatiken und die Chomsky-Hierarchie [Bildschirmversion,Druckversion]
(Besprechung: 24. April, 25. April, 2.Mai) - Foliensatz 02 zu Regulären Sprachen (Formalismen) [Bildschirmversion,Druckversion]
(Besprechung 2.Mai,8.Mai,9.Mai,15.Mai) - Foliensatz 03 zu Regulären Sprachen (Regularität widerlegen,Satz von Myhill-Nerode,Eigenschaften regulärer Sprachen) [Bildschirmversion,Druckversion]
(Besprechung 16.Mai, 22.Mai, 23.Mai) - Foliensatz 04 zu Kontextfreien Sprachen (Teil I) [Bildschirmversion,Druckversion]
(Besprechung 29.Mai, 5.Juni) - Foliensatz 05 zu Kontextfreien Sprachen (Teil II) [Bildschirmversion,Druckversion]
(Besprechung 5. Juni, 6. Juni, 12.Juni) - Foliensatz 06 zu Kontextsensitiven und Typ 0-Sprachen [Bildschirmversion,Druckversion]
(Besprechung am 12.Juni, 13.Juni, 19.Juni) - Foliensatz 07 Übersicht zu Formalen Sprachen [Bildschirmversion,Druckversion]
(Besprechung am 19.Juni) - Foliensatz 08 Berechenbarkeit Teil I [Bildschirmversion,Druckversion]
(Besprechung am 19.Juni, 26.Juni) - Foliensatz 09 Berechenbarkeit Teil II [Bildschirmversion,Druckversion]
(Besprechung am 27.Juni, 3.Juli) - Foliensatz 10 Berechenbarkeit Teil III [Bildschirmversion,Druckversion]
(Besprechung am 3.Juli, 4.Juli, 10.Juli) - Foliensatz 11 Komplexitätstheorie Teil I [Bildschirmversion,Druckversion]
(Besprechung 11.Juli,17.Juli) - Foliensatz 12 Komplexitätstheorie Teil II [Bildschirmversion,Druckversion]
(Besprechung 18.Juli, 24.Juli)
Skript
Das Skript zur Vorlesung ist hier verfügbar.
Zentralübung
- Folien zur Zentralübung am 09. Mai [Bildschirmversion,Druckversion]
- Folien zur Zentralübung am 16. Mai [Bildschirmversion,Druckversion]
- Folien zur Zentralübung am 6. Juni [Bildschirmversion,Druckversion]
- Folien zur Zentralübung am 13. Juni [Bildschirmversion,Druckversion]
- Folien zur Zentralübung am 27. Juni [Bildschirmversion,Druckversion]
- Folien zur Zentralübung am 04. Juli [Bildschirmversion,Druckversion]
- Folien zur Zentralübung am 11. Juli [Bildschirmversion,Druckversion]
- Folien zur Wiederholung und Fragestunde am 25.Juli [Bildschirmversion,Druckversion]
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 (Normalenformen berechnen, etc.)
- Online Turing Machine Simulator Online-Werzkeug zum Simulieren von Turingmaschinen
Protokoll
- Mittwoch 24. April: Begrüßung, Einführung, Inhaltsübersicht, Alphabete, Worte, Formale Sprachen
- Donnerstag 25. April: Chomsky Grammatiken und die Chomsky-Hierarchie
- Mittwoch 1.Mai: Feiertag (keine Vorlesung)
- Donnerstag 2.Mai: Elimination von epsilon-Produktionen, Wortproblem, Typ-3 Sprachen, endliche Automaten (DFA)
- Mittwoch 8.Mai: DFA (Konstruktion DFA in Typ 3 Grammatik), NFAs, reguläre Grammatik in NFA überführen, NFA in DFA mit Potenzmengenkonstruktion
- Donnerstag 9.Mai: Grösse von DFA vs NFA, NFA mit Epsilon-Übergängen, Zentralübung (DFAs, NFAs)
- Mittwoch 15.Mai: NFA mit Epsilon-Übergängen und mit eindeutigen Start- und Endzuständen, Reguläre Ausdrücke, Satz von Kleene
- Donnerstag 16.Mai: Pumping-Lemma und Zentralübung (Reguläre Ausdrücke und Anwenden des Pumping-Lemmas)
- Mittwoch 22. Mai: Pumping-Lemma (Wdh), Satz von Myhill-Nerode
- Donnerstag 23. Mai: Konstruktion des Minimalautomaten, Abschlusseigenschaften Typ-3, Entscheidbarkeiten bei Typ-3 (keine Zentralübung, stattdessen Vorlesung, um die kommenden Feiertage auszugleichen)
- Mittwoch 29. Mai: Kontextfreie Sprachen: Operationen und Normalformen
- Donnerstag 30.Mai: Feiertag (keine Vorlesung)
- Mittwoch 05. Juni: Pumping-Lemma für kontextfreie Sprachen, CYK-Algorithmus
- Donnerstag 06. Juni: Kellerautomaten Zentralübung: Pumping-Lemma für CFLs und Ogdens Lemma, Beispiel zum CYK-Algorithmus
- Mittwoch 12.Juni: Kellerautomaten, deterministisch kontextfreie Sprachen, Abschlusseigenschaften Typ-2, Typ-1 Sprachen, Turingmaschinen
- Donnerstag 13.Juni: Turingmaschinen und LBAs, Zentralübung: Kellerautomaten (Beispiele), Akzeptanz bei PDAs, Turingmaschinen (Beispiel)
- Mittwoch 19.Juni: LBA-Probleme, Intuitive Berechenbarkeit, Mehrbandmaschinen
- Donnerstag 20.Juni: Feiertag (keine Vorlesung)
- Mittwoch 26. Juni: LOOP-Programme, WHILE-Programme, GOTO-Programme, Äquivalenz zur Turingberechenbarkeit
- Donnerstag 27.Juni: Ackermannfunktion, Zentralübung: LOOP/WHILE/GOTO
- Mittwoch 03.Juli: rekursive Funktionen,Halteproblem, Unentscheidbarkeit, rekursiv aufzählbar
- Donnerstag 04.Juli: Fortsetzung Halteproblem, Unentscheidbarkeit, Reduktionen, Zentralübung: Beispiele zu primitiv und mu-rekursiven Funktionen, Reduktion
- Mittwoch 10.Juli: Reduktionen, Satz von Rice, Postsches Korrespondenzproblem
- Donnerstag 11.Juli: Zeitkomplexität, P, NP, Zentralübung: Reduktionen
- Mittwoch 17.Juli: NP Vollständigkeit, Satz von Cook
- Donnerstag 18.Juli: Weitere NP vollständige Probleme
- Mittwoch 24.Juli: Weitere NP vollständige Probleme
- Donnerstag 25.Juli: Wiederholung/Fragen zur Klausur
Ü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
Klausur
Die Klausur findet am Dienstag, 30. Juli um 16:00 Uhr statt (Bearbeitungszeit 120 Minuten).
Eine Anmeldung ist zur Teilnahme an der Klausur ist erforderlich.
Die Anmeldung ist im Uni2work bereits freigeschaltet und bis zum 26. Juli um 12:00 Uhr nötig.
Nachklausur
Die Nachklausur findet am Dienstag, 24. September um 14:00 Uhr statt (Bearbeitungszeit 120 Minuten).
Eine Anmeldung ist zur Teilnahme an der Nachklausur ist erforderlich.
Die Anmeldung ist im Uni2work bereits freigeschaltet und bis zum 20. September um 12:00 Uhr nötig.
Artikelaktionen