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

artist window: art to buy magazin und internetgalerie

Das artist window stellt Künstler bzw. deren Werke vor und gibt somit einen Einblick in die Ateliers und Werkstätten der Kunstschaffenden. Das besondere am artist window ist, dass die ...

Auszüge aus den Offenlegungsschriften (3 Teile)

Offenlegungsschriften der Patentanmeldungen beim Deutschen Patent- und Markenamt in drei Teilausgaben. Bibliographie, Hauptanspruch und wichtigste Zeichnung. Auszüge aus den Patentschriften ohne ...

CE-Markt

CE-Markt ist Pflichtlektüre in der Unterhaltungselektronik-Branche. Die Vermarktung von Home und Mobile Electronics mit den besten Verkaufsargumenten und Verkaufsstrategien gehören ebenso zum ...

der gefahrgutbeauftragte

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

DGZ Deutsche Gewerkschafts-Zeitung

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

DHS

Die Flugzeuge der NVA Neben unser F-40 Reihe, soll mit der DHS die Geschichte der "anderen" deutschen Luftwaffe, den Luftstreitkräften der Nationalen Volksarmee (NVA-LSK) der ehemaligen DDR ...

Die Kaufleute für Büromanagement

Prüfungs- und Praxiswissen für Ihre Ausbildung. Mehr Erfolg in der Ausbildung, sicher in alle Prüfungen gehen, im Beruf jeden Tag überzeugen: „Die Kaufleute für Büromanagement“ ist die ...

IT-BUSINESS

IT-BUSINESS ist seit mehr als 25 Jahren die Fachzeitschrift für den IT-Markt Sie liefert 2-wöchentlich fundiert recherchierte Themen, praxisbezogene Fallstudien, aktuelle Hintergrundberichte aus ...

Extracts from European Patent Specifications (3 parts)

Vom Deutschen Patent- und Markenamt erteilte Patente. Bibliographie, Patentanspruch, wichtigste Zeichnung. Thomson Reuters is the world’s leading source of intelligent information for businesses ...

DW DIREKT INFO für Architekten und Bauplaner

Direktversand an Architekturbüros, Generalplaner, Generalunternehmer, Bauträger, Bauämter, Wohnungs- und Siedlungsgesellschaften, Bauabteilungen von Industrie, Banken, Versicherungen, ...