Podúloha a) (2 body) OR – stroj

Keď sa snažíme pracovať s logickými hradlami alebo funkciami, často sa nám oplatí napísať si celú tabuľku hodnôt pre hľadané hradlo a nájsť podobnosti s hradlami, ktoré poznáme. Vieme, že hradlo OR má vrátiť nulu iba v tom prípade, ak sú obe vstupné hodnoty rovné 0. Inak vráti hodnotu 1. To sa trochu podobá na hradlo AND, ktoré vráti 1 iba v jedinom prípade – keď sa obe vstupné hodnoty rovnajú 1.

Ak znegujeme výsledok AND, podobnosť s hradlom OR je ešte výraznejšia, pretože negovaný AND (nazývaný tiež NAND) vracia 0 iba v jedinom prípade, presne tak, ako hradlo OR. Akurát tie prípady sú odlišné. OR na to potrebuje dve nuly, ale NAND dve jednotky. Ako teda zaručíme, aby ak naše hradlo dostane dve 0, náš znegovaný AND dostal dve 1? Jednoducho obe vstupné hodnoty znegujeme.

Celé hradlo preto vyzerá nasledovne: znegované vstupné hodnoty vložíme do hradla AND, ktorého výsledok nakoniec tiež znegujeme.

`Páska A:            0011100100100010
Páska B:            1010010110101101
C=!A                1100011011011101 
D=!B                0101101001010010
E=C&D               0100001001010000
F=!E                1011110110101111
Vytlač F:           1011110110101111`

Alebo v skratke F=!((!A) & (!B)).

Podúloha b) (2 body) XOR – stroj

Jednotka bude na tých pozíciách, kde sa čísla na páskach líšili. A to bude tam, kde bude buď na páske A $1$ a zároveň na páske B nebude $1$, alebo keď bude na páske B $1$ a zároveň na páske A $1$ nebude.

Všimnime si zvýraznené slová v tomto popise. Tie predsa priamo zodpovedajú strojom ktoré máme – “a zároveň” je stroj AND a “alebo” je stroj OR. A ak chceme zistiť, na ktorých pozíciách nie je $1$, zistíme to pomocou stroja NOT.

Správne sformulované zadanie nám teda presne popisuje, ako sa dostaneme k výsledku a túto formuláciu stačí prepísať do kódu:

`Páska A:            0011100100100010
Páska B:            1010010110101101
C=!A                1100011011011101 (kde v A nie je 1) 
D=!B                0101101001010010 (kde v B nie je 1)
E=A&D               0001100000000010 (v A je 1 a v B nie je 1)
F=B&C               1000010010001101 (v B je 1 a v A nie je 1)
G=E|F               1001110010001111
Vytlač G:           1001110010001111`

Alebo v skratke G=(A&!B) OR (!A&B)

Podúloha c) (3 body) SEL – stroj

Ak chceme vynulovať niektoré políčka na páske, najlepšie je spraviť AND s páskou, ktorá má nuly, práve na tých miestach, ktoré chceme vynulovať. Tento stroj chce vynulovať všetky pozície, okrem jednej konkrétnej ($k+1$ z pravej strany). Na tejto pozícii teda chceme mať 1, ktorá zaručí, že po operácii AND ostane na tejto pozícii pôvodná hodnota. No a pásku, ktorá obsahuje 1 iba na $k+1$ pozícii vyrobíme najľahšie pomocou stroja LSHIFT.

Výsledný program je teda C = (1<<k)&A.

Pre $k=3$ to teda môže vyzerať takto:

`k=3
Páska A:            1110010111100101
B=1<<k              0000000000001000
C=B&A               0000000000000000 
Vytlač C:           0000000000000000`

Prípadne pre $k=5$:

`k=5
Páska A:            1110010111100101
B=1<<k              0000000000100000
C=B&A               0000000000100000
Vytlač C:           0000000000100000`

Podúloha d) (3 body) RAO – stroj

