Formale Systeme

Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in WS 2024

Dozent

Sebastian Rudolph

Tutor

Umfang (SWS)

4/2/0

Module

Leistungskontrolle

Klausur

Vorlesungsreihe

Formale Systeme

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

Franz Baader: Skript Formale Systeme, Teil 1 – Automaten und formale Sprachen. TU Dresden.

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)

Veranstaltungskalender abonnieren (icalendar)

Vorlesung	1. Formale Sprachen	DS3, 14. Oktober 2024 in BAR/SCHÖ	Datei
Vorlesung	2. Grammatiken und die Chomsky-Hierarchie	DS4, 17. Oktober 2024 in HSZ/0003	Datei
Vorlesung	3. Endliche Automaten	DS3, 21. Oktober 2024 in BAR/SCHÖ	Datei
Vorlesung	4. Nichtdeterministische Endliche Automaten	DS4, 24. Oktober 2024 in HSZ/0003	Datei
Vorlesung	5. Abschlusseigenschaften regulärer Sprachen	DS3, 28. Oktober 2024 in BAR/SCHÖ	Datei
Entfällt	Reformationstag
Entfällt	Keine Vorlesung	DS3, 4. November 2024 in --
Entfällt	Keine Vorlesung	DS4, 7. November 2024 in --
Vorlesung	6. Reguläre Ausdrücke	DS3, 11. November 2024 in BAR/SCHÖ	Datei
Vorlesung	7. Reguläre Ausdrücke (2)	DS4, 14. November 2024 in HSZ/0003	Datei
Vorlesung	8. Minimale Automaten	DS3, 18. November 2024 in BAR/SCHÖ	Datei
Vorlesung	9. Minimale Automaten (2)	DS4, 21. November 2024 in HSZ/0003	Datei
Vorlesung	10. Grenzen regulärer Sprachen / Probleme regulärer Sprachen	DS3, 25. November 2024 in BAR/SCHÖ	Datei
Vorlesung	11. Von regulären zu kontextfreien Sprachen	DS4, 28. November 2024 in HSZ/0003	Datei
Vorlesung	12. Das Wortproblem für kontextfreie Sprachen	DS3, 2. Dezember 2024 in BAR/SCHÖ	Datei
Vorlesung	13. Das Pumping-Lemma für kontextfreie Sprachen	DS4, 5. Dezember 2024 in HSZ/0003	Datei
Vorlesung	14. Abschlusseigenschaften kontextfreier Sprachen	DS3, 9. Dezember 2024 in BAR/SCHÖ	Datei
Vorlesung	15. Kellerautomaten	DS4, 12. Dezember 2024 in HSZ/0003	Datei
Vorlesung	16. Kellerautomaten & CFGs	DS3, 16. Dezember 2024 in BAR/SCHÖ	Datei
Vorlesung	17. Deterministische Typ-2-Sprachen / Probleme für kontextfreie Sprachen	DS4, 19. Dezember 2024 in HSZ/0003	Datei
Vorlesung	18. Turingmaschinen	DS3, 6. Januar 2025 in BAR/SCHÖ
Vorlesung	19. Nichtdeterminismus und Unentscheidbarkeit	DS4, 9. Januar 2025 in HSZ/0003
Vorlesung	20. Typ 0 und Typ 1	DS3, 13. Januar 2025 in BAR/SCHÖ
Vorlesung	21. Aussagenlogik	DS4, 16. Januar 2025 in HSZ/0003
Vorlesung	22. Äquivalenzen und Normalformen	DS3, 20. Januar 2025 in BAR/SCHÖ
Vorlesung	23. Logisches Schließen	DS4, 23. Januar 2025 in HSZ/0003
Vorlesung	24. Horn-Logik und Komplexitätstheorie	DS3, 27. Januar 2025 in BAR/SCHÖ
Vorlesung	25. NP-Vollständigkeit	DS4, 30. Januar 2025 in HSZ/0003
Vorlesung	26. Zusammenfassung und Ausblick	DS3, 3. Februar 2025 in BAR/SCHÖ

Kalender