Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Berechenbarkeit und dem Ressourcenverbrauch (hauptsächlich Ausführungsgeschwindigkeit und Speicherplatzbedarfplatzbedarf) von Algorithmen auf verschiedenen mathematisch definierten formalen Rechnermodellen, sowie der Güte derartiger Algorithmen. Kostenmaße spielen eine wichtige Rolle.
Als Rechnermodelltypen werden dabei hauptsächlich
- deterministische Maschinen (siehe auch Determinismus (Algorithmus)),
- randomisierte Maschinen,
- nichtdeterministische Maschinen (siehe auch Nichtdeterminismus),
- randomisierte nichtdeterministische Maschinen und
- quantenmechanische Maschinen
untersucht. In der Regel werden diese als
- Registermaschinen oder
- spezielle Turingmaschinen
realisiert.
Die Einteilung von algorithmischen Problemen in Komplexitätsklassen erfolgt
in
Ein wichtiger Anwendungsbereich der Komplexitätstheorie ist die Kryptographie.
Siehe auch: P/NP-Problem, NP (Komplexitätsklasse)
Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz. |
Webtipps: Niederlande | Plattdeutsch