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

Bibel für heute

BIBEL FÜR HEUTE ist die Bibellese für alle, die die tägliche Routine durchbrechen wollen: Um sich intensiver mit einem Bibeltext zu beschäftigen. Um beim Bibel lesen Einblicke in Gottes ...

Branchenbrief international - Spielzeugbranche aktuell

Informationsdienst für die Spielwarenbranche Seit 1980 ist der „BRANCHENBRIEF INTERNATIONAL - Spielzeugbranche aktuell" der Informationsdienst der Spielwarenbranche, bekannt unter dem Kürzel ...

care konkret

care konkret ist die Wochenzeitung für Entscheider in der Pflege. Ambulant wie stationär. Sie fasst topaktuelle Informationen und Hintergründe aus der Pflegebranche kompakt und kompetent für Sie ...

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

Correo

La Revista de Bayer CropScience para la Agricultura ModernaPflanzenschutzmagazin für den Landwirt, landwirtschaftlichen Berater, Händler und am Thema Interessierten mit umfassender ...

dental:spiegel

dental:spiegel - Das Magazin für das erfolgreiche Praxisteam. Der dental:spiegel gehört zu den Top 5 der reichweitenstärksten Fachzeitschriften für Zahnärzte in Deutschland (laut LA-DENT 2011 ...

DGZ Deutsche Gewerkschafts-Zeitung

Das Magazin der christlichen Gewerkschaften: Christliche Gewerkschaft Metall (CGM) Christliche Gewerkschaft Deutscher Eisenbahner (CGDE) Christliche Gewerkschaft Bergbau, Chemie, Energie (CGBCE) ...

ea evangelische aspekte

evangelische Beiträge zum Leben in Kirche und Gesellschaft Die Evangelische Akademikerschaft in Deutschland ist Herausgeberin der Zeitschrift evangelische aspekte Sie erscheint viermal im Jahr. In ...

DVGW energie | wasser-praxis

Die »DVGW energie | wasser-praxis« ist die führende Fachzeitschrift der deutschen Gas- und Wasser Branche. 11 Mal im Jahr informiert sie mit technischen Fachbeiträgen, praxisorientierten ...

Euro am Sonntag

Deutschlands aktuelleste Finanz-Wochenzeitung Jede Woche neu bietet €uro am Sonntag Antworten auf die wichtigsten Fragen zu den Themen Geldanlage und Vermögensaufbau. Auch komplexe Sachverhalte ...