1. Käännä seuraava Pascal-kielinen ohjelma MIX-konekoodiksi (käskytaulukko luentomonisteen s. 69):

program collatz(input);

var x : integer;

begin

end.

2. Seuraava Prolog-ohjelma määrittelee joidenkin taruolentojen sukusuhteita (father(X, Y) º "X:n isä on Y" jne.):

father(elrond, earendil).

father(elros, earendil).

mother(elrond, elwing).

mother(elros, elwing).

mother(earendil, idril).

father(idril, turgon).

father(turgon, fingolfin).

father(gilgalad, fingon).

father(fingon, fingolfin).

parent(X,Y) :- father(X,Y).

parent(X,Y) :- mother(X,Y).

ancestor(X,Y) :- parent(X,Y).

ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

Täydennä ohjelmaa predikaateilla sibling(X,Y) º "X ja Y ovat sisaruksia" ja cousin(X,Y) º "X ja Y ovat serkuksia". Tarvitset aiempien tietojen lisäksi alkeispredikaattia (X \== Y) º "X ja Y eivät viittaa samaan olioon". (Voit kokeilla Prolog-ohjelmointia käytännössä yliopiston atk-keskuksen koneille (esim. "tukki") asennetulla C-Prolog -tulkilla. Tulkki käynnistyy komennolla "prolog", ja vastaamalla tulkin ensimmäiseen "?-" -kehotteeseen komennolla "[user]." (huomaa piste) pääsee kirjoittamaan omaa ohjelmaa. Ylläkuvattujen rivien jälkeen saa esim. kyselyllä "?- ancestor(elrond,X)" selville taruhenkilö Elrondin esivanhemmat. Kun kone on selvittänyt ja tulostanut yhden esivanhemman (esim. "X = earendil"), saadaan seuraava kirjoittamalla tulosrivin loppuun puolipiste (";").)

 3. Todista, että seuraava algoritmi laskee syötteenä annetun ei-negatiivisen kokonaisluvun n neliöjuuren ylöspäin pyöristäen, so. asettaa m ¬ éÖnù.

input n

if n = 0 then output 0

else

Ohje: Tarkastele erikseen tapaukset n = 0 ja n > 0. Jälkimmäisessä tapauksessa valitse silmukkainvariantiksi ehto n > (m-1)². Totea, että invariantti on voimassa ennen silmukan ensimmäistä suorituskertaa, ja että siitä silmukan viimeisen suorituskerran jälkeen seuraa ominaisuus m = éÖnù. Tarkasta myös, että silmukan suoritus aina päättyy.