Komplexitätstheorie Grenzen der Effizienz von Algorithmen - neues Buch

EAN (ISBN-13): 9783540001614
ISBN (ISBN-10): 3540001611
Gebundene Ausgabe
Taschenbuch
Erscheinungsjahr: 2003
Herausgeber: Springer
321 Seiten
Gewicht: 0,503 kg
Sprache: ger/Deutsch

Buch in der Datenbank seit 2007-04-28T23:12:13+02:00 (Berlin)
Detailseite zuletzt geändert am 2024-04-10T09:01:19+02:00 (Berlin)
ISBN/EAN: 3540001611

ISBN - alternative Schreibweisen:
3-540-00161-1, 978-3-540-00161-4
Alternative Schreibweisen und verwandte Suchbegriffe:
Autor des Buches: wege, ingo wegener, berlin
Titel des Buches: taschenbuch der algorithmen, der springer, wegener, komplexität, komplex, theorie, lehrbuch, komplexitätstheorie grenzen der effizienz von algorithmen

---

Daten vom Verlag:

Autor/in: Ingo Wegener
Titel: Springer-Lehrbuch; Komplexitätstheorie - Grenzen der Effizienz von Algorithmen
Verlag: Springer; Springer Berlin
322 Seiten
Erscheinungsjahr: 2003-03-10
Berlin; Heidelberg; DE
Sprache: Deutsch
64,99 € (DE)
66,81 € (AT)
72,00 CHF (CH)
Available
X, 322 S.

BC; Hardcover, Softcover / Informatik, EDV/Informatik; Kodierungstheorie und Verschlüsselung (Kryptologie); Verstehen; ACE; Algorithmen; Hardware; Informatik; Komplexität; Komplexitätstheorie; Optimierung; Rucksackproblem; Verifikation; tar; algorithm analysis and problem complexity; Coding and Information Theory; Computer System Implementation; Mathematical Logic and Foundations; Algorithms; Computer Science Logic and Foundations of Programming; Formal Languages and Automata Theory; Informationstheorie; Systemanalyse und -design; Mathematik: Logik; Mathematische Grundlagen; Algorithmen und Datenstrukturen; Theoretische Informatik; EA

