K. Rüdiger Reischuk

Komplexitätstheorie Band I: Grundlagen

Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus. 2. , völlig neu bearb. und erweitert Auflage 1999.

kartoniert , 380 Seiten

ISBN 3519122758

EAN 9783519122753

Veröffentlicht Januar 1999

Verlag/Hersteller Vieweg+Teubner Verlag

Auch erhältlich als:

pdf eBook

€ 36,99

€ 49,95 inkl. MwSt.

Auf die Wunschliste

Weitere interessante Themen

Beschreibung

Die Komplexitätstheorie untersucht den algorithmischen Aufwand zur Lösung von Problemen mit Hilfe einer Maschine. Dabei werden Rechnermodelle wie Turing-Maschinen oder Registermaschinen verwendet, um von speziellen Architektur- und Implementationsdetails unabhängige Ergebnisse zu gewinnen. Neben den klassischen Komplexitätsmaßen Zeitaufwand und Speicherplatzbedarf werden eine Reihe weiterer Maße zur Strukturierung eingesetzt. Algorithmische Probleme werden diesbezüglich klassifiziert und in Beziehung zueinander gesetzt. Die Suche nach effizienten Lösungsstrategien wird komplementiert durch den (im allgemeinen sehr schwierigen) Nachweis unterer Schranken für den Lösungsaufwand.