Formale Sprachen und Komplexität
Aktuelles
- 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 ab 16.Mai)
Skript
Das Skript zur Vorlesung wird ständig erweitert. Die aktuelle Version ist hier verfügbar.
Zentralübung
- Folien zur Zentralübung am 09. Mai [Bildschirmversion,Druckversion]
- Folien zur Zentralübung am 16. Mai [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.
- ...
Protokoll und Planung
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)
Planung für die bald kommenden Vorlesungen
- Mittwoch 22. Mai: Pumping-Lemma (Wdh), Satz von Myhill-Nerode
- Donnerstag 23. Mai: Satz von Myhill-Nerode, Konstruktion des Minimalautomaten (evtl.)
Ü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 noch nicht möglich und wird rechtzeitig (d.h. ca. 4 Wochen vor dem Klausurtermin) freigeschaltet und hier erläutert.
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 noch nicht möglich und wird rechtzeitig (d.h. ca. 4 Wochen vor dem Klausurtermin) freigeschaltet und hier erläutert.
Artikelaktionen