Formale Systeme

From International Center for Computational Logic

Formale Systeme

Course with SWS 4/2/0 (lecture/exercise/practical) in WS 2021

Lecturer

Tutor

SWS

  • 4/2/0

Modules

Examination method

  • Written exam

Matrix channel

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.

Prüfung

Klausureinsicht: Zweiter Termin

Für alle Teilnehmer der Klausur besteht am 31.5.2022 zwischen 13:00 und 14:00 Uhr erneut die Möglichkeit zur Klausureinsicht. Diese wird im Raum APB 2040 stattfinden. Wir bitten alle, die dieses Angebot in Anspruch nehmen möchten, sich anzumelden. Hierzu genügt eine kurze Mail an Dörthe Arndt.

Klausureinsicht

Für alle Teilnehmer der Klausur besteht am 28.4.2022 zwischen 16:00 und 17:00 Uhr die Möglichkeit zur Klausureinsicht. Diese wird im APB Raum 2040 stattfinden. Wir bitten alle, die dieses Angebot in Anspruch nehmen möchten, sich anzumelden. Hierzu genügt eine kurze Mail an Dörthe Arndt.

Ergebnisse

Die Korrektur wurde abgeschlossen. Die Ergebnisse werden nach Bearbeitung durch die Prüfungsämter bald in jExam, Selma und HIS verfügbar sein.

Ablauf

Es gelten die aktuellen Bestimmungen der TU Dresden, insbesondere die Hinweise zu Prüfungen.

Zeit

Die Prüfungsklausur über 90min findet am 15. Februar 2022 statt. Der Einlass beginnt um 08:00 Uhr. Die Klausur beginnt, sobald der Einlass abgeschlossen ist. Seien Sie daher spätestens um 08:00 Uhr da.

Ort

Zur Prüfung stehen die Hörsäle TRE/MATH, TRE/PHYS und HSZ/0004 zur Verfügung. Je nach Anfangsbuchstabe Ihres Familiennamens suchen Sie bitte die folgenden Hörsäle auf:

  • A–J: TRE/MATH
  • K–R: TRE/PHYS
  • S–Z: HSZ/0004

Bitte beachten Sie an den einzelnen Räumen auch evtl. unterschiedliche Eingänge, die wiederum nach Anfangsbuchstaben unterteilt sind.

Hilfsmittel

Erlaubt ist ein beidseitig beschriebenes (oder bedrucktes) Blatt DIN A4 („Formelsammlung“).

Es sind keine weiteren Hilfsmittel erlaubt, insbesondere keine technischen oder elektronischen Hilfsmittel oder sonstige Nachschlagewerke.

Gesundheit & Hygiene

  • 3G+: Alle Beteiligten müssen ein höchstens 24h altes negatives Testergebnis vorweisen können, auch vollständig geimpfte und geboosterte Personen. Wir empfehlen einen Test am 14.02. ab 11:00 Uhr.
  • Gültig sind alle Testnachweise, die auch gültig sind für Zugang zu 2G+ im öffentlichen Raum (Kultur, Restaurant usw). Das wird meist auch auf den Testergebnissen ausgewiesen.
  • Kontaktverfolgung mittels Corona-Warn-App bzw. durch Unterschrift auf der Anwesenheitsliste
  • Tragen von FFP2-Masken bis zum Prüfungsraum
  • Tragen von OP- oder FFP2-Masken im Prüfungsraum
  • Atteste zur Befreiung von der Maskenpflicht müssen im Vorfeld vorgelegt werden

Vorlesungen

Vorlesungstermine:

  • Mo 3. DS
  • Do 4. DS

Die Vorlesung wird virtuell (über Zoom) durchgeführt. Der Link zu den Zoom-Terminen findet sich in der OPAL-Seite der Lehrveranstaltung. Die 1. Vorlesung findet am 11. Oktober 2021 statt; die letzte Vorlesung findet am 24. Januar 2022 statt.

Übungen

Es wird dieses Semester sowohl virtuelle Übungsgruppen als auch Übungen in Präsenz geben.

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 (digitalen) Übung zu verweisen. Übungsleiter:innen von Präsenzgruppen sind berechtigt und verpflichtet, die Einhaltung der 3G-Regeln zu überprüfen sowie Beschränkungen der Personenanzahl in den Übungsräumen durchzusetzen.

Übungsgruppen finden ab dem 18. Oktober 2021 zu ihren jeweiligen Terminen statt. Die Übungen werden digital über das an der TU Dresden gehostete System BigBlueButton abgehalten. Links auf die entsprechenden digitalen Räume werden über OPAL bekanntgegeben. Übungsblätter können in OPAL abgerufen werden.

