Komplexitätstheorie

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Berechenbarkeit und Ressourcenverbrauch (hauptsächlich Ausführungsgeschwindigkeit und Speicherplatzbedarf ) von Algorithmen auf verschiedenen mathematisch definierten Rechnermodellen sowie der Güte derartiger Algorithmen. Kostenmaße eine wichtige Rolle.

Als Rechnermodelltypen werden dabei hauptsächlich

deterministische Maschinen (s.a. Determinismus (Algorithmus) )
randomisierte Maschinen
nichtdeterministische Maschinen (s.a. Nichtdeterminismus )
randomisierte nichtdeterministische Maschinen und
quantenmechanische Maschinen

untersucht. In der Regel werden diese

Registermaschinen oder
spezielle Turingmaschinen

realisiert.

Die Einteilung von algorithmischen Problemen in Komplexitätsklassen erfolgt in

Zeitkomplexität und
Platzkomplexität

Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist Kryptographie .

Siehe auch : P/NP-Problem NP (Komplexitätsklasse)

Bücher zum Thema Komplexitätstheorie

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Komplexit%E4tstheorie.html">Komplexitätstheorie </a>