Formale Systeme
Formale Systeme
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in WS 2023
Dozent
Tutor
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Klausur
Matrix-Kanal
Vorlesungsreihe
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
Die Vorlesungstermine sind
Die erste Vorlesung findet am Montag, dem 9.Oktober 2023 statt.
Übungen
Die Einschreibung in die Übungsgruppen wird über OPAL erfolgen. Ein entsprechender Link hierzu wird zu gegebener Zeit bereitgestellt. Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe verpflichtend. Studierenden ohne Einschreibung kann die Teilnahme an einer selbst gewählten Übung nicht garantiert werden. Übungsleiter sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.
Übungsgruppen finden ab dem 16. Oktober 2023 zu Ihren jeweiligen Terminen in den angegebenen Räumen statt. Die Übungsblätter können in der Spalte der jeweiligen Übung unter Termine und Unterlagen heruntergeladen werden.
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 steht 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 direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht über andere Kanäle gerichtet werden können. Allgemeine 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)
Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | Einleitung formale Sprachen | DS3, 9. Oktober 2023 in BAR/SCHÖ | |
| Vorlesung | Gammatiken und die Chomsky-Hierarchie | DS4, 12. Oktober 2023 in HSZ/0003 | |
| Vorlesung | Endliche Automaten | DS3, 16. Oktober 2023 in BAR/SCHÖ | |
| Vorlesung | Nichtdeterministische Automaten | DS4, 19. Oktober 2023 in HSZ/0003 | |
| Vorlesung | Abschlusseigenschaften regulärer Sprachen | DS3, 23. Oktober 2023 in BAR/SCHÖ | |
| Vorlesung | Reguläre Ausdrücke (1) | DS4, 26. Oktober 2023 in HSZ/0003 | |
| Vorlesung | Reguläre Ausdrücke (2) | DS3, 30. Oktober 2023 in BAR/SCHÖ | |
| Vorlesung | Minimale Automaten (1) | DS4, 2. November 2023 in HSZ/0003 | |
| Vorlesung | Minimale Automaten (2) | DS3, 6. November 2023 in BAR/SCHÖ | |
| Vorlesung | Grenzen regulärer Sprachen / Probleme für Automaten | DS4, 9. November 2023 in HSZ/0003 | |
| Vorlesung | Von regulären zu kontextfreien Sprachen | DS3, 13. November 2023 in BAR/SCHÖ | |
| Vorlesung | Das Wortproblem für kontextfreie Sprachen | DS4, 16. November 2023 in HSZ/0003 | |
| Vorlesung | Das Pumping Lemma kontextfreier Sprachen | DS3, 20. November 2023 in BAR/SCHÖ | |
| Vorlesung | Abschlusseigenschaften kontextfreier Sprachen | DS4, 23. November 2023 in HSZ/0003 | |
| Vorlesung | Einleitung Kellerautomaten | DS3, 27. November 2023 in BAR/SCHÖ | |
| Vorlesung | Kellerautomaten und CFGs | DS4, 30. November 2023 in HSZ/0003 | |
| Vorlesung | Deterministische Sprachen / Entscheidungsprobleme | DS3, 4. Dezember 2023 in BAR/SCHÖ | |
| Vorlesung | Turingmaschinen | DS4, 7. Dezember 2023 in HSZ/0003 | |
| Vorlesung | Nichtdeterministische Turingmaschinen und Unentscheidbarkeit | DS3, 11. Dezember 2023 in BAR/SCHÖ | |
| Vorlesung | Typ 0 und Typ 1 | DS4, 14. Dezember 2023 in HSZ/0003 | |
| Vorlesung | Konsultation: Fragen und Antworten | DS3, 18. Dezember 2023 in BAR/SCHÖ | |
| Vorlesung | Aussagenlogik | DS4, 4. Januar 2024 in HSZ/0003 | |
| Vorlesung | Äquivalenzen und Normalformen | DS3, 8. Januar 2024 in BAR/SCHÖ | |
| Vorlesung | Logisches Schließen | DS4, 11. Januar 2024 in HSZ/0003 | |
| Vorlesung | Horn-Logik und Komplexitätstheorie | DS3, 15. Januar 2024 in BAR/SCHÖ | |
| Vorlesung | NP-Vollständigkeit | DS4, 18. Januar 2024 in HSZ/0003 | |
| Vorlesung | Zusammenfassung und Ausblick | DS3, 22. Januar 2024 in BAR/SCHÖ |
Kalender
<ul><li>„Lehrveranstaltungstype“ befindet sich nicht in der Liste (Vorlesung, Übung, Seminar, Praktikum, Entfällt, Konsultation) zulässiger Werte für das Attribut „Lehrveranstaltungstype“.</li> <!--br--><li>„DS“ befindet sich nicht in der Liste (DS1, DS2, DS3, DS4, DS5, DS6, DS7, DS8, terminlos) zulässiger Werte für das Attribut „Doppelstunde“.</li> <!--br--><li>Der Datenwert „Date“ enthält einen Gedankenstrich oder andere für die Interpretation der Datumsangabe ungültige Zeichen.</li></ul>
