Formale Systeme
Formale Systeme
Course with SWS 4/2/0 (lecture/exercise/practical) in WS 2024
Lecturer
Tutor
SWS
- 4/2/0
Modules
Examination method
- Written exam
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
Vorlesungstermine:
- Mo 3. DS (BAR/SCHÖ/E)
- Do 4. DS (HSZ/0003/H)
Übungen
Die Einschreibung 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:innen sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.
Übungsgruppen finden ab dem 21. Oktober 2024 zu ihren jeweiligen Terminen statt. Übungsblätter können in OPAL abgerufen werden.
Kontakt
Im OPAL steht ein Forum zum Austausch mit anderen Kursteilnehmenden bereit.
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. Allgemeine Fragen sollten Sie aber immer in geteilten Kanälen stellen, damit auch Ihre Kommiliton:innen 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.
- Christel Baier, Manuela Berg, Walter Nauber: Formale Systeme WS2011/2012: Skript zur Vorlesung. TU Dresden.
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. Formale Sprachen | DS3, October 14, 2024 in BAR/SCHÖ | File |
| Lecture | 2. Grammatiken und die Chomsky-Hierarchie | DS4, October 17, 2024 in HSZ/0003 | File |
| Lecture | 3. Endliche Automaten | DS3, October 21, 2024 in BAR/SCHÖ | File |
| Lecture | 4. Nichtdeterministische Endliche Automaten | DS4, October 24, 2024 in HSZ/0003 | |
| Lecture | 5. Abschlusseigenschaften regulärer Sprachen | DS3, October 28, 2024 in BAR/SCHÖ | |
| No session | Reformationstag | ||
| No session | Keine Vorlesung | DS3, November 4, 2024 in -- | |
| No session | Keine Vorlesung | DS4, November 7, 2024 in -- | |
| Lecture | 6. Reguläre Ausdrücke | DS3, November 11, 2024 in BAR/SCHÖ | |
| Lecture | 7. Reguläre Ausdrücke (2) | DS4, November 14, 2024 in HSZ/0003 | |
| Lecture | 8. Minimale Automaten | DS3, November 18, 2024 in BAR/SCHÖ | |
| Lecture | 9. Minimale Automaten (2) | DS4, November 21, 2024 in HSZ/0003 | |
| Lecture | 10. Grenzen regulärer Sprachen / Probleme regulärer Sprachen | DS3, November 25, 2024 in BAR/SCHÖ | |
| Lecture | 11. Von regulären zu kontextfreien Sprachen | DS4, November 28, 2024 in HSZ/0003 | |
| Lecture | 12. Das Wortproblem für kontextfreie Sprachen | DS3, December 2, 2024 in BAR/SCHÖ | |
| Lecture | 13. Das Pumping-Lemma für kontextfreie Sprachen | DS4, December 5, 2024 in HSZ/0003 | |
| Lecture | 14. Abschlusseigenschaften kontextfreier Sprachen | DS3, December 9, 2024 in BAR/SCHÖ | |
| Lecture | 15. Kellerautomaten | DS4, December 12, 2024 in HSZ/0003 | |
| Lecture | 16. Kellerautomaten (2) | DS3, December 16, 2024 in BAR/SCHÖ | |
| Lecture | 17. Deterministische Typ-2-Sprachen / Probleme für kontextfreie Sprachen | DS4, December 19, 2024 in HSZ/0003 | |
| Lecture | 18. Turingmaschinen | DS3, January 6, 2025 in BAR/SCHÖ | |
| Lecture | 19. Nichtdeterminismus und Unentscheidbarkeit | DS4, January 9, 2025 in HSZ/0003 | |
| Lecture | 20. Typ 0 und Typ 1 | DS3, January 13, 2025 in BAR/SCHÖ | |
| Lecture | 21. Aussagenlogik | DS4, January 16, 2025 in HSZ/0003 | |
| Lecture | 22. Äquivalenzen und Normalformen | DS3, January 20, 2025 in BAR/SCHÖ | |
| Lecture | 23. Logisches Schließen | DS4, January 23, 2025 in HSZ/0003 | |
| Lecture | 24. Horn-Logik und Komplexitätstheorie | DS3, January 27, 2025 in BAR/SCHÖ | |
| Lecture | 25. NP-Vollständigkeit | DS4, January 30, 2025 in HSZ/0003 | |
| Lecture | 26. Zusammenfassung und Ausblick | DS3, February 3, 2025 in BAR/SCHÖ |
Calendar
