Vrijeme: 15:41

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.