Das Erfüllbarkeitsproblem SAT: Algorithmen und Analysen

Uwe Schöning; Jacobo Torán

doi:10.58662/9783865417244

Keywords

Search publication

Bibliographic data

Edition: 1/2012
Copyright Year: 2012
ISBN-Print: 978-3-86541-473-1
ISBN-Online: 978-3-86541-724-4
Publisher: Lehmanns Media, Berlin
Language: German
Pages: 181
Product Type: Monograph

1. Vorwort No access
2. Inhaltsverzeichnis No access
Einleitung No access Pages 9 - 9
1. 1.1 Boole’sche Formeln und Belegungen No access
2. 1.2 Konjunktive Normalform und CSP No access
3. 1.3 Tseitin-Codierung und serien-parallele Graphen No access
4. 1.4 Beispiele für SAT-Codierungen No access
5. 1.5 Autarke Belegungen No access
6. 1.6 Craig-Interpolanten No access
7. 1.7 Erfüllbarkeit durch Kombinatorik No access
1. 2.1 Kalküle und NP versus co-NP No access
2. 2.2 Widerlegungsvollständigkeit No access
3. 2.3 Unit-Klauseln, Subsumption und pure Literale No access
4. 2.4 Strategien und Restriktionen No access
5. 2.5 Exponentielle untere Schranke für die Länge von Resolutionsbeweisen No access
1. 3.1 2-KNF No access
2. 3.2 Horn-Formeln No access
3. 3.3 Renamable Horn-Formeln No access
4. 3.4 Schaefer-Klassifikation No access
1. 4.1 DPLL und heuristische Funktionen No access
2. 4.2 Monien-Speckenmeyer-Algorithmus No access
3. 4.3 Paturi-Pudlák-Zane-Algorithmus No access
4. 1. 4.4.1 Klausellernen No access
  2. 4.4.2 Nicht-chronologisches Backtracking No access
1. 5.1 Deterministische lokale Suche No access
2. 5.2 Zufällige Anfangsbelegung No access
3. 5.3 Überdeckungscodes No access
4. 5.4 Ein random walk-Algorithmus No access
5. 5.5 Moser-Scheder-Algorithmus No access
6. 5.6 GSAT, WalkSAT, Novelty No access
7. 5.7 Harte Formeln für lokale Suche No access
1. 6.1 Ein Divide-and-Conquer-Algorithmus No access
2. 6.2 Stålmarck-Algorithmus No access
3. 6.3 SAT-Algorithmen mit OBDDs No access
4. 6.4 Randomisiertes Runden und die Cross-Entropy-Methode No access
1. 7.1 Schwellenwert und Phasenübergang No access
2. 7.2 Zufällige erfüllbare Formeln No access
3. 7.3 Ising-Modell und physikalisch motivierte Algorithmen No access
8 Abschlussdiskussion No access Pages 141 - 144
1. Programmieren in Pseudo-Code No access
2. Graphen No access
3. Asymptotische Notation und Rekursionsgleichungen No access
4. Effiziente Algorithmen, P und NP No access
5. Probabilistische Algorithmen und die Klasse RP No access
6. Boole’sche Schaltkreise No access
7. SAT ist NP-vollständig No access
8. Binäre Entscheidungsgraphen (BDDs) No access
9. Zufallsvariablen No access
10. Markov-Ketten No access
11. Abschätzungen mit Binomialkoeffizienten No access
Literatur No access Pages 174 - 183
Index No access Pages 184 - 187