Formale Systeme

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

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.

Prüfung

Lernraum

Uns wurde am Freitag, dem 09.02.2024, der Lernraum WEB/136 für die 5. DS (14:50-16:20 Uhr) zugeordnet. Zu diesem Termin werden einige Übungsgruppenleiter anwesend sein und auf Fragen eingehen können.

Zeit

Die Klausur über 90 Minuten findet am Dienstag, den 13.02.2024 statt. Der Einlass beginnt um 12:45 Uhr. Die Klausur beginnt um 13:15 Uhr.

Ort

Für die Prüfung stehen und die Räume HSZ/0002, HSZ/0003 sowie HSZ/AUDI/H zur Verfügung. Suchen Sie die Räume gemäß des Anfangsbuchstabens Ihres Nachnamens auf:

Hilfsmittel

Es sind keine Hilfsmittel erlaubt, insbesondere keine technischen und elektronischen Hilfsmittel oder Formelsammlungen und Nachschlagewerke.

Repetitorien

Am Montag, den 11.12.2023 findet im Zeitraum der Vorlesung (11:10-12:40) ein Repetitorium in BAR/SCHÖ statt. In diesem wird eine kurze Zusammenfassung des bis dahin behandelten Stoffs gegeben sowie einige der Aufgaben zur Selbstkontrolle aus den Übungsblättern besprochen.

Vorlesungen

Die Vorlesungstermine sind

  • montags 3.DS (11:10–12:40) in BAR/SCHÖ sowie
  • donnerstags 4.DS (13:00–14:30) in HSZ/0003.

Die erste Vorlesung findet am Montag, dem 9.Oktober 2023 statt.

Übungen

Die Einschreibung in die Übungsgruppen wird über OPAL erfolgen. 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.

Die folgenden Termine für Übungen werden wir anbieten:

  • Gruppe A: montags 2. DS (9:20-10:50) in APB E010 (Übungsleiter: Marcos Cramer)
  • Gruppe B: montags 2. DS (9:20-10:50) in APB E009 (Übungsleiter: Johannes Tantow)
  • Gruppe C: montags 6. DS (16:40-18:10) in APB E010 (Übungsleiter: Florens Förster)
  • Gruppe I: mittwochs 6. DS (16:40-18:10) in APB E007 (Übungsleiter: Jonas Karge)
  • Gruppe D: donnerstags 1. DS (7:30-9:00) in APB E007 (Übungsleiter: Aaron Kutzer)
  • Gruppe E: donnerstags 5. DS (14:50-16:20) in APB E008 (Übungsleiter: Anton Claußnitzer)
  • Gruppe F: freitags 1. DS (7:30-9:00) in APB E009 (Übungsleiter: Max Korn)
  • Gruppe G: freitags 2. DS (9:20-10:50) in APB E006 (Übungsleiter: Aaron Kutzer)
  • Gruppe H: freitags 3. DS (11:10-12:40) in APB E010 (Übungsleiter: Florens Förster)
  • Gruppe J: freitags 4. DS (13:00-14:30) in APB E009 (Übungsleiter: Stephan Mennicke)

Die Einschreibung in die Gruppen der OPAL-Lehrveranstaltung wird am Montag, den 09.10.2023 um 18:00 Uhr freigeschalten.

Der Übungsbetrieb startet am 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/FS2023, 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)
(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik, aber auch einiges zur Aussagenlogik)
(Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)

Veranstaltungskalender abonnieren (icalendar)

Vorlesung Einleitung formale Sprachen DS3, 9. Oktober 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Grammatiken und die Chomsky-Hierarchie DS4, 12. Oktober 2023 in HSZ/0003 Datei 1 Datei 2
Übung 1. Übungsblatt Datei
Vorlesung Endliche Automaten DS3, 16. Oktober 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Nichtdeterministische Automaten DS4, 19. Oktober 2023 in HSZ/0003 Datei 1 Datei 2
Übung 2. Übungsblatt Datei
Vorlesung Abschlusseigenschaften regulärer Sprachen DS3, 23. Oktober 2023 in BAR/SCHÖ Datei 1 Datei 2
Entfällt Interne Veranstaltung DS4, 26. Oktober 2023 in --
Übung 3. Übungsblatt Datei
Vorlesung Reguläre Ausdrücke (1) DS3, 30. Oktober 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Reguläre Ausdrücke (2) DS4, 2. November 2023 in HSZ/0003 Datei 1 Datei 2
Übung 4. Übungsblatt Datei
Vorlesung Minimale Automaten (1) DS3, 6. November 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Minimale Automaten (2) DS4, 9. November 2023 in HSZ/0003 Datei 1 Datei 2
Übung 5. Übungsblatt Datei
Vorlesung Grenzen regulärer Sprachen / Probleme für Automaten DS3, 13. November 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Von regulären zu kontextfreien Sprachen DS4, 16. November 2023 in HSZ/0003 Datei 1 Datei 2
Übung 6. Übungsblatt Datei
Vorlesung Das Wortproblem für kontextfreie Sprachen DS3, 20. November 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Das Pumping Lemma kontextfreier Sprachen DS4, 23. November 2023 in HSZ/0003 Datei 1 Datei 2
Übung 7. Übungsblatt Datei
Vorlesung Abschlusseigenschaften kontextfreier Sprachen DS3, 27. November 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Einleitung Kellerautomaten DS4, 30. November 2023 in HSZ/0003 Datei 1 Datei 2
Übung 8. Übungsblatt Datei
Vorlesung Kellerautomaten und CFGs DS3, 4. Dezember 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Deterministische Sprachen / Entscheidungsprobleme DS4, 7. Dezember 2023 in HSZ/0003 Datei 1 Datei 2
Übung 9. Übungsblatt Datei
Übung Repetitorium DS3, 11. Dezember 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Turingmaschinen DS4, 14. Dezember 2023 in HSZ/0003 Datei 1 Datei 2
Übung 10. Übungsblatt Datei
Vorlesung Nichtdeterministische Turingmaschinen und Unentscheidbarkeit DS3, 18. Dezember 2023 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Typ 0 und Typ 1 DS4, 4. Januar 2024 in HSZ/0003 Datei 1 Datei 2
Übung 11. Übungsblatt Datei
Vorlesung Aussagenlogik DS3, 8. Januar 2024 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Äquivalenzen und Normalformen DS4, 11. Januar 2024 in HSZ/0003 Datei 1 Datei 2
Übung 12. Übungsblatt Datei
Vorlesung Logisches Schließen DS3, 15. Januar 2024 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Horn-Logik und Komplexitätstheorie DS4, 18. Januar 2024 in HSZ/0003 Datei 1 Datei 2
Übung 13. Übungsblatt Datei
Vorlesung NP-Vollständigkeit DS3, 22. Januar 2024 in BAR/SCHÖ Datei 1 Datei 2
Vorlesung Zusammenfassung und Ausblick DS4, 25. Januar 2024 in HSZ/0003 Datei 1 Datei 2
Übung 14. Übungsblatt Datei
Konsultation Besprechung offener Fragen DS3, 29. Januar 2024 in BAR/SCHÖ
Konsultation Besprechung der Probeklausur DS4, 1. Februar 2024 in HSZ/0003 Datei 1 Datei 2


Kalender