Zamislimo računalo čija memorija je beskonačna traka podijeljena na ćelije (vidi sliku). Ovakvo računalo ćemo zvati RAM-stroj, a ćelije trake registri. U registrima su upisani prirodni brojevi (uključujući i nulu). RAM-stroj još ima i programski brojač, a to je broj čije značenje će biti jasno uskoro.
![Attachment RAM-stroj.png](/media/attachment/1/00172_e2cz24zrjfcqgshmxz4l/RAM-stroj.png)
Program za RAM-stroj sastoji se od niza instrukcija tipa
,
i
. Instrukcija tipa
povećava sadržaj registra na koji se odnosi za
. Instrukcija tipa
smanjuje sadržaj registra na koji se odnosi za
, ako on već nije nula; u suprotnom se sadržaj registra ne mijenja, nego se samo programski brojač postavlja na zadanu vrijednost. Instrukcija tipa
mijenja programski brojač na zadanu vrijednost. Dajemo primjer jednostavnog RAM-programa. ![\begin{bmatrix}
1. & \operatorname{DEC}\ \mathcal{R}_1, 4 \\
2. & \operatorname{INC}\ \mathcal{R}_0 \\
3. & \operatorname{GOTO}\ 1 \\
4. & \operatorname{INC}\ \mathcal{R}_0
\end{bmatrix}](/media/m/6/d/3/6d3e404e9b7720f94ab3a639e4e4d53c.png)
Programi se na RAM-stroju izvršavaju na sljedeći način. U ćelijama RAM-stroja su na početku svugdje nule, osim u registru
, u kojem je zapisan ulazni podatak. Programski brojač je na početku jednak
i izvršavanje programa kreće od prve instrukcije. Nakon izvršetka svake instrukcije, programski brojač se uvećava za jedan, osim u slučaju kada ga sama instrukcija promijeni. Sljedeća se izvršava instrukcija s rednim brojem jednakim trenutnom sadržaju programskog brojača. Ako je sadržaj programskog brojača prevelik, dakle veći od broja instrukcija programa, tada program završava. Probajte u glavi ili na papiru izvršiti prethodni program s ulaznim podacima
.
Primjećujemo da se na kraju svakog izvršavanja ovog programa u registru
uvijek nalazi broj
. Registar
stoga zovemo izlazni te kažemo da ovaj RAM-program izračunava funkciju
.
Vaš prvi zadatak je napisati RAM-program koji izračunava konstantnu funkciju
.
Kao rješenje upišite šifru koju će generirati evaluator sa stranice https://www.skoljka.org/marinada20/ram/evaluator/. Program se unosi u kompaktnom formatu, točnije kao niz brojeva koji kodiraju vaš RAM-program na sljedeći način.
-ti član niza jednak je: ![\begin{itemize}
\item $2^{k+1}$, ako je $n$-ta instrukcija $\operatorname{INC}$ $\mathcal{R}_k$;
\item $2^{k+1} \cdot 3^{\ell}$, ako je $n$-ta instrukcija $\operatorname{DEC}$ $\mathcal{R}_k, \ell$;
\item $3^\ell$, ako je $n$-ta instrukcija $\operatorname{GOTO}$ $\ell$.
\end{itemize}](/media/m/6/c/d/6cda8ee6089a2c33efcabb0207195b33.png)
Primjerice,
RAM-programa navedenog u primjeru je:
.
Zamislimo računalo čija memorija je beskonačna traka podijeljena na ćelije (vidi sliku).
Ovakvo računalo ćemo zvati \emph{RAM-stroj}, a ćelije trake \emph{registri}.
U registrima su upisani prirodni brojevi (uključujući i nulu).
RAM-stroj još ima i \emph{programski brojač}, a to je broj čije značenje će biti jasno uskoro.
\includegraphics{RAM-stroj.png}
Program za RAM-stroj sastoji se od niza instrukcija tipa $\operatorname{INC}$, $\operatorname{DEC}$ i $\operatorname{GOTO}$.
Instrukcija tipa $\operatorname{INC}$ \textbf{povećava} sadržaj registra na koji se odnosi za $1$.
Instrukcija tipa $\operatorname{DEC}$ \textbf{smanjuje} sadržaj registra na koji se odnosi za $1$, ako on već nije nula; u suprotnom se sadržaj registra ne mijenja, nego se samo programski brojač postavlja na zadanu vrijednost.
Instrukcija tipa $\operatorname{GOTO}$ mijenja programski brojač na zadanu vrijednost.
Dajemo primjer jednostavnog RAM-programa.
\[
\begin{bmatrix}
1. & \operatorname{DEC}\ \mathcal{R}_1, 4 \\
2. & \operatorname{INC}\ \mathcal{R}_0 \\
3. & \operatorname{GOTO}\ 1 \\
4. & \operatorname{INC}\ \mathcal{R}_0
\end{bmatrix}
\]
Programi se na RAM-stroju izvršavaju na sljedeći način.
U ćelijama RAM-stroja su na početku svugdje nule, osim u registru $\mathcal{R}_1$, u kojem je zapisan ulazni podatak.
Programski brojač je na početku jednak $1$ i izvršavanje programa kreće od prve instrukcije.
Nakon izvršetka svake instrukcije, programski brojač se uvećava za jedan, osim u slučaju kada ga sama instrukcija promijeni.
Sljedeća se izvršava instrukcija s rednim brojem jednakim trenutnom sadržaju programskog brojača.
Ako je sadržaj programskog brojača prevelik, dakle veći od broja instrukcija programa, tada program završava.
Probajte u glavi ili na papiru izvršiti prethodni program s ulaznim podacima $x = 0, 1, 2, 3$.
Primjećujemo da se na kraju svakog izvršavanja ovog programa u registru $\mathcal{R}_0$ uvijek nalazi broj $x+1$.
Registar $\mathcal{R}_0$ stoga zovemo \emph{izlazni} te kažemo da ovaj RAM-program \emph{izračunava} funkciju $f(x) = x + 1$.
Vaš prvi zadatak je napisati RAM-program koji izračunava konstantnu funkciju $f(x) = 3$.
Kao rješenje upišite šifru koju će generirati evaluator sa stranice \href{https://www.skoljka.org/marinada20/ram/evaluator/}{https://www.skoljka.org/marinada20/ram/evaluator/}.
Program se unosi u kompaktnom formatu, točnije kao niz brojeva koji \emph{kodiraju} vaš RAM-program na sljedeći način.
$n$-ti član niza jednak je:
\begin{itemize}
\item $2^{k+1}$, ako je $n$-ta instrukcija $\operatorname{INC}$ $\mathcal{R}_k$;
\item $2^{k+1} \cdot 3^{\ell}$, ako je $n$-ta instrukcija $\operatorname{DEC}$ $\mathcal{R}_k, \ell$;
\item $3^\ell$, ako je $n$-ta instrukcija $\operatorname{GOTO}$ $\ell$.
\end{itemize}
Primjerice, $\text{k}\^o\text{d}$ RAM-programa navedenog u primjeru je: $324, 2, 3, 2$.