Komplexitätstheorie

Grenzen der Effizienz von Algorithmen

AvIngo Wegener

Häftad, Tyska, 2003

Del i serien Springer-Lehrbuch

748 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

E-bok

359 kr

Beskrivning

Die Komplexitätstheorie ist inzwischen eine ausgefeilte Theorie. Viele wichtige und nützliche Ergebnisse sind schwer vermittelbar, da der Weg zu Ergebnissen für konkrete Probleme lang und beschwerlich ist. Während die NP-Vollständigkeitstheorie die gesamte Informatik beeinflußt hat, werden die neueren Ergebnisse in der Ausbildung an den Rand gedrängt. Dieses Lehrbuch trifft eine Auswahl unter den Ergebnissen, so dass die Bedeutung der Komplexitätstheorie für eine moderne Informatik in den Mittelpunkt rückt.

Produktinformation

Utgivningsdatum:2003-03-10
Mått:155 x 235 x 19 mm
Vikt:505 g
Format:Häftad
Språk:Tyska
Serie:Springer-Lehrbuch
Antal sidor:322
Upplaga:2003
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783540001614

Utforska kategorier

Innehållsförteckning

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.

Mer från samma författare

Numbers, Information and Complexity

Ning Cai, Gunter Dueck, Ingo Althöfer, Ning Cai, Gunter Dueck, Levon H. Khachatrian, Marcus Pinsker, G. Sarkozy, Ingo Wegener, Zhen Zhang

Inbunden, 2000

2 205 kr

Branching Programs and Binary Decision Diagrams

Ingo Wegener

Inbunden, 2000

1 774 kr

Numbers, Information and Complexity

Ingo Althöfer, Ning Cai, Gunter Dueck, Levon H. Khachatrian, Marcus Pinsker, G. Sarkozy, Ingo Wegener, Zhen Zhang

Häftad, 2010

2 205 kr

Numbers, Information and Complexity

Zhen Zhang, Ingo Wegener, G. Sarkozy, Marcus Pinsker, Levon H. Khachatrian, Gunter Dueck, Ning Cai, Ingo Althofer

E-bok

2013

2 862 kr

Anorexia nervosa

Katrin Imbierowicz, Ambra Marx, Ingo Wegener, Nora Kämpfer, Marcel Lüssem, Franziska Geiser

Häftad, 2025

493 kr

Kompendium Theoretische Informatik — eine Ideensammlung

Ingo Wegener

E-bok

2013

390 kr

Theoretische Informatik

Ingo Wegener

E-bok

2015

520 kr

Starthilfe Informatik

Ingo Wegener, Volker Claus, Dietrich Boles, Hans-Jurgen Appelrath

E-bok

2013

559 kr

Suchprobleme

Ingo Wegener, Rudolf Ahlswede

E-bok

2013

537 kr

Theoretische Informatik

Ingo Wegener

E-bok

2013

542 kr

Mer från samma serie

Sozialpsychologie

Johannes Ullrich, Wolfgang Stroebe, Miles Hewstone

Inbunden, 2023

656 kr

Lineare Algebra

Gilbert Strang

Häftad, 2003

675 kr

Robotik: Programmierung intelligenter Roboter

Hans-Jürgen Siegert, Siegfried Bocionek

Häftad, 1996

469 kr

Werkstoffkunde

Hans-Jürgen Bargel

Inbunden, 2022

777 kr

Biologie für Mediziner

Werner Buselmaier, Joana Haussig

Häftad, 2018

409 kr

Teilchen und Kerne

Bogdan Povh, Klaus Rith, Christoph Scholz, Frank Zetsche, Werner Rodejohann

Häftad, 2013

521 kr

Recht der Ordnungswidrigkeiten

Wolfgang Mitsch

Häftad, 2005

366 kr

Rechnerorganisation

Hans Liebig

Häftad, 2003

521 kr

Empirische Wirtschaftsforschung

Thomas K. Bauer, Michael Fertig, Christoph M. Schmidt

Häftad, 2009

521 kr

Vergleichende Tierphysiologie

Gerhard Heldmaier, Gerhard Neuweiler

Inbunden, 2003

1 171 kr

Du kanske också är intresserad av

Effiziente Algorithmen für grundlegende Funktionen

Ingo Wegener

Häftad, 1989

520 kr

Automata, Languages and Programming

Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener

Häftad, 2006

1 139 kr

Advances in Computational Intelligence

Hans-Paul Schwefel, Ingo Wegener, K.D. Weinert

Häftad, 2010

1 106 kr

Suchprobleme

Ingo Wegener, Rudolf Ahlswede

E-bok

2013

537 kr

Anorexia nervosa

Katrin Imbierowicz, Ambra Marx, Ingo Wegener, Nora Kämpfer, Marcel Lüssem, Franziska Geiser

Häftad, 2025

493 kr

Starthilfe Informatik

Ingo Wegener, Volker Claus, Dietrich Boles

E-bok

2013

542 kr

Numbers, Information and Complexity

Ning Cai, Gunter Dueck, Ingo Althöfer, Ning Cai, Gunter Dueck, Levon H. Khachatrian, Marcus Pinsker, G. Sarkozy, Ingo Wegener, Zhen Zhang

Inbunden, 2000

2 205 kr

Theoretische Informatik

Ingo Wegener

E-bok

2013

542 kr

Theoretische Informatik

Ingo Wegener

E-bok

2015

520 kr

Automata, Languages and Programming

Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener

Häftad, 2006

1 139 kr

Komplexitätstheorie

Grenzen der Effizienz von Algorithmen

AvIngo Wegener

Häftad, Tyska, 2003

Del i serien Springer-Lehrbuch

748 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

E-bok

359 kr

Beskrivning

Produktinformation

Utgivningsdatum:2003-03-10
Mått:155 x 235 x 19 mm
Vikt:505 g
Format:Häftad
Språk:Tyska
Serie:Springer-Lehrbuch
Antal sidor:322
Upplaga:2003
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783540001614

Utforska kategorier

Innehållsförteckning

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.