Mitteilungen

Am 28.04.2022 haben Sie zwischen 14:00 und 15:30 Uhr im Raum Z2073 die Gelegenheit, Einsicht in Ihre Klausur zu nehmen. Um einen hinreichenden Infektionsschutz zu gewährleisten, bitten wir Sie, sich vorher über unsere Terminumfrage (hier klicken) anzumelden.

Vorlesungen und Übungen im Fach "Automaten und Komplexität" werden im SS21 bis auf Weiteres nur online stattfinden. Wir werden für jede Vorlesung Videos und Folien (sowie gegebenenfalls zusätzliches Material) hochladen, welches Sie zuhause vor dem Termin auf Ihrem Stundenplan selbstständig durcharbeiten. Zum Termin der Vorlesung bieten wir eine Sprechstunde an, zu der Fragen zu den aktuellsten Materialien gestellt werden können.

Die Übungen rechnen Sie bitte ebenfalls vor dem Termin in Ihrem Stundenplan durch. Sie können Ihre Lösungen dann im zugehörigen Moodle-Kurs hochladen. Zum Termin in Ihrem Stundenplan werden wir gemeinsam (online) über Ihre Lösungen und Probleme sprechen. Währenddessen werden Ihre Abgaben von uns korrigiert, wodurch Sie für die Prüfung am Ende des Semesters Bonuspunkte erhalten können.

Die Links zu den WebEx-Meetings finden Sie im zugehörigen Moodle-Kurs: Link. In diesem Kurs können Sie auch Ihre Lösungen für die Übungen zum Korrigieren abgeben.

Materialien

Vorlesung

  • 1. Vorlesung: Skript (korrigiert am 26.04.) und Video (Thema: Einführung, Definition DFAs, Abschlusseigenschaften)
  • 2. Vorlesung: Skript (korrigiert am 07.05.) und Video (Thema: NFAs, Potenzmengenkonstruktion, Abschlusseigenschaften)
  • 3. Vorlesung: Skript und Video (Thema: Reguläre Ausdrücke und Nicht-reguläre Sprachen)
  • 4. Vorlesung: Skript und Video (Thema: Minimale DFAs und Analyse regulärer Sprachen)
    Hinweis: Im Video hat sich ein Fehler auf den Seiten 52 und 53 eingeschlichen (die Rollen der Automaten M1 und M2 wurden vertauscht. In der PDF-Datei ist dies korrigiert (rot markierter Text).
  • 5. Vorlesung: Skript und Video (Thema: Anwendung in der Verifikation)
  • 6. Vorlesung: Skript und Video (Thema: Kontextfreie und rechtslineare Grammatiken)
  • 7. Vorlesung: Skript und Video (Thema: Ableitungsbäume)
  • 8. Vorlesung: Skript und Video (Thema: Nicht-kontextfreie Sprachen)
  • 9. Vorlesung: Skript und Video (Thema: CYK-Algorithmus und Chomsky-Normalform)
  • 10. Vorlesung: Skript und Video (Thema: Kellerautomaten)
  • 11. Vorlesung: Skript und Video (Thema: Analyse kontextfreier Sprachen und Anwendung in der Verifikation)
  • 12. Vorlesung: Skript und Video (Thema: Turing-Maschinen, (Semi-)Entscheidbare Sprachen und Church-Turing-These)
  • 13. Vorlesung: Skript und Video (Thema: Unentscheidbare Probleme, Reduktionen und Satz von Rice)
  • 14. Vorlesung: Skript und Video (Thema: Komplexitätsklassen, Polynomialzeitreduktionen)
  • 15. Vorlesung: Skript und Video (Thema: NP-vollständige Probleme)

Übung

Termine

Vorlesung:  Dienstag, 15:00 - 16:30 Uhr, (LdV-Hs 2) Online, C. Köcher

Übung: Montag (G), 11:00 - 12:30 Uhr, (Sr HU 010) Online, C. Köcher