Tietojenkäsittelyopin laboratorio Tentti 23.1.96

Saikkonen, Syriänen, Tiusanen 1

Merkitse jokaisen vastauspaperisi vasempaan yläreunaan selvästi allekkain:

* Tik-76.101 Ohjelmoinnin pitkä peruskurssi

* tentti 23.01.1996

* sukunimi, etunimet

* koulutusohjelma, opintokirjan numero

Käytä mahdollisimman selvää käsialaa, jätä riittävät marginaalit sivun laitoihin ja merkitse tehtävännumeronäkyviin.

Merkitse jokaiseen paperiin paperien kokonaismäärä.

Tentissä saa käyttää apuna kurssikirjaa (Abeison & Sussman), mutta ei muuta materiaalia (esim. opetusmonisteita).

Tentin korjaamisen jouduttamiseksi vastaa eri tehtäviin eri papereilla alla olevien ohjeiden mukaan.

Paperille l:

1. Proseduuri (sum f n k) laskee summan (Si: n < i < n+k: f(i)) eli siis summan funktion f arvoista argumentin vaihdellessa välillä (n.. n+k):

f(n)+f(n+l)+ ... f(n+k).

a) Kirjoita proseduuri sum.

b) Kun f(n) on funktio, joka laskee fibonaccin sarjan n:nen luvun, voidaan e.m.

summafunktio toteuttaa tehokkaammin yhdistämällä funktiot yhdeksi proseduuriksi (sumfib n k). Kirjoita proseduuri sumfib.

c) Arvioi a) ja b) kohtien aika- ja tilavaatimuksia, kun molemmissa käytetään samaa algoritmia fib(n):n laskemiseen,

Paperille 2:

2. Kirjassa esitettiin (aluksi) joukkoja järjestämättöminä listoina, joissa ei esiintynyt duplikaatteja, ts. sama alkio saattoi esiintyä listassa vain kerran. Oletetaan nyt, että duplikaatit sallitaan.Esimerkiksi joukkoa (1,2,3) voisi edustaa vaikkapa lista (2 3 2 1 3 2 2). Määrittele proseduurit element-of-set?, adjoin-set, union-set ja intersection-set, jotka käyttävät tätä joukkojen esitystapaa.

Miten näiden proseduurien tehokkuus suhtautuu vastaavan proseduurin tehoon tapauksessa, jossa dupiikaatteja ei sallita? Onko olemassa sovelluksia, joissa lama joukkojen esitys olisi parempi kuin esitys, jossa duplikaatteja ei sallita?

(element-of-set? x set) kertoo onko alkio x joukon set jäsen, (adjoin-set x set) palauttaa joukon, joka saadaan liittämällä alkio x joukkoon set, (union-set setl set2) ja (intersection-set setl set2) palauttavatjoukkojenseti ja se(2 yhdisteenja leikkauksen.

3 . (a) Toteuta konstruktori (rakentajafunktio) make-polar viestinvälitysmekanismin (message-passing) avulla. Ohjelmasi tulee muistuttamaan kirjan sivulla 141 esitettyä proseduuria make-rectangular. (4p)

(b) Anna esimerkki make-polarin käytöstä: näytä, miten voit ensin muodostaa sen avulla kompleksiluvun ja ottaa sitten näin muodostetusta luvusta reaaliosan. (2p.)

Paperille 3:

4. Tarkastellaan proseduurimäärittelyä

(define (append l1 l2)

(cond ((null? l1) l2)

(else (cons (car l1) (append (cdr l1) l1)))))

Kuinka monta kertaa metasirkulaarinen eval suoritetaan, kun oppikirjan osassa 4.1 esitetyllä metasirkulaarisella evaluaattorilla evaluoidaan lauseke

(append '(a) ())

Perustele! (6p)

5. Määrittele rekisterikone, joka toteuttaa seuraavan ohjelman mukaisen laskennan. Riittää, jos annat vastauksesi käyttäen (define-machine ) tai (build-model ) -muotoja; käytä luvun 5 nimiä rekistereille, mikäli voit selkeyden kärsimättä. (6p)

(define (b n k)

(cond ((= k 0) 1)

((> n k) 0)

(else (+ (b n (- k 1))

(b (- n 1) (- k 1))))))