Cantitate/Preț
Produs
Total produse
Vezi coșul
Komplexitätstheorie: Grenzen der Effizienz von Algorithmen de Ingo Wegener

Komplexitätstheorie: Grenzen der Effizienz von Algorithmen: Springer-Lehrbuch

Autor Ingo Wegener
de Limba Germană Paperback – 10 mar 2003
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.
Citește tot Restrânge

Din seria Springer-Lehrbuch

  • Physik für Biologen: Die physikalischen Grundlagen der Biophysik und anderer Naturwissenschaften
    Preț: 38187 lei
  • 5% Basiswissen Biochemie: mit Pathobiochemie
    Preț: 46069 lei
  • 5% Kinder- und Jugendmedizin
    Preț: 46435 lei
  • 11% Meteorologie: Eine interdisziplinäre Einführung in die Physik der Atmosphäre
    Preț: 41626 lei
  • Mathematik für Chemiker: Eine Einfiihxung
    Preț: 22983 lei
  • Statistisch gesichert und trotzdem falsch?: Vom (Un-)Wesen statistischer Schlüsse
    Preț: 10442 lei
  • Medizinische Statistik mit R und Excel: Einführung in die RExcel- und R-Commander-Oberflächen zur statistischen Auswertung
    Preț: 18233 lei
  • Fallrepetitorium Familien- und Erbrecht
    Preț: 17176 lei
  • Zwangsvollstreckungsrecht im Assessorexamen und in der Praxis
    Preț: 22533 lei
  • 5% Basiswissen Chirurgie
    Preț: 31313 lei
  • 5% Atlas der Anatomie des Menschen: mit Muskeltabellen
    Preț: 38223 lei
  • Funktionentheorie 1
    Preț: 32242 lei
  • 5% Allgemeine und Spezielle Pathologie
    Preț: 54166 lei
  • 5% Poster Stoffwechsel
    Preț: 4524 lei
  • Gerthsen Physik
    Preț: 52503 lei
  • 5% Lunge und Atemwege
    Preț: 27075 lei
  • 5% Basiswissen Neurologie
    Preț: 34952 lei
  • Elektronische Schaltungen 1: Grundlagen, Analyse, Aufbau
    Preț: 36247 lei
  • 5% Urologie
    Preț: 47732 lei
  • Allgemeine Psychologie für Bachelor: Denken - Urteilen, Entscheiden, Problemlösen. Lesen, Hören, Lernen im Web.
    Preț: 24850 lei
  • 5% Basiswissen Innere Medizin
    Preț: 35076 lei
  • Kernphysik: Eine Einführung
    Preț: 42644 lei
  • Grundkurs Theoretische Physik 6: Statistische Physik
    Preț: 47356 lei
  • Analysis 1
    Preț: 31603 lei
  • Finanzwirtschaftliches Risikomanagement
    Preț: 25764 lei
  • Eine Einführung in die Statistik und ihre Anwendungen
    Preț: 21711 lei
  • Operations Research: Eine Einführung
    Preț: 23960 lei
  • Wirtschaftspsychologie für Bachelor
    Preț: 25890 lei
  • Vertragsgestaltung: Eine methodisch-didaktische Einführung
    Preț: 25181 lei
  • 5% Basiswissen Humangenetik
    Preț: 27979 lei
  • 5% Psychiatrie: Einschließlich Psychotherapie
    Preț: 37636 lei
  • 5% Anamnese und klinische Untersuchung
    Preț: 68582 lei
  • 5% Pathophysiologie
    Preț: 73050 lei
  • 5% Biologie für Mediziner
    Preț: 24317 lei
  • Systemanalyse: Einführung in die mathematische Modellierung natürlicher Systeme
    Preț: 35425 lei
  • Lernskript Psychologie: Die Grundlagenfächer kompakt
    Preț: 26802 lei
  • Finanzmanagement: Lehr- und Praxisbuch für Investition, Finanzierung und Finanzcontrolling
    Preț: 30557 lei
  • Physiologie kompakt
    Preț: 31790 lei
  • Theorien in der biologiedidaktischen Forschung: Ein Handbuch für Lehramtsstudenten und Doktoranden
    Preț: 23966 lei
  • Kosten- und Erlösrechnung: Eine controllingorientierte Einführung
    Preț: 21768 lei
  • Keynesianische Makroökonomik: Zins, Beschäftigung, Inflation und Wachstum
    Preț: 27238 lei
  • Motivation und Emotion: Allgemeine Psychologie für Bachelor
    Preț: 23735 lei
  • 5% Basiswissen Psychiatrie und Psychotherapie
    Preț: 30829 lei
  • 5% Pharmakotherapie: Klinische Pharmakologie
    Preț: 45731 lei
  • Biologische Psychologie
    Preț: 35304 lei
  • Arbeits-, Organisations- und Personalpsychologie für Bachelor
    Preț: 23777 lei
  • 11% Kognitive Neurowissenschaften
    Preț: 58459 lei
  • Einführung in die Mathematik: Hintergründe der Schulmathematik
    Preț: 33294 lei
  • 11% Verteilungsfreie Methoden in der Biostatistik
    Preț: 51291 lei
  • Entscheidungstheorie: Klassische Konzepte und Fuzzy-Erweiterungen
    Preț: 22203 lei

Preț: 47999 lei

Nou

Puncte Express: 720
Preț estimativ în valută:
9186€ • 9542$ • 7630£

Carte tipărită la comandă

Livrare economică 03-17 februarie 25

 Adaugă în coș

Wish list
Gift list
Am citit!
Adaugă în listă
Preluare comenzi: 021 569.72.76

Specificații

ISBN-13: 9783540001614
ISBN-10: 3540001611
Pagini: 322
Ilustrații: X, 322 S.
Dimensiuni: 155 x 235 x 17 mm
Greutate: 0.47 kg
Ediția:2003
Editura: Springer Berlin, Heidelberg
Colecția Springer
Seria Springer-Lehrbuch

Locul publicării:Berlin, Heidelberg, Germany

Public țintă

Graduate

Cuprins

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.

Textul de pe ultima copertă

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.

Caracteristici

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