Komplexitätstheorie
Grenzen der Effizienz von Algorithmen
Buch in deiner Nähe kaufen
Beschreibung
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.
Die Komplexitätstheorie ist inzwischen eine ausgefeilte Theorie. Viele wichtige und nützliche Ergebnisse sind nicht leicht zu vermitteln, da der Weg zu Ergebnissen für konkrete Probleme lang und beschwerlich ist. Während die NP-Vollständigkeitstheorie die gesamte Informatik beeinflusst 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.
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
Autor*in
Ingo Wegener
Themen in »Komplexitätstheorie«
ACE Algorithmen Hardware Informatik Komplexität Komplexitätstheorie Optimierung Rucksackproblem Verifikation tar algorithm analysis and problem complexity