Maszyna RAM

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Maszyna RAM - w informatyce model abstrakcyjnej maszyny będący odmianą maszyny rejestrowej, bardzo podobnej do maszyny licznikowej, lecz z możliwością niebezpośredniego adresowania jej rejestrów. Model RAM wykorzystywany jest podczas analizy złożoności obliczeniowej algorytmów.

Maszyna RAM służy często w celu jako wprowadzenie do programowania oraz pomoc do nauki logicznego rozumowania. Ułatwia wyrobienie dobrych nawyków, np. inicjowania zmiennych przed użyciem. Zwykle stosuje się różnego rodzaju emulatory tejże maszyny, które przedstawiają działanie kodu wprowadzonego przez programistę; często instrukcje maszyny RAM upodabnia się do mnemoników asemblera, np. add, sub, mul, div, call oraz halt.

Budowa[edytuj | edytuj kod]

Maszyna RAM składa się ze wskaźnika rozkazów, czyli komórki zawierającej aktualnie wykonywaną instrukcję oraz pamięci będącej tablicą o nieskończonej przeliczalnej liczbie elementów. Maszyna RAM realizuje program wyrażony w skończonej liczbie instrukcji:

Instrukcja Znaczenie
Z(n) mem[n] := 0 Wyzeruj komórkę o numerze n. Zwiększ wskaźnik rozkazów o 1.
S(n) mem[n] := mem[n] + 1 Dodaj 1 do komórki o numerze n. Zwiększ wskaźnik rozkazów o 1.
T(m, n) mem[n] := mem[m] Skopiuj zawartość komórki o numerze m do komórki o numerze n. Zwiększ wskaźnik rozkazów o 1.
I(m, n, q) jeżeli mem[m] = mem[n] to skocz do q Jeśli zawartości komórek o numerach n i m są równe, ustaw wskaźnik rozkazów na q, w przeciwnym wypadku zwiększ go o 1.

Przykład[edytuj | edytuj kod]

Przykładowy program RAM

Nr Instrukcja
0 Z(3)
1 I(1,3,5)
2 I(2,3,6)
3 S(3)
4 I(0,0,1)
5 S(0)

Program oblicza funkcję f(x, y) = \begin{cases} 1, & x \leqslant y; \\ 0, & x > y. \end{cases}

Jako wejście przyjmuje dwie wartości x i y (umieszczane odpowiednio w komórkach o numerach 1 oraz 2). Pozostałe komórki pamięci są wyzerowane. Wynik działania programu (zwracana wartość) znajduje się w komórce o numerze 0.

Zobacz też[edytuj | edytuj kod]