PRIKLADY NA POCITANIE:
~~~~~~~~~~~~~~~~~~~~~~


Priklad  1:
-----------
   Ukazte, ze problem zastavenia pre standardne schemy je ciastocne
   rozhodnutelny.


Priklad  2:
-----------
   Zistite, ci je nasledujuca schema volna, resp. ci sa zastavi

   S: begin [y1,y2,y3]:=[x,f(x),f(f(x))]
         1: [y2]:=[f(y2)]
         2: if p(y2) then goto 4
         3: goto end
         4: [y3]:=[f(y3)]
         5: [y2]:=[f(y2)]
         6: if p(y2) then goto end
         7: [y1]:=[f(y1)]
         8: if p(y1) then goto 10
         9: goto 5
        10: [y3]:=[f(y3)]
        11: if p(y3) then goto end
        12: goto 1
      end [z]:=[a]

Priklad  3:
-----------
   Najdite nekonecnu mnozinu M standardnych schem taku, ze pre jej lubovolnu
   konecnu podmnozinu M' existuje interpretacia, pre ktoru vsetky schemy z M'
   zastavia, ale neexistuje interpretacia pre ktoru zastavia vsetky schemy
   z mnoziny M.

Priklad  4:
-----------
   Ukazte, ze problem volnosti Janovovych schem je rozhodnutelny.

Priklad  5:
-----------
   Nech S je lubovolna volna schema. Tvoria vystupne termy (po odstraneni
   zatvoriek) cez vsetky mozne Herbrandovske interpretacie regularnu
   mnozinu? Aku podmienku staci pridat, aby regularnu mnozinu tvorili?

Priklad  6:
-----------
   Keby sme pri vypocte rekurzivneho programu prepisovali term zodpovedajuci
   najpravejsiemu najvnutornejsiemu vyskytu funkcnej premennej mohli by sme
   dostat iny vysledok ako pri normalnom vyhodnocovani?

Priklad  7:
-----------
   Uvazujme nasledovnu rekurzivnu schemu:

     begin
        F(y) = if p(y) then f(y) else h(y,F(g(y)))
     end [z]:=[F(a)]

   Najdite ekvivalentnu standardnu schemu pouzivajucu iba tri pracovne
   premenne.

Priklad  8:
-----------
   Uvazujme triedu standardnych schem, ktore zastavia pre kazdu interpretaciu.
   Su v triede tychto schem problemy izomorfizmu a ekvivalencie rozhodnutelne?



PREMIOVE ULOHY:
~~~~~~~~~~~~~~~

Priklad  1: (3 body)
-----------
Dokazte, ze izomorfizmus volnych schem je rozhodnutelny. (Uvazujeme
definiciu 2, teda dve kompatibilne schemy su izomorfne akk pre kazdu
interpretaciu a ohodnotenie vstupnych premennych maju rovnaku postupnost
vykonanych priradovac¡ch prikazov)

Priklad  2: (3 body)
-----------
Su dosiahnutelne schemy efektivne prelozitelne do priechodnych?
Dokazte, alebo vyvratte.

Priklad  3: (3 body)
-----------
Dokazte, ze Janovove schemy su efektivne prelozitelne do volnych schem.