Komplexitätstheorie: Grenzen Der Effizienz Von Algorithmen

ISBN-13: 9783540001614 / Niemiecki / Twarda / 2003 / 322 str.

Ingo Wegener

Opis

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."

Spis treści

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.

Blurb

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.