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:
- Endliche Staatsmaschinen
- Postmaschinen (Post -Turing -Maschinen und Tag -Maschinen).
- Pushdown -Automaten
- Maschinen registrieren
- Turing -Maschinen
- Entscheidungsbaummodell
Funktionsmodelle
Funktionsmodelle umfassen:
Gleichzeitige Modelle
Gleichzeitige Modelle umfassen:
- Schauspielermodell
- Mobilfunkautomat
- Interaktionsnetze
- Kahn -Prozessnetzwerke
- Logik -Tore und Digitale Schaltungen
- Petri Nets
- Synchroner Datenfluss
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
- Stapelmaschine (0-Operand-Maschine)
- Akkumulatormaschine (1-Operand-Maschine)
- Registrieren Sie Maschine (2,3, ... Operand Machine)
- Zufallszugriffsmaschine
- Abstrakte Maschine
- Zellprobenmodell
- Robertson -Webb -Query -Modell
- Chomsky -Hierarchie
- Vollständigkeit
Verweise
- ^ "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.