Marinada '20 - Školjka

Vrijeme: 12:44

RAM-programiranje #1

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$

Program za RAM-stroj sastoji se od niza instrukcija tipa $\operatorname{INC}$ , $\operatorname{DEC}$ i $\operatorname{GOTO}$ . Instrukcija tipa $\operatorname{INC}$ povećava sadržaj registra na koji se odnosi za $1$ . Instrukcija tipa $\operatorname{DEC}$ 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 izlazni te kažemo da ovaj RAM-program 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 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. $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$ .

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$.