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

Argumente + Fakten der Medizin

Medizin und Gesundheit Aktuell zu Konzepten, Forschung, Therapie, Diagnostik und Klinik Seit April 1991 erscheint regelmäßig eine monatliche Fachzeitschrift für den jungen niedergelassenen ...

AUTOCAD Magazin

Die herstellerunabhängige Fachzeitschrift wendet sich an alle Anwender und Entscheider, die mit Softwarelösungen von Autodesk arbeiten. Das Magazin gibt praktische ...

Card-Forum

Card-Forum ist das marktführende Magazin im Themenbereich der kartengestützten Systeme für Zahlung und Identifikation, Telekommunikation und Kundenbindung sowie der damit verwandten und ...

D.i.D. Diakonie in Düsseldorf .

Berichte und Neuigkeiten aus den Arbeitsgebieten der Diakonie in Düsseldorf. Gibt es Gebrauchsanweisungen, die einen in die Welt des Glaubens einführen? Nun, natürlich nicht in der Art, wie es ...

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 ...

Gastronomie Report

News & Infos für die Gastronomie: Tipps, Trends und Ideen, Produkte aus aller Welt, Innovative Konzepte, Küchentechnik der Zukunft, Service mit Zusatznutzen und vieles mehr. Frech, offensiv, ...

der gefahrgutbeauftragte

Gefahrgutvorschriften sind kompliziert, sie in die Praxis umzusetzen ist es auch. der gefahrgutbeauftragte macht die Arbeit leichter: Gefahrgutbeauftragten, beauftragten Personen und ...

Die Medizinischen Fachangestellten

Prüfungs- und Praxiswissen für Zahnmedizinische Fachangestellte Mehr Erfolg in der Ausbildung, sicher in alle Prüfungen gehen, im Beruf jeden Tag überzeugen: „Die Zahnmedizinische ...

dima

Bau und Einsatz von Werkzeugmaschinen für spangebende und spanlose sowie abtragende und umformende Fertigungsverfahren. dima - die maschine - bietet als Fachzeitschrift die Kommunikationsplattform ...

elektrobörse handel

elektrobörse handel gibt einen facettenreichen Überblick über den Elektrogerätemarkt: Produktneuheiten und -trends, Branchennachrichten, Interviews, Messeberichte uvm.. In den monatlichen ...