Sie sind hier

E-Book

Das Erfüllbarkeitsproblem SAT

Algorithmen und Analysen

Autor	Jacobo Torán, Uwe Schöning
Verlag	Lehmanns Media GmbH
Erscheinungsjahr	2012
Seitenanzahl	181 Seiten
ISBN	9783865417244
Format	PDF
Kopierschutz	Wasserzeichen/DRM
Geräte	PC/MAC/eReader/Tablet
Preis	16,99 EUR

SAT (für satisfiability) ist der Name des bekanntesten NP-vollständigen Problems, des Erfüllbarkeitsproblems der Aussagenlogik. Gegeben ist hierbei eine Formel mit Boole'schen Variablen und Verknüpfungen und gesucht wird eine 'Lösung', also eine Wertezuweisung an die Variablen, so dass die Formel wahr wird. Dieses algorithmische Problem ist Dreh- und Angelpunkt für alle NP-Vollständigkeitsnachweise und wurde schon als 'Drosophila' der Algorithmik bezeichnet. Für SAT werden seit einiger Zeit leistungsstarke Algorithmen entwickelt, die in der Lage sind, Formeln mit hunderten oder tausenden von Variablen zu lösen. Bei schwierigen Formeln mit nur wenigen Lösungen kommt dies der sprichwörtlichen Suche nach der Nadel im Heuhaufen gleich. Wie derartige Algorithmen arbeiten und wie die zugehörigen logischen Kalküle und heuristischen Suchmethoden eingesetzt werden, wird in diesem Buch - die erste deutschsprachige Veröffentlichung zum Thema - eingehend und fundiert erklärt. Der Titel erscheint als Band 1 der Reihe Mathematik für Anwendungen Diese Textbuchreihe soll zeigen, dass Mathematik mehr ist als nur eine Zusammenstellung von Theoremen und Definitionen - tatsächlich eröffnet die Mathematik die Möglichkeit, anwendungsnah Probleme der realen Welt zu lösen. Gedacht als Grundlage für Vorlesungen und Seminare in den Ingenieurwissenschaften und der Informatik, zielt jeder Band darauf ab, ein bestimmtes Thema kompakt und didaktisch durchdacht zu erfassen und dabei den Balanceakt zwischen formal-korrekter und informal-verständlicher Darstellung zu vollbringen. Nicht nur Studierende, sondern auch Praktiker aus der Industrie sowie Lehrer und Schüler in mathematischen Fächern werden diese Reihe zu schätzen wissen. Mathematics for Applications This series of textbooks is designed to demonstrate how mathematics is more than just a collection of theorems and definitions - it is a powerful means to solve real-world problems! Intended for use in lecture courses and seminars in any field of engineering or computer science, each volume aims for a compact and didactically sound presentation of its subject matter, balancing the demands of formal correctness with the need for general accessibility. Not only students, but also those working in technical professions, teachers of high school mathematics and even their students should find these books valuable.

Dr. Uwe Schöning und Dr. Jacobo Torán sind Professoren am Institut für Theoretische Informatik in der Fakultät für Ingenieurwissenschaften und Informatik der Universität Ulm.

Kaufen Sie hier:

Horizontale Tabs

Blick ins Buch

Inhaltsverzeichnis

Titel
2
Vorwort	4
Inhaltsverzeichnis	5
Einleitung	7
1 Erste Definitionen und Ergebnisse	8
1.1 Boole’sche Formeln und Belegungen	8
1.2 Konjunktive Normalform und CSP	14
1.3 Tseitin-Codierung und serien-parallele Graphen	17
1.4 Beispiele für SAT-Codierungen	23
1.5 Autarke Belegungen	26
1.6 Craig-Interpolanten	27
1.7 Erfüllbarkeit durch Kombinatorik	29
2 Resolutionskalkül	35
2.1 Kalküle und NP versus co-NP	35
2.2 Widerlegungsvollständigkeit	37
2.3 Unit-Klauseln, Subsumption und pure Literale	43
2.4 Strategien und Restriktionen	45
2.5 Exponentielle untere Schranke für die Länge von Resolutionsbeweisen	52
3 Polynomial-lösbare Spezialfälle	62
3.1 2-KNF	62
3.2 Horn-Formeln	66
3.3 Renamable Horn-Formeln	68
3.4 Schaefer-Klassifikation	71
4 Backtracking und DPLL-Algorithmen	72
4.1 DPLL und heuristische Funktionen	74
4.2 Monien-Speckenmeyer-Algorithmus	76
4.3 Paturi-Pudlák-Zane-Algorithmus	79
4.4 DPLL in der Praxis	83
4.4.1 Klausellernen	84
4.4.2 Nicht-chronologisches Backtracking	86
5 Lokale Suche und Hamming-Kugeln	88
5.1 Deterministische lokale Suche	89
5.2 Zufällige Anfangsbelegung	92
5.3 Überdeckungscodes	94
5.4 Ein random walk-Algorithmus	97
5.5 Moser-Scheder-Algorithmus	101
5.6 GSAT, WalkSAT, Novelty	106
5.7 Harte Formeln für lokale Suche	108
6 Weitere SAT-Algorithmen	111
6.1 Ein Divide-and-Conquer-Algorithmus	111
6.2 Stålmarck-Algorithmus	114
6.3 SAT-Algorithmen mit OBDDs	118
6.4 Randomisiertes Runden und die Cross-Entropy-Methode	120
7 Zufällige Klauselmengen und physikalische Ansätze	123
7.1 Schwellenwert und Phasenübergang	123
7.2 Zufällige erfüllbare Formeln	127
7.3 Ising-Modell und physikalisch motivierte Algorithmen	129
8 Abschlussdiskussion	135
Anhang	139
Programmieren in Pseudo-Code	139
Graphen	141
Asymptotische Notation und Rekursionsgleichungen	143
Effiziente Algorithmen, P und NP	145
Probabilistische Algorithmen und die Klasse RP	149
Boole’sche Schaltkreise	151
SAT ist NP-vollständig	154
Binäre Entscheidungsgraphen (BDDs)	157
Zufallsvariablen	160
Markov-Ketten	164
Abschätzungen mit Binomialkoeffizienten	166
Literatur	168
Index	178

