Glossar

Komplexität von Algorithmen und Problemen

  • deterministisch: ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Für die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen
  • Kostenfunktion: Funktion zum Beschreiben des Wachstumsverhalten der Laufzeit des Algorithmus
  • Kostenmaß: in welcher Art die Kosten gemessen werden
  • nichtdeterministisch: ist ein Konzept der theoretischen Informatik, in dem Algorithmen bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nächsten Zustand haben
  • Polynomialzeit: Ein Problem wird in der Komplexitätstheorie als in Polynomialzeit lösbar beschrieben, wenn die benötigte Rechenzeit einer deterministischen Rechenmaschine mit der Problemgröße nicht stärker als mit einer Polynomfunktion wächst
  • Problemgröße: präzise Beschreibung des Umfangs der zu verarbeiteten Daten, von dem das Laufzeitverhalten maßgeblich beeinflusst wird.
  • randomisierter Algorithmus: versucht, durch die Wahl von zufälligen Zwischenergebnissen zu einem guten bzw. näherungsweise korrekten Ergebnis zu kommen
  • Reduktion: ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt werden kann.
  • Reduzierbarkeit: ein Problem wird auf ein anderes zurückgeführt
  • Zeitkomplexität eines Problems: wird durch eine untere Schranke für Kostenfunktionen von Algorithmen zur Lösung des Problems beschrieben

Ein Kommentar zu „Glossar

Schreibe einen Kommentar