Ingo Wegener

Komplexitätstheorie (eBook, PDF)

Grenzen der Effizienz von Algorithmen

• Format: PDF

Produktbeschreibung

Die Komplexitätstheorie untersucht die Mindestressourcen zur Lösung algorithmischer Probleme und damit die Grenzen des mit den vorhandenen Ressourcen Machbaren. Ihre Ergebnisse verhindern, dass sich die Suche nach effizienten Algorithmen auf unerreichbare Ziele konzentriert. Insofern hat die NP-Vollständigkeitstheorie die Entwicklung der gesamten Informatik beeinflusst. Die Komplexitätstheorie reagiert auf alle neuen algorithmischen Konzepte.

Dieses Lehrbuch wählt einen Einstieg in die Komplexitätstheorie, bei dem die Randomisierung als Schlüsselkonzept angesehen wird. Die Auswahl der Inhalte betont den Bezug zu konkreten Anwendungen und rückt die Bedeutung der Komplexitätstheorie für eine moderne Informatik in den Mittelpunkt.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer Berlin Heidelberg
• Seitenzahl: 322
• Erscheinungstermin: 11. März 2013
• Deutsch
• ISBN-13: 9783642555480
• Artikelnr.: 53136161

Autorenporträt

Ingo Wegener, Universität Dortmund

Inhaltsangabe

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.