Pri riešení tejto úlohy si musíme uvedomiť, akú podmienku vlastne kontrolujeme. Jednotka bude na tých pozíciach, kde už bola predtým, a zároveň bola 1 buď napravo alebo naľavo od danej pozície. Uvedomme si, že ak posunieme celú pásku o 1 doprava a túto pásku spojíme strojom AND s pôvodnou páskou A tak 1 ostanú na tých pozíciách, kde boli 1 pôvodne a zároveň mali 1 napravo od seba.

Rovnakú myšlienku vieme samozrejme použiť aj na smer vľavo. Výsledné riešenie dostaneme spojením týchto dvoch možností strojom OR.

`Páska A:            1110010111100101
B=A<<1              1100101111001010 (posunutie doľava)
C=A>>1              0111001011110010 (posunutie doprava)
D=A&B               1100000111000000 (pozície s 1, ktoré majú 1 aj napravo od seba)
E=A&C               0110000011100000 (pozície s 1, ktoré majú 1 aj naľavo od seba)
F=D|E               1110000111100000
Vytlač E:           1110000111100000`

Alebo v skratke: E=((A<<1)&A) | ((A>>1)&A)

Podúloha e) (3 body) RM – stroj

Budeme postupovať podobne ako v predchádzajúcej úlohe. Najprv si uvedomíme, že jednotka je na okraji práve vtedy, keď nemá jednotky na oboch stranách. Rovnako ako v predchádzajúcej úlohe to, či je jednotka napravo alebo naľavo, zistíme posunutím pásky o jednu cifru doprava alebo doľava.

Ak tieto dva posuny dáme dokopy pomocou AND, dostaneme všetky pozície 1, ktoré majú 1 na oboch stranách. My sa však práve týchto jednotiek chceme zbaviť a preto túto pásku znegujeme. Následne ju spojíme s pôvodnou páskou A, čím dostaneme výsledok.

`Páska A:            0110010111101110
B=A<<1              1100101111011100
C=A>>1              0011001011110111
D=B&C               0000001011010100 (1 je na pozíciách ktoré mali z oboch strán 1)
E=!D                1111110100101011 
F=A&E               0110010100101010 
Vytlač F:           0110010100101010`

Alebo skrátene F=(!((A<<1) & (A>>1))) & A

A ako toto súvisí s počítačmi?

V počítači sa čísla ukladajú v binárnej sústave ako postupnosť núl a jednotiek. Tento fakt už, ako programátori takmer nevnímame, pretože počítač nám ich vypisuje v desiatkovej sústave. Napriek tomu však s číslami vieme pracovať aj v ich binárnej reprezentácii, a to pomocou funkcií podobných tým v tejto úlohe.

Pomerne bežne sa stáva, že znalosť týchto funkcií a toho, ako fungujú vám pomôže pri riešení nejakého problému. Jednou z veľa výhod napríklad je, že tieto binárne operácie sú naozaj rýchle¹.

Najčastejšie používané sú nasledovné funkcie udané aj s bežným označeným:

`& - AND
| - OR
^ - XOR
~ - NOT
<< - posuvanie dolava
>> - posuvanie doprava`

Keby sme si chceli posledný príklad prepísať do Pythonu vyzeralo by to nasledovne:

A= int ('0110010111101110', 2) #nacitaj cislo v dvojkovej sustave
B=A<<1
C=A>>1
D=B & C
E=~D
F=A&E
print (bin(F)) #vypis v dvojkovej sustave

Program vypíše: 0b110010100101010

0b označuje, že číslo vypisujeme v binárnej sústave. Oproti našej páske tam chýba 0 na začiatku. Tá sa však nevypisuje z rovnakých dôvodov, z akých v desiatkovej nepíšeme 0572.

Keby sme si chceli posledný príklad prepísať do C++, vyzeralo by to nasledovne:

#include <iostream>
#include <string>
#include <cstdlib>
#include <bitset>
using namespace std;
int main()
{
    string s = "0110010111101110"; 
    int A = (int) strtol(s.c_str(), NULL, 2);  //zmena retazca v dvojkovej sustave na cislo
    int B = A<<1;
    int C = A>>1;
    int D = B&C;
    int E = ~D;
    int F = A&E;
    cout<<bitset<16>(F)<<endl; //vypis ako cislo v dvojkovej sustave, tak aby malo 16 cifier
}