Skip to main content
SpringerLink
Log in

Komplexitätstheorie

Grenzen der Effizienz von Algorithmen

  • Textbook
  • © 2003

Overview

Authors:
  1. Ingo Wegener

    1. Lehrstuhl Informatik II, Universität Dortmund, Dortmund, Deutschland

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • 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

Part of the book series: Springer-Lehrbuch (SLB)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 69.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (17 chapters)

  1. Front Matter

    Pages I-X
    Download chapter PDF

  2. Einleitung

    • Ingo Wegener
    Pages 1-11

  3. Algorithmische Probleme und ihre Komplexität

    • Ingo Wegener
    Pages 13-27

  4. Die grundlegenden Komplexitätsklassen

    • Ingo Wegener
    Pages 29-46

  5. Reduktionen — algorithmische Beziehungen zwischen Problemen

    • Ingo Wegener
    Pages 47-67

  6. Die NP-Vollständigkeitstheorie

    • Ingo Wegener
    Pages 69-82

  7. NP-vollständige und NP-äquivalente Probleme

    • Ingo Wegener
    Pages 83-93

  8. Die Komplexitätsanalyse von Problemen

    • Ingo Wegener
    Pages 95-104

  9. Die Komplexität von Approximationsproblemen — klassische Resultate

    • Ingo Wegener
    Pages 105-121

  10. Die Komplexität von Black-Box-Problemen

    • Ingo Wegener
    Pages 123-134

  11. Weitere Komplexitätsklassen und Beziehungen zwischen den Komplexitätsklassen

    • Ingo Wegener
    Pages 135-152

  12. Interaktive Beweise

    • Ingo Wegener
    Pages 153-167

  13. Das PCP-Theorem und die Komplexität von Approximationsproblemen

    • Ingo Wegener
    Pages 169-193

  14. Weitere klassische Themen der Komplexitätstheorie

    • Ingo Wegener
    Pages 195-211

  15. Die Komplexität von nichtuniformen Problemen

    • Ingo Wegener
    Pages 213-230

  16. Kommunikationskomplexität

    • Ingo Wegener
    Pages 231-263

  17. Die Komplexität boolescher Funktionen

    • Ingo Wegener
    Pages 265-291

  18. Schlussbemerkungen

    • Ingo Wegener
    Pages 293-294

  19. Back Matter

    Pages 293-321
    Download chapter PDF
Back to top

Keywords

About this book

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.

Authors and Affiliations

  • Lehrstuhl Informatik II, Universität Dortmund, Dortmund, Deutschland

    Ingo Wegener

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation