##  [Random-Access-Maschine](/de/node/58905) 

 Definition

Ein abstraktes sequentielles Maschinenmodell zur Analyse von Algorithmen, das einen Prozessor beschreibt, der auf einem unbeschränkten Feld von Speicherzellen arbeitet, wobei jede Zelle per Adresse in Einheitszeit zugänglich ist, und über eine Standardmenge primitiver Operationen verfügt; verwendet zur Untersuchung von Zeit- und Platzkomplexität unter der Annahme von Einheitkosten für Arithmetik und konstantem Speicherzugriff.

 

 

 

 

 

 





## Prinzip

Prinzip

Algorithmentritte als Operationen eines Zentralprozessors mit konstantem adressiertem Speicherzugriff und festem Befehlssatz zu behandeln und damit algorithmische Kosten von physischen Speicherlayoutfragen zu trennen.

 

 

 

 

 





## Demonstration

Demonstration

Analysiere einen Ganzzahl-Sortieralgorithmus, indem die Anzahl primitiver Operationen (Vergleiche, Zuweisungen, Lade-/Speicheroperationen) auf einer RAM mit Direktadressierung gezählt wird; drücke die Laufzeit als Funktion der Eingabegröße aus unter der Annahme, dass jeder Speicherzugriff eine Zeiteinheit kostet.

 

 

 

 

## Fehlanwendung

Fehlanwendung

Annahme von Einheitszeitzugriff für beliebig große in einer Zelle gespeicherte Ganzzahlen ohne Berücksichtigung ihrer Bitlänge oder Übertragung der RAM-Kosten direkt auf Modelle mit hierarchischen Caches und nicht-uniformen Zugriffszeiten.

 

 

 

 

 





## Konsequenz

Konsequenz

Ermöglicht ein einfaches, analytisch handhabbares Modell, das maschinenunabhängige asymptotische Zeit- und Platzgrenzen für sequentielle Algorithmen liefert und Vergleiche zwischen Algorithmen erleichtert.

 

 

 

 

## Umkehrung

Umkehrung

Ein Modell, das Speicher strikt sequentiell behandelt (z. B. ein Turing-Band), wobei der Zugriff auf die i-te Zelle Zeit proportional zu i erfordern kann und damit die Zufallszugriffsannahme umkehrt.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Modelliert keine parallelen oder verteilten Rechnungen, Cache-Hierarchien oder hardwarenahe Effekte; Konventionen variieren, ob Arithmetik auf unbeschränkten Ganzzahlen Einheitskosten hat; schließt stochastische oder quantenmechanische Ressourcen aus.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Im Wettbewerb mit dem Turingmaschinenmodell (feine Kopfbewegungen und Band) und word-RAM-Varianten (begrenzte Wortgröße), bei denen Kostenbegriffe und Speichereinheit abweichen.

 

 

 

 

 





## Synthese

Synthese

Ein vereinfachtes Modell sequenziellen Rechnens, das konstanten adressierten Speicherzugriff und primitive Operationen annimmt, um algorithmische Kosten zu fokussieren und Hardwaredetails zu abstrahieren — geeignet für asymptotische Analysen, wenn Einheitskosten akzeptabel sind.