SAT-Algorithmen

  • Moduldetails

    Dozent: Dr. Arne Meier

    Frequenz: unregelmäßig

    Veranstaltungsart: Vorlesung, Übung und Labor (2V + 1Ü + 1L, 5 CP)

    Prüfung: mündl. Prüfung

  • Vorlesungsinhalte

    Das Modul vermittelt grundlegende Kenntnisse über moderne Verfahren zum Lösen des SAT-Problems. Nach erfolgreichem Abschluss der LV können die Studierenden gängige Verfahren analysieren und hinsichtlich ihrer Anwendungsfähgikeit in unterschiedlichen Bereichen der Informatik wie beispielsweise Software Engineering, Wissensrepräsentation, Bioinformatik beurteilen. Sie entwerfen und implementieren Algorithmen für spezielle Varianten des SAT-Problems.

    Gliederung:

    • Boole'sche Formeln und Belegungen
    • CNF
    • Tseitin-Kodierung
    • Craig-Interpolanten
    • Resolutionskalkül
    • Polynomial-lösbare Spezialfälle
    • DPLL und Backtracking
    • PPZ-Algorithmus
    • GSAT.

    Das Modul umfasst eine Laborkomponente, in der SAT-Algorithmen implementiert werden.

  • Informationen zur Prüfung

    Die Abschlussprüfung des Moduls ist eine mündliche Prüfung.

    Termin

    Die Prüfungstermine vergeben wir über eine institutsinterne Website (siehe Link unten). Achtung: Dies ersetzt nicht die Anmeldung der Prüfung im QIS.


    Anmeldung

    Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten).


    Studienleistung

    Falls Ihre Prüfungsordnung eine Studienleistung für dieses Modul vorsieht, kontaktieren Sie bitte den Dozenten.

MATERIALIEN

Alle Materialien finden Sie im Stud.IP.

PRÜFUNGSANMELDUNG

Online-Anmeldung beim Prüfungsamt
Termin für mündliche Prüfung vereinbaren