Projekt Algorithm Engineering (SAT Solving)
Voraussetzungen
- Gute Programmierkenntnisse
- Optional: Vorlesung SAT Solving
Themen
If requested, the project can also be conducted in English.
Das Erfüllbarkeitsproblem (SAT) ist eines der bekanntesten und am intensivsten untersuchten Probleme der Informatik. Ein wichtiges Merkmal ist die NP-Vollständigkeit von SAT. Traditionell wurde die NP-Vollständigkeit als Argument benutzt, um zu zeigen, dass ein Problem nicht effizient gelöst werden kann. Moderne SAT-Solver können jedoch im praktischen Einsatz Instanzen lösen, die Millionen von Variablen enthalten. Das Ziel dieses Projekts ist es, ein besseres Verständnis für die praktische Anwendung von SAT-Solvern zu erlangen.
Eine vorläufige Themenliste besteht aus:
- Faktorisieren mit SAT Solvern
- Über die Härte äquivalenter Formeln
- Parallelisierung eines SAT Solvers
Selbstverständlich können auch eigene Themen vorgeschlagen werden.
Bei Interesse melden Sie sich bitte für den entsprechenden Moodle-Kurs an.