Komplexitätstheorie : Grenzen der Effizienz von Algorithmen
著者
書誌事項
Komplexitätstheorie : Grenzen der Effizienz von Algorithmen
（Springer-Lehrbuch）
Springer, 2003
- : [pbk.]
大学図書館所蔵 件 / 全1件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
"Mit 18 abbildungen"
Includes bibliographical references (p. [311]-314) and index
内容説明・目次
内容説明
Die Komplexitatstheorie ist inzwischen eine ausgefeilte Theorie. Viele wichtige und nutzliche Ergebnisse sind schwer vermittelbar, da der Weg zu Ergebnissen fur konkrete Probleme lang und beschwerlich ist. Wahrend die NP-Vollstandigkeitstheorie die gesamte Informatik beeinflusst hat, werden die neueren Ergebnisse in der Ausbildung an den Rand gedrangt. Dieses Lehrbuch trifft eine Auswahl unter den Ergebnissen, so dass die Bedeutung der Komplexitatstheorie fur eine moderne Informatik in den Mittelpunkt ruckt.
目次
Aus dem Inhalt:
Einfuhrung.- Welche Algorithmen sind effizient?- Was kann die Komplexitatstheorie idealerweise leisten?- Komplexitatstheoretische AEhnlichkeiten.- Die NP-Vollstandigkeitstheorie.- Techniken zum Entwurf von Reduktionen.- Die Komplexitatsanalyse von Problemen.- Pseudopolynomielle Algorithmen und starke NP-Vollstandigkeit.- Die polynomielle Hierarchie.- Interaktive Beweise, Zero-Knowledge Beweise und das PCP-Theorem.- Die Komplexitat von Approximationsproblemen.- Ein Einblick in weitere Themen der Komplexitatstheorie.- Komplexitatstheoretische Unterschiede zwischen Software und Hardware.- Die Komplexitat boolescher Funktionen.- Kommunikationskomplexitat.- Anhang.- Literatur.- Index.
「Nielsen BookData」 より