1. Einleitung.- 1.1 Was ist Kornplexitätstheorie?.- 1.2 Zum didaktischen Hintergrund.- 1.3 Überblick.- 1.4 Weiterftihrende Literatur.- 2. Algorithmische Probleme und ihre Kornplexität.- 2.1 Was sind algorithmische Probleme?.- 2.2 Einige wichtige algorithmische Probleme.- 2.3 Wie wird die Rechenzeit eines Algorithmus gemessen?.- 2.4 Die Komplexität algorithmischer Probleme.- 3. Die grundlegenden Komplexitätsklassen.- 3.1 Die Sonderrolle polynomieller Rechenzeiten.- 3.2 Randomisierte Algorithmen.- 3.3 Die grundlegenden Komplexitatsklassen für algorithmische Probleme.- 3.4 Die grundlegenden Komplexitatsklassen für Entscheidungsprobleme.- 3.5 Nichtdeterminismus als Spezialfall von Randomisierung.- 4. Reduktionen - algorithmische Beziehungen zwischen Problemen.- 4.1 Wann sind sich Probleme algorithmisch ähnlich?.- 4.2 Reduktionen zwischen den verschiedenen Varianten eines Problems.- 4.3 Reduktionen zwischen verwandten Problemen.- 4.4 Reduktionen zwischen nicht verwandten Problemen.- 4.5 DieSonderrolle polynomieller Reduktionen.- 5. Die NP-Vollständigkeitstheorie.- 5.1 Grundlegende Überlegungen.- 5.2 Probleme in NP.- 5.3 Alternative Charakterisierungen von NP.- 5.4 Das Theorem von Cook.- 6. NP-vollständige und NP-äquivalente Probleme.- 6.1 Grundlegende Überlegungen.- 6.2 Rundreiseprobleme.- 6.3 Rucksackprobleme.- 6.4 Aufteilungsprobleme und Lastverteilungsprobleme.- 6.5 Cliquenprobleme.- 6.6 Teambildungsprobleme.- 6.7 Meisterschaftsprobleme.- 7. Die Komplexitätsanalyse von Problemen.- 7.1 Die Trennlinie zwischen einfachen und schwierigen Varianteneines Problems.- 7.2 Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit.- 7.3 Ein Überblick über die betrachteten NP-Vollständigkeitsbeweise.- 8. Die Komplexität von Approximationsproblemen - klassische Resultate.- 8.1 Komplexitätsklassen.- 8.2 Approximationsalgorithmen.- 8.3 Die Lückentechnik.- 8.4 Approximationserhaltende Reduktionen.- 8.5 Vollständige Approximationsprobleme.- 9. Die Komplexität von Black-Box-Problemen.- 9.1 Black-Box-Optimierung.- 9.2 Das Minimax-Prinzip von Yao.- 9.3 Untere Schranken für die Black-Box-Komplexität.- 10. Weitere Komplexitätsklassen und Beziehungen zwischen den Komplexitätsklassen.- 10.1 Grundlegende Überlegungen.- 10.2 Die Komplexitätsklassen innerhalb von NP und co-NP.- 10.3 Orakelklassen.- 10.4 Die polynomielle Hierarchie.- 10.5 BPP, NP und die polynomielle Hierarchie.- 11. Interaktive Beweise.- 11.1 Grundlegende Überlegungen.- 11.2 Interaktive Beweissysteme.- 11.3 Zur Komplexität des Graphenisomorphieproblems.- 11.4 Beweissysteme, die kein Wissen preisgeben.- 12. Das PCP-Theorem und die Komplexität von Approximationsproblemen.- 12.1 Randomisierte Verifikation von Beweisen.- 12.2 Das PCP-Theorem.- 12.3 Das PCP-Theorem und Nichtapproximierbarkeitsresultate.- 12.4 Das PCP-Theorem und APX-Vollständigkeit.- 13. Weitere klassische Themen der Komplexitätstheorie.- 13.1 Überblick.- 13.2 Speicherplatzbasierte Komplexitätsklassen.- 13.3 PSPACE-vollständige Probleme.- 13.4 Nichtdeterminismus und Determinismus bei Platzschranken.- 13.5 Nichtdeterminismus und Komplementbildung bei präzisen Platzschranken.- 13.6 Komplexitätsklassen innerhalb von P.- 13.7 Die Komplexität von Anzahlproblemen.- 14. Die Komplexität von nichtuniformen Problemen.- 14.1 Grundlegende Überlegungen.- 14.2 Simulationen von Turingmaschinen durch Schaltkreise.- 14.3 Simulationen von Schaltkreisen durch nichtuniforme Turingmaschinen.- 14.4 Branchingprogramme und Platzbedarf.- 14.5 Polynomielle Schaltkreise für Probleme in BPP.- 14.6 Komplexitätsklassen für Berechnungen mit Hilfsinformationen.- 14.7 Gibt es polynomielle Schaltkreise für alle Probleme in NP?.- 15. Kommunikationskomplexität.- 15.1 Das Kommunikationsspiel.- 15.2 Untere Schranken für die Kommunikationskomplexität.- 15.3 Nichtdeterministische Kommunikationsprotokolle.- 15.4 Randomisierte Kommunikationsprotokolle.- 15.5 Kommunikationskomplexität und VLSI-Schaltkreise.- 15.6 Kommunikationskomplexität und die Rechenzeit von Turingmaschinen.- 16. Die Komplexität boolescher Funktionen.- 16.1 Grundlegende Überlegungen.- 16.2 Die Größe von Schaltkreisen.- 16.3 Die Tiefe von Schaltkreisen.- 16.4 Die Größe von tiefenbeschränkten Schaltkreisen.- 16.5 Die Größe von tiefenbeschränkten Thresholdschaltkreisen.- 16.6 Die Größe von Branchingprogrammen.- 16.7 Reduktionskonzepte.- Schlussbemerkungen.- A. Anhang.- A2. Ergebnisse aus der Wahrscheinlichkeitstheorie.
Neuartige Einführung in das klassische Gebiet der Komplexitätstheorie Integration moderner Themen wie PCP-Theorem, Nichtapproximierbarkeit, Randomisierung und Kommunikationskomplexität Informelle Darstellung von Beweis-Ideen, bevor formale Beweise folgen