Seminar Künstliche Intelligenz (01954) im Sommersemester 2022

Veranstalter:
Lehrgebiet Künstliche Intelligenz
Veranstaltungsart:
Seminar
Prüfer:
Prof. Dr. Matthias Thimm
Teilnehmerzahl:
15
Titel:
Satisfiability Solving
Termin:
2 Tage im September
Ort:
Online-Veranstaltung
Abgabetermin der schriftlichen Ausarbeitung:
31.07.2022
Ansprechpartner:

Erläuterungen:

Das Erfüllbarkeitsproblem (satisfiability problem, SAT) ist ein zentrales Problem der theoretischen Informatik und fragt, ob zu einer gegebenen aussagenlogischen Formel (üblicherweise in konjunktiver Normalform) ein Modell existiert, d. h. eine Belegung aller in der Formel auftauchenden Variablen mit ”wahr“ oder ”falsch“, so dass die gesamte Formel zu ”wahr“ evaluiert. Dieses Problem ist NP-vollständig und algorithmische Lösungen benötigen daher im schlimmsten Fall exponentielle Laufzeit (unterüblichen komplexitätstheoretischen Annahmen). Viele Probleme der Informatik (beispielsweise Verifikationsprobleme) und insbesondere der KI (beispielsweise Planungsprobleme) können als Erfüllbarkeitsproblem modelliert werden und profitieren damit von effektiven Lösungsstrategien für das Erfüllbarkeitsproblem.
In diesem Seminar werden sowohl die Grundlagen als auch erweiterte Techniken zur algorithmischen Lösung des Erfüllbarkeitsproblems behandelt. Die Themen des Seminars folgen dabei der Struktur des Handbook of Satisfiability 1). Bitte beachten Sie, dass die gesamte Veranstaltung (inklusive der Präsentationen und der Ausarbeitung) auf Englisch stattfinden wird.

1) Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh (Editors). Handbook of Satisfiability. IOS Press, 2009

Inhaltliche Voraussetzungen:

Gute Kenntnisse in mathematischer Logik und algorithmischen Grundlagen der Informatik.

Formal nach Prüfungsordnung:

  • B.Sc. Informatik: Studieneingangsphase ist abgeschlossen, die Module Grundpraktikum Programmierung, Grundlagen der Theoretischen Informatik und Softwaresysteme sind bestanden
  • M.Sc. Informatik: erfolgreicher Abschluss von vier Wahlpflichtmodulen
  • M.Sc. Praktische Informatik: erfolgreicher Abschluss von zwei Wahlpflichtmodulen

Für alle bereits seit dem Sommersemester 2019 oder früher eingeschriebenen Studierenden in Studiengängen der Informatik gelten Übergangsbestimmungen gemäß der Prüfungsordnung.

Geforderte Leistungen:

Eine schriftliche Ausarbeitung von 12 Seiten (Englisch) und eine Präsentation von 25 Minuten (Englisch) im Rahmen einer gemeinsamen Online-Veranstaltung.

10.05.2024