Weitere E-Books zum Thema: Mathematik - Algorithmik - Arithmetik

Operations Research

Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

Linearoptimierung Format: PDF

Operations Research

Linearoptimierung Format: PDF

Gewöhnliche Differenzialgleichungen

Differenzialgleichungen in Theorie und Praxis Format: PDF

Im Anschluss an Vorlesungen in Analysis und Linearer Algebra folgen an nahezu allen technischen und wirtschaftswissenschaftlich orientierten Studiengängen an Hochschulen und Universitäten als eine…

Mathematik für Informatiker

Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

Format: PDF

Mathematik für Informatiker

Format: PDF

Praktische Informationstechnik mit C#

Anwendungen und Grundlagen Format: PDF

Scientific Computing, Computational Intelligence und Computational Engineering sind zentrale Methoden der modernen Informationstechnik. Hinter diesen Begriffen stehen verschiedene Konzepte der…

Praktische Informationstechnik mit C#

Anwendungen und Grundlagen Format: PDF

Scientific Computing, Computational Intelligence und Computational Engineering sind zentrale Methoden der modernen Informationstechnik. Hinter diesen Begriffen stehen verschiedene Konzepte der…

Praktische Informationstechnik mit C#

Anwendungen und Grundlagen Format: PDF

Scientific Computing, Computational Intelligence und Computational Engineering sind zentrale Methoden der modernen Informationstechnik. Hinter diesen Begriffen stehen verschiedene Konzepte der…

Weitere Zeitschriften

BEHINDERTEPÄDAGOGIK

Für diese Fachzeitschrift arbeiten namhafte Persönlichkeiten aus den verschiedenen Fotschungs-, Lehr- und Praxisbereichen zusammen. Zu ihren Aufgaben gehören Prävention, Früherkennung, ...

Card Forum International

Card Forum International, Magazine for Card Technologies and Applications, is a leading source for information in the field of card-based payment systems, related technologies, and required reading ...

caritas

mitteilungen für die Erzdiözese FreiburgUm Kindern aus armen Familien gute Perspektiven für eine eigenständige Lebensführung zu ermöglichen, muss die Kinderarmut in Deutschland nachhaltig ...

Darum - Magazin aus Mission und Ökumene

Lesen Sie aktuelle Reportagen und Hintergrundberichte über das weltweite Engagement von Christinnen und Christen. Erhalten Sie kompakte Informationen zu den Themen Mission, Kirchen und Christen in ...

die horen

Zeitschrift für Literatur, Kunst und Kritik."...weil sie mit großer Aufmerksamkeit die internationale Literatur beobachtet und vorstellt; weil sie in der deutschen Literatur nicht nur das Neueste ...

Dr. med. Mabuse, Zeitschrift für alle Gesundheitsberufe

Zeitschrift für alle Gesundheitsberufe Seit über 40 Jahren sorgt die Zeitschrift Dr. med. Mabuse für einen anderen Blick auf die Gesundheits- und Sozialpolitik. Das Konzept einer Zeitschrift ...

DSD Der Sicherheitsdienst

Der "DSD – Der Sicherheitsdienst" ist das Magazin der Sicherheitswirtschaft. Es erscheint viermal jährlich und mit einer Auflage von 11.000 Exemplaren. Der DSD informiert über aktuelle Themen ...

Eishockey NEWS

Eishockey NEWS bringt alles über die DEL, die DEL2, die Oberliga sowie die Regionalligen und Informationen über die NHL. Dazu ausführliche Statistiken, Hintergrundberichte, Personalities ...

Fachhochschule Regensburg Hochschulführer

Studienführer der Fachhochschule Regensburg. Erscheint einmal jährlich. Unsere Aufgabe: Anwendungsorientierte Ausbildung, angewandte Forschung und praxisnahe Weiterbildung Die Hochschule ...

filmdienst#de

filmdienst.de führt die Tradition der 1947 gegründeten Zeitschrift FILMDIENST im digitalen Zeitalter fort. Wir begleiten seit 1947 Filme in allen ihren Ausprägungen und Erscheinungsformen. ...