Komplexitätstheorie: Grenzen der Effizienz von Algorithmen by Ingo WegenerKomplexitätstheorie: Grenzen der Effizienz von Algorithmen by Ingo Wegener

Komplexitätstheorie: Grenzen der Effizienz von Algorithmen

byIngo Wegener

Paperback | March 10, 2003 | German

Pricing and Purchase Info

$70.50 online 
$77.95 list price save 9%
Earn 353 plum® points

Prices and offers may vary in store

Quantity:

In stock online

Ships free on orders over $25

Not available in stores

about

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.
Title:Komplexitätstheorie: Grenzen der Effizienz von AlgorithmenFormat:PaperbackDimensions:331 pagesPublished:March 10, 2003Publisher:Springer Berlin HeidelbergLanguage:German

The following ISBNs are associated with this title:

ISBN - 10:3540001611

ISBN - 13:9783540001614

Look for similar items by category:

Reviews

Table of Contents

Aus dem Inhalt:Einführung.- Welche Algorithmen sind effizient?- Was kann die Komplexitätstheorie idealerweise leisten?- Komplexitätstheoretische Ähnlichkeiten.- Die NP-Vollständigkeitstheorie.- Techniken zum Entwurf von Reduktionen.- Die Komplexitätsanalyse von Problemen.- Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit.- Die polynomielle Hierarchie.- Interaktive Beweise, Zero-Knowledge Beweise und das PCP-Theorem.- Die Komplexität von Approximationsproblemen.- Ein Einblick in weitere Themen der Komplexitätstheorie.- Komplexitätstheoretische Unterschiede zwischen Software und Hardware.- Die Komplexität boolescher Funktionen.- Kommunikationskomplexität.- Anhang.- Literatur.- Index.