Individuelles Feedback für Ihre Lösungen: Als zusätzliche Hilfe bieten wir in diesem Semester an, von Studierenden eingereichte Lösungsansätze zu sichten und Ihnen dazu eine Rückmeldung zu geben. Die Details (Abgabetermin & Umfang) werden von den Tutor:innen festgelegt. Unterlagen können per E-Mail an die Tutor:innen abgegeben werden (als digitales Dokument, egal ob Handyfoto der eigenen Handschrift oder am Computer geschriebener Text).


Kontakt

Zur Kommunikation unter Vorlesungsteilnehmer:innen der TU Dresden stehen ein OPAL-Diskussionsforum und ein Matrix-Kanal zur Verfügung.

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.

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)

Subscribe to events of this course (icalendar)

Lecture 1. Vorlesung: Formale Sprachen DS3, October 11, 2021 in Video conference File 1 File 2
Lecture 2. Vorlesung: Grammatiken und die Chomsky-Hierarchie DS4, October 14, 2021 in Video conference File 1 File 2
Exercise 1. Übungsblatt File
Lecture 3. Vorlesung: Endliche Automaten DS3, October 18, 2021 in Video conference File 1 File 2
Lecture 4. Vorlesung: Nichtdeterministische Endliche Automaten DS4, October 21, 2021 in Video conference File 1 File 2
Exercise 2. Übungsblatt File
Lecture 5. Vorlesung: Abschlusseigenschaften regulärer Sprachen DS3, October 25, 2021 in Video conference File 1 File 2
Lecture 6. Vorlesung: Reguläre Ausdrücke DS4, October 28, 2021 in Video conference File 1 File 2
Exercise 3. Übungsblatt File
Lecture 7. Vorlesung: Reguläre Ausdrücke (2) DS3, November 1, 2021 in Video conference File 1 File 2
Lecture 8. Vorlesung: Minimale Automaten DS4, November 4, 2021 in Video conference File 1 File 2
Exercise 4. Übungsblatt File
Lecture 9. Vorlesung: Minimale Automaten (2) DS3, November 8, 2021 in Video conference File 1 File 2
Lecture 10. Vorlesung: Grenzen regulärer Sprachen / Probleme regulärer Sprachen DS4, November 11, 2021 in Video conference File 1 File 2
Exercise 5. Übungsblatt File
Lecture 11. Vorlesung: Von regulären zu kontextfreien Sprachen DS3, November 15, 2021 in Video conference File 1 File 2
Lecture 12. Vorlesung: Das Wortproblem für kontextfreie Sprachen DS4, November 18, 2021 in Video conference File 1 File 2
Exercise 6. Übungsblatt File
Lecture 13. Vorlesung: Das Pumping-Lemma für kontextfreie Sprachen DS3, November 22, 2021 in Video conference File 1 File 2
Lecture 14. Vorlesung: Abschlusseigenschaften kontextfreier Sprachen DS4, November 25, 2021 in Video conference File 1 File 2
Exercise 7. Übungsblatt File
Lecture 15. Vorlesung: Kellerautomaten DS3, November 29, 2021 in Video conference File 1 File 2
Lecture 16. Vorlesung: Kellerautomaten (2) DS4, December 2, 2021 in Video conference File 1 File 2
Exercise 8. Übungsblatt File
Lecture 17. Vorlesung: Deterministische Typ-2-Sprachen / Probleme für kontextfreie Sprachen DS3, December 6, 2021 in Video conference File 1 File 2
Lecture 18. Vorlesung: Turingmaschinen DS4, December 9, 2021 in Video conference File 1 File 2
Exercise 9. Übungsblatt File
Lecture 19. Vorlesung: Nichtdeterminismus und Unentscheidbarkeit DS3, December 13, 2021 in Video conference File 1 File 2
Lecture 20. Vorlesung: Typ 0 und Typ 1 DS4, December 16, 2021 in Video conference File 1 File 2
Exercise 10. Übungsblatt File
Lecture 21. Vorlesung: Aussagenlogik DS4, January 6, 2022 in Video conference File 1 File 2
Exercise 11. Übungsblatt File
Lecture 22. Vorlesung: Äquivalenzen und Normalformen DS3, January 10, 2022 in Video conference File 1 File 2
Lecture 23. Vorlesung: Logisches Schließen DS4, January 13, 2022 in Video conference File 1 File 2
Exercise 12. Übungsblatt File
Lecture 24. Vorlesung: Horn-Logik und Komplexitätstheorie DS3, January 17, 2022 in Video conference File 1 File 2
Lecture 25. Vorlesung: NP-Vollständigkeit DS4, January 20, 2022 in Video conference File 1 File 2
Exercise 13. Übungsblatt File
Lecture 26. Vorlesung: Zusammenfassung und Ausblick DS3, January 24, 2022 in Video conference File 1 File 2
Exercise 14. Übungsblatt File
Exercise Probeklausur File
Exercise Lösung Probeklausur DS3, February 7, 2022 in -- File


Calendar