Formale Systeme
Formale Systeme
Course with SWS 4/2/0 (lecture/exercise/practical) in WS 2020
Lecturer
Tutor
SWS
- 4/2/0
Modules
Examination method
- Written exam
Matrix channel
Lecture series
Die Lehrveranstaltung Formale Systeme vermittelt eine Einleitung in die Gebiete der formalen Sprachen, Automatentheorie und Aussagenlogik. Dies beinhaltet einige der wichtigsten Grundlagen der Informatik, wie z.B. reguläre Ausdrücke, formale Grammatiken sowie Methoden zur praktischen Lösung von "schweren" (NP-vollständigen) Problemen. Damit bildet die Vorlesung die Grundlage für die Vorlesung Theoretische Informatik und Logik und für viele vertiefende Vorlesungen.
Vorlesungen
Im Wintersemester 2020/21 findet die Lehrveranstaltung rein digital statt. Die Vorlesungen werden als Videoreihe auf YouTube veröffentlicht. Links finden sich unter
Zudem werden einige Live-Sessions zur Konsultation angeboten. Diese werden aufgrund der großen Teilnehmerzahl jeweils über Zoom abgehalten. Die Einwahldetails finden sich im Bereich Links der OPAL-Seite dieser Lehrveranstaltung. Ein Login oder die Installation spezieller Software ist nicht erforderlich. Konsultationstermine sind wie folgt:
- Montag, 26.10.2020, 3.DS (11:10–12:40): Einführung und Willkommen
- Montag, 23.11.2020, 3.DS (11:10–12:40): Gelegenheit für Fragen und Feedback zum Stoff und zur digitalen Durchführung
- Donnerstag, 25.02.2021, 2. DS (09:20–11:10): Besprechung Probeklausur und Vorbereitung Klausur
- Donnerstag, 04.03.2021, 2. DS (09:20–11:10): Fragen zur Klausurvorberitung
Übungen
Die Einschreibungen in die Übungsgruppen erfolgt über die OPAL-Seite der Lehrveranstaltung. Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe verpflichtend. Studierenden ohne Einschreibung kann die Teilnahme an einer selbstgewählten Übung nicht garantiert werden. Übungsleiter sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der (digitalen) Übung zu verweisen.
Übungsgruppen finden ab dem 5. November 2020 zu ihren jeweiligen Terminen statt. Die Übungen werden digital über das an der TU Dresden gehostete System BigBlueButton abgehalten. Links auf die entsprechenden digitalen Räume werden über OPAL bekanntgegeben. Übungsblätter können in OPAL abgerufen werden.
Individuelles Feedback für Ihre Lösungen: Als zusätzliche Hilfe bieten wir in diesem Semester an, von Ihnen eingereichte Lösungsansätze zu sichten und Ihnen dazu eine Rückmeldung zu geben. Die Details (Abgabetermin, Umfang) werden von den Tutoren festgelegt. Unterlagen können über OPAL abgegeben werden (als digitales Dokument, egal ob Handyfoto der eigenen Handschrift oder am Computer geschriebener Text).
Die Übungsblätter können in der Spalte der jeweiligen Übung unter "Termine und Unterlagen" heruntergeladen werden.
Wiederholungsprüfung
Die Wiederholungsprüfung wird in der Prüfungsform Referat im Zeitraum 2.–4. August durchgeführt. Nach erfolgter Anmeldung erhalten alle Teilnehmenden ein individuelles Thema, zu dem sie einen zehnminütigen Kurzvortrag ausarbeiten. Im Anschluss an jeden Vortrag folgt eine kurze Fragerunde. Die Vorträge werden in ganztägigen Onlineseminaren gehalten; jede:r Teilnehmer:in muss aber nur am jeweiligen Halbtag des eigenen Vortrags teilnehmen. Zur Themenvergabe melden Sie sich bitte per Email bei Maximilian Marx.
Wir empfehlen dringend, zur Unterstützung der Präsentation Folien zu verwenden. Diese müssen bis zum 30.7. im PDF-Format eingereicht werden, damit wir sie in eine Gesamtpräsentation integrieren können (aufgrund des Zeitaufwandes wird die Präsentation von Folien vom eigenen Rechner aus nicht unterstützt). Gleichwohl werden Sie die Folien im BBB selbst umschalten können.
Prüfung
Aufgrund der COVID-19-Situation wird die Klausur dieses Semester als Online-Klausur über die ONYX-Plattform stattfinden. Klausurtermin ist der 9. März von 09:20 Uhr bis 10:50 Uhr (eine Anmeldung an die Plattform ist ab 08:50 möglich); die Probeklausur findet am 16. Februar von 12:00 Uhr bis 13:30 Uhr statt. Die Anmeldung findet wie gewohnt statt. Bitte beachten Sie die Hinweise zur Klausurdurchführung.
Unterlagen
Die vollständigen Foliensätze zur Vorlesung erscheinen bis zur Woche der Vorlesung online (siehe Termine und Unterlagen). Weiterführende Literatur ist unter Literatur angegeben. Die Quellen der Vorlesungsfolien sind auf github verfügbar: https://github.com/knowsys/FormaleSysteme
Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von Creative Commons CC By 3.0 Deutschland genutzt, weitergegeben und modifiziert werden. Als Namensnennung ist folgende Angabe einzufügen:
(C) Markus Krötzsch, https://iccl.inf.tu-dresden.de/web/FS2020, CC BY 3.0 DE
Bildrechte können davon abweichen und sind gesondert angegeben. Die Foliensätze enthalten keinerlei Texte, die aus Werken entnommen sind, für welche die VG Wort Verwertungsrechte vertritt.
Besonderen Dank gilt allen Contributors, die Anmerkungen und Verbesserungen beigetragen haben: Daniel Borchmann, Maximilian Marx, Christian Lewe, David Tiede, Johannes (jhaye), Andrej Bereza, CniKKoR, Marcus Rossel, Max Haertwig, Sönke (eknoes), Benno Fünfstück, Julius Schmitt. (Stand März 2021; Ergänzungen sind willkommen.)
Kontakt
Zur Kommunikation unter Vorlesungsteilnehmern der TU Dresden stehen ein OPAL-Diskussionsforum und ein Matrix-Kanal zur Verfügung.
Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/mkroetzsch/FormaleSysteme Alternativ können Hinweise zu Tippfehlern in den Vorlesungsfolien auch an die Mailingliste geschickt werden.
Persönliche Fragen können auch direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht über andere Kanäle gerichtet werden können. Allgemein Fragen sollten Sie aber immer in geteilten Kanälen stellen, damit auch Ihre Kommilitoninnen und Kommilitonen davon profitieren (oder vielleicht sogar direkt helfen können).Allgemein sind die Vorlesungsfolien und Übungsunterlagen ausreichend detailliert für das Studium. Weitere Lehrmaterialien können dennoch hilfreich sein, um Details nachzuschlagen oder sich weiter im Thema zu vertiefen.
Formale Sprachen, Komplexität und Entscheidbarkeit
Lehrbücher
- Uwe Schöning: Theoretische Informatik -- kurz gefasst. Spektrum Akademischer Verlag.
- (deutschsprachiger Standardtext; in der Tat ziemlich kurz gefasst)
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit. Pearson Studium.
- (aus dem Englischen übertragenes Standardwerk; Original ev. besser)
- Michael Sipser: Introduction to the Theory of Computation. Cengage Learning.
- (Standardtext zu Sprachen und Berechnungskomplexität; leider nur auf Englisch)
Online verfügbare Skripte
Die Vorlesungen haben kleine Abweichungen von diesem Text, stimmen aber in vielen wichtigen Punkten überein.
Andere Scripte scheinen zurzeit nicht (mehr) online verfügbar zu sein. Hinweise zu weiteren Links auf sinnvolle Materialien sind willkommen.
Aussagenlogik
Die Vorlesungsfolien sollten bei diesem Thema ausreichen. Wer dennoch weitere Details nachschlagen will, dem nützen eventuell die folgenden Bücher:
- Uwe Schöning: Logik für Informatiker. Spektrum Akademischer Verlag.
- (leichte Abweichungen in Notation und Darstellung)
- Martin Kreuzer, Stefan Kühling: Logik für Informatiker. Pearson Studium.
- (sehr knapp und informell; eventuell interessant als Quelle für Übungsaufgaben)
- Steffen Hölldobler: Logik und Logikprogrammierung. Synchron Verlag.
- (Schwerpunkt auf Logikprogrammierung und Prädikatenlogik, aber auch einiges zur Aussagenlogik)
- Steffen Hölldobler, Sebastian Bader, Bertram Fronhöfer, Ursula Hans, Pascal Hitzler, Markus Krötzsch, Tobias Pietzsch: Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen Synchron Verlag
- (Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)
Subscribe to events of this course (icalendar)
| Lecture | 1. Begrüßung und Einleitung | DS3, October 26, 2020 in Zoom | File |
| Video 1, Video 2 | |||
| Lecture | 2. Grammatiken und die Chomsky-Hierarchie | DS4, October 29, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Exercise | 1. Übungsblatt | File | |
| Lecture | 3. Endliche Automaten | DS3, November 2, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Lecture | 4. Nichtdeterministische Automaten | DS4, November 5, 2020 in Video | File |
| Video 1, Video 2, Video 3, Video 4 | |||
| Exercise | 2. Übungsblatt | File | |
| Lecture | 5. Abschlusseigenschaften regulärer Sprachen | DS3, November 9, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Lecture | 6. Reguläre Ausdrücke (1) | DS4, November 12, 2020 in Video | File |
| Video 1, Video 2 | |||
| Exercise | 3. Übungsblatt | File | |
| Lecture | 7. Reguläre Ausdrücke (2) | DS3, November 16, 2020 in Video | File |
| Video 1, Video 2 | |||
| Lecture | 8. Minimale Automaten | DS4, November 19, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Exercise | 4. Übungsblatt | File | |
| Lecture | 9. Minimale Automaten (2) | DS3, November 23, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Consultation | Konsultation 1 | DS3, November 23, 2020 in Zoom | |
| Lecture | 10. Grenzen regulärer Sprachen / Probleme für Automaten | DS4, November 26, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Exercise | 5. Übungsblatt | File | |
| Lecture | 11. Von regulären zu kontextfreien Sprachen | DS3, November 30, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Lecture | 12. Das Wortproblem für kontextfreie Sprachen | DS4, December 3, 2020 in Video | File |
| Video 1, Video 2 | |||
| Exercise | 6. Übungsblatt | File | |
| Lecture | 13. Das Pumping Lemma kontextfreier Sprachen | DS3, December 7, 2020 in Video | File |
| Video | |||
| Lecture | 14. Abschlusseigenschaften kontextfreier Sprachen | DS3, December 10, 2020 in Video | File |
| Video 1, Video 2 | |||
| Exercise | 7. Übungsblatt | File | |
| Lecture | 15. Einleitung Kellerautomaten | DS2, December 14, 2020 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Lecture | 16. Kellerautomaten & CFGs | DS3, December 17, 2020 in Video | File |
| Video 1, Video 2 | |||
| Exercise | 8. Übungsblatt | File | |
| Lecture | 17. Deterministische Sprachen / Entscheidungsprobleme | DS2, January 4, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Practical | Werbung: PAUL Consultants e.V. | DS3, January 7, 2021 in Video | |
| Video | |||
| Lecture | 18. Turingmaschinen | DS3, January 7, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Exercise | 9. Übungsblatt | File | |
| Lecture | 19. Nichtdeterministische Turingmaschinen und Unentscheidbarkeit | DS2, January 11, 2021 in Video | File |
| Video 1, Video 2 | |||
| Lecture | 20. Typ 0 und Typ 1 | DS3, January 14, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Exercise | 10. Übungsblatt | File | |
| Lecture | 21. Aussagenlogik | DS2, January 18, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Lecture | 22. Äquivalenzen und Normalformen | DS3, January 21, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Exercise | 11. Übungsblatt | File | |
| Lecture | 23. Logisches Schließen | DS2, January 25, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Lecture | 24. Horn-Logik und Komplexitätstheorie | DS3, January 28, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Exercise | 12. Übungsblatt | File | |
| Lecture | 25. NP-Vollständigkeit | DS2, February 1, 2021 in Video | File |
| Video 1, Video 2, Video 3 | |||
| Lecture | Ergebnisse der Vorlesungsevaluation | File | |
| Lecture | Bonusmaterial: Zusammenfassung | File | |
| Video 1, Video 2 | |||
| Exercise | 13. Übungsblatt | File | |
| Consultation | Besprechung der Musterklausur | DS2, February 25, 2021 in (online) | File 1, File 2 |
| Consultation | Konsultation 2 | DS2, March 4, 2021 in (online) | |
Calendar
