Formale Systeme
Formale Systeme
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in WS 2016
Dozent
Tutor
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Klausur
Die Vorlesung 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.
Termine
Die erste Vorlesung ist am Montag, 10.10.2016. Weitere Termine sind jeweils:
- montags 3.DS (11:10–12:40) HSZ/0002
- donnerstags 4.DS (13:00–14:30) HSZ/0003
mit Ausnahme von Mo, 31.10., (Reformationstag) und der vorlesungsfreien Zeit zum Jahreswechsel (keine Vorlesungen vom 22.12.2016 bis zum 3.1.2017).
Übungen
Die Einschreibungen in die Übungsgruppen erfolgt über JExam.
Bitte beachten Sie: 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 Übung zu verweisen.
Unterlagen
Die vollständigen Foliensätze zur Vorlesung erscheinen jeweils kurz nach der Vorlesung online (siehe Termine und Unterlagen). Weiterführende Literatur ist unter Literatur angegeben.
Kontakt
Für Fragen rund um den Stoff und Vorlesungsbetrieb ist eine Mailingliste eingerichtet worden, auf der sich Teilnehmer_innen der Vorlesung einschreiben können. Dazu muss nur das Anmeldeformular ausgefüllt werden. Fast alle Fragen sollten auf diesem Weg gestellt werden. Auch Hinweise zu Tippfehlern in den Vorlesungsfolien sollten am besten direkt an die Liste geschickt werden.
Persönliche Fragen können auch direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht an die Mailingliste gerichtet werden können. Allgemein Fragen sollten Sie aber immer an die Liste richten, damit auch Ihre 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.
Teil 1: Formale Sprachen
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
- Franz Baader: Skript Formale Systeme, Teil 1 – Automaten und formale Sprachen. TU Dresden.
- Christel Baier, Manuela Berg, Walter Nauber: Formale Systeme WS 2011/2012: Skript zur Vorlesung. TU Dresden.
Die Vorlesungen haben kleine Abweichungen von diesen Skripten, stimmen aber in vielen wichtigen Punkten überein.
Teil 2: Aussagenlogik
Literaturempfehlungen werden später an dieser Stelle bekannt gegeben.Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | Willkommen/Einleitung formale Sprachen | DS3, 10. Oktober 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Grammatiken und die Chomsky-Hierarchie | DS4, 13. Oktober 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Endliche Automaten | DS3, 17. Oktober 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Nichtdeterministische endliche Automaten | DS4, 20. Oktober 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Abschlusseigenschaften regulärer Sprachen | DS3, 24. Oktober 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Reguläre Ausdrücke (1) | DS4, 27. Oktober 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Reguläre Ausdrücke (2) | DS4, 3. November 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Minimale Automaten | DS3, 7. November 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Minimale Automaten (2) | DS4, 10. November 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Grenzen regulärer Sprachen/Probleme für Automaten | DS3, 14. November 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Von regulären zu kontextfreien Sprachen | DS4, 17. November 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Das Wortproblem kontextfreier Sprachen | DS3, 21. November 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Das Pumping Lemma kontextfreier Sprachen | DS4, 24. November 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Abschlusseigenschaften kontextfreier Sprachen | DS3, 28. November 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Kellerautomaten | DS4, 1. Dezember 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Kellerautomaten und Typ-2-Grammatiken | DS3, 5. Dezember 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Übung | Repetitorium 1 | DS4, 8. Dezember 2016 in HSZ/0003 | Datei |
| Vorlesung | Deterministische Typ-2-Sprachen / Entscheidungsprobleme | DS3, 12. Dezember 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Turingmaschinen | DS4, 15. Dezember 2016 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Nichtdeterminismus und Unentscheidbarkeit | DS3, 19. Dezember 2016 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Typ-0- und Typ-1-Sprachen | DS4, 5. Januar 2017 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Aussagenlogik | DS3, 9. Januar 2017 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Äquivalenz und Normalformen | DS4, 12. Januar 2017 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | Logisches Schließen | DS3, 16. Januar 2017 in HSZ/0002 | Datei 1, Datei 2 |
| Vorlesung | Horn-Logik / Komplexität | DS4, 19. Januar 2017 in HSZ/0003 | Datei 1, Datei 2 |
| Vorlesung | NP-Vollständigkeit | DS3, 23. Januar 2017 in HSZ/0002 | Datei 1, Datei 2 |
| Übung | Besprechung Musterklausur | DS4, 26. Januar 2017 in HSZ/0003 | Datei |
| Übung | Repetitorium 2 | DS3, 30. Januar 2017 in HSZ/0002 | Datei |
| Vorlesung | Zusammenfassung und Ausblick | DS4, 2. Februar 2017 in HSZ/0003 | Datei 1, Datei 2 |
Kalender
