Berechnungsmodell

Im Informatik, und genauer gesagt in Computerbarkeitstheorie und Computerkomplexitätstheorie, a Berechnungsmodell ist ein Modell, das beschreibt, wie eine Ausgabe von a Mathematische Funktion wird mit einem Eingang berechnet. Ein Modell beschreibt, wie Einheiten von Berechnungen, Erinnerungen und Kommunikation organisiert werden.[1] Das Rechenkomplexität von einem Algorithmus kann mit einem Berechnungsmodell gemessen werden. Die Verwendung eines Modells ermöglicht die Untersuchung der Leistung von Algorithmen unabhängig von den Variationen, die spezifisch für bestimmte sind Implementierungen und spezifische Technologie.

Modelle

Berechnungsmodelle können in drei Kategorien eingeteilt werden: sequentielle Modelle, Funktionsmodelle und gleichzeitige Modelle.

Sequentielle Modelle

Sequentielle Modelle umfassen:

Funktionsmodelle

Funktionsmodelle umfassen:

Gleichzeitige Modelle

Gleichzeitige Modelle umfassen:

Einige dieser Modelle haben beide deterministisch und Nichtdeterministisch Varianten. Nichtdeterministische Modelle sind für die praktische Berechnung nicht nützlich. Sie werden in der Untersuchung von verwendet Rechenkomplexität von Algorithmen.

Modelle unterscheiden sich in ihrer Ausdruckskraft; Zum Beispiel jede Funktion, die von a berechnet werden kann Endliche Zustandsmaschine kann auch von a berechnet werden Turing Maschine, aber nicht umgekehrt.

Verwendet

Im Bereich der Laufzeit Analyse von AlgorithmenEs ist üblich, ein Rechenmodell in Bezug auf zu spezifizieren primitive Operationen erlaubt, die Einheitenkosten haben oder einfach Einheitskostenvorgänge. Ein häufig verwendetes Beispiel ist das Zufallszugriffsmaschine, die Einheitenkosten für Lesen und Schreibzugriff auf alle Speicherzellen enthält. In dieser Hinsicht unterscheidet es sich vom oben genannten Turing-Maschinenmodell.

Siehe auch

Verweise

  1. ^ "Berechnungsmodelle" (PDF).

Weitere Lektüre

  • Fernández, Maribel (2009). Berechnungsmodelle: Eine Einführung in die Computerbarkeitstheorie. Bachelorthemen in der Informatik. Springer. ISBN 978-1-84882-433-1.
  • Savage, John E. (1998). Berechnungsmodelle: Erforschung der Berechnungsleistung. Addison-Wesley. ISBN 978-0201895391.