Das Erfüllbarkeitsproblem SAT

Algorithmen und Analysen

Autoren

• Uwe Schöning

Parameter

• Mathematik

Mehr zum Buch

SAT (für satisfiability) ist das bekannteste NP-vollständige Problem, das sich mit der Erfüllbarkeit von Aussagenlogik beschäftigt. Bei diesem Problem wird eine Formel mit Boole’schen Variablen und Verknüpfungen gegeben, und es wird eine Wertezuweisung gesucht, die die Formel wahr macht. Dieses algorithmische Problem ist zentral für NP-Vollständigkeitsnachweise und wird oft als „Drosophila“ der Algorithmik bezeichnet. In den letzten Jahren wurden leistungsstarke Algorithmen entwickelt, die in der Lage sind, Formeln mit Hunderten oder Tausenden von Variablen zu lösen. Besonders herausfordernd sind Formeln mit wenigen Lösungen, was der Suche nach einer Nadel im Heuhaufen gleicht. In diesem Buch wird detailliert erklärt, wie solche Algorithmen funktionieren und wie logische Kalküle sowie heuristische Suchmethoden eingesetzt werden. Es ist die erste deutschsprachige Veröffentlichung zu diesem Thema und erscheint als Band 1 der Reihe Mathematik für Anwendungen. Diese Reihe zeigt, dass Mathematik mehr ist als nur Theoreme und Definitionen – sie bietet die Möglichkeit, anwendungsnahe Probleme der realen Welt zu lösen. Die Bände sind für Vorlesungen und Seminare in Ingenieurwissenschaften und Informatik gedacht und zielen darauf ab, Themen kompakt und didaktisch durchdacht zu präsentieren. Sie sind wertvoll für Studierende, Praktiker aus der Industrie sowie Lehrer und Schüler in mathematischen Fächern.

• Sprache: Deutsch
• Erscheinungsdatum: 2012