Îçҹ̽»¨

Projekt SAT-Solving

• Programmierkenntnisse
• Interesse an Algorithmen für NP-harte Probleme
• Vordiplom / Bachelor

• Erweiterungen und Verbesserungen unseres SAT-Solvers hybridGM
• Erweiterungen und Verbesserungen unserers SAT-Solvers Sparrow
• Experimenteller Vergleich der eigenen Implementierung mit bestehenden Solvern auf einem der TOP500 Supercomputer ()
• kurze Dokumentation der Herangehensweise und der Ergebnisse in einem Praktikumsbericht.

Der SLS-solver Sparrow, der kürzlich entwickelt wurde, basiert auf sehr einfache Ideen. Die Performanz des Solvers bei 3-SAT-Problemen ist rekordverdächtig. Es gibt monentan keinen Solver, der besser abschneidet. Diese Performanz kann aber noch weiter verbessert werden. 

ist ein System zum Verwalten von SAT-Solvern und Instanzen. Es ermöglicht das Designen von Benchmarks und auch deren Ausführung auf einem Grid oder Supercomputer. Es gibt noch viele Erweiterungen für dieses System, die sich als Praktikumsthema formulieren lassen.

Unser Solver hybridGM ist einer der besten SAT-Solver für random-Probleme. Es gibt ein paar einfache Ideen, wie dieser Solver noch effizienter gemacht werden kann. Jede solche Idee stellt ein Praktikumsthema dar. Diese werden dann in der Vorbesprechung vorgestellt. 

- Meldungen rundum das SAT- Problem

- SAT Bibliothek für Java

- Solver und Benchamrks rundum SAT

- Wettbewerbe der SAT-Solver

SAT in Ulm - lokale Seite der Mitarbeiter die sich mit dem SAT-Problem beschäftigen

- Solver und Benchmarks rundum das CSP - Problem

1. Stochastic Local Search Foundations and Applications - Hoos, Holger H.; Stützle, Thomas
2. Handbook of Satisfiability - Biere, A.; Heule, M.; Van Maaren, H.; Walsh, T.;

Die Bücher stehen in der Abteilung zur Verfügung.