Tietojenkäsittelyopin laboratorio

Mäntylä, Saikkonen, Syrjänen

Tik-76. 1 01 Ohjelmoinnin pitkä peruskurssi

Tentti 26.09.1995

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

* Tik-76. 1 01 Ohjelmoinnin pitkä peruskurssi

* tentti 26.09.1995

* sukunimi, etunimet

* koulutusohjelma, opintokirjan numero

Käytä mahdollisimman selvää käsialaa, jätä riittävät marginaalit sivun laitoihin ja merkitse tehtävän numero näkyviin. Mikäli vastaat useammalla paperilla, merkitse jokaiseen niistä paperien kokonaismäärä.

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

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

Paperille l:

1. Generoidaan kokonaislukujonoa a0,al,a2,... funktion f avulla siten, että a0 = f(0) ja a(i+ 1) = f(ai), Sanotaan, että funktio f sisältää r:n mittaisen syklin, jos on olemassa sellaiset kokonaisluvut q>0 ja r > 0 se. aq = a(q+r).

Tee proseduuri, joka etsii parametrina saatavan syklisen funktion f lyhimmän syklin pituuden käyttäen vain vakiomäärän muistia.

Vihje: Mieti ensin, miten syklinen funktio ylipäät käyttäytyy. Jonon alku ei välttämättä kuulu sykliin. Etsi ensin kohta, joka on syklissä ja sitten vasta lyhin sykli.

Paperille 2:

2. Määrittele proseduuri (predikaatti) present?, joka tutkii esiintyykö annettu atomi jossain annetussa S-lausekkeessa. Se poikkeaa memq:sta, joka tutkii vain listarakenteen ylimmän tason. Esim. (present? 'x '((y x) (z x) (y z))) palauttaisi totuusarvon true.

3 . On määritelty seuraavat proseduurit

(define (cons x y)

(lambda (m) (m x y>>)

(define (car z)

(z (Iwnbda (p q) p>>)

osoita, että kaikille objekteille x ja y pätee, että (car (cons x y)) palauttaa arvon x. Käytä tarkasteluissa korvausmallin (substitution model) mukaista perustelua. Määrittele vastaava cdr.

Paperille 3:

4. (a) Kirjoita proseduuri, joka palauttaa streamin, joka koostuu kaikista kahdesta kokonaisluvusta x, y koostuvista pareista (listoista) (x y) siten, että 0 < x < XMAX ja 0 < y < YMAX. Kokonaisluvut XMAX ja YMAX toimivat proseduurin parametreina. Käytä mahdollisimman korkean tason stream-operaatioita. (3p)

(b) Kirjoita suodatinproseduuri (filter), joka päästää lävitseen kohdan (a) streamista vain ne parit, joille pätee yhtälö

(x - x0)2 + (y - y0)^2 <= r^2

missä x0, y0, r ovat parametreja. Käytä mahdollisimman korkean tason streamoperaatioita. (3p)

5. Tarkastellaan seuraavia kyselyjärjestelmän sääntöjä:

(rule (append-to-form 0 ?y ?y))

(rule (append-to-form (?u . ?v) ?y (?u . ?z))

(append-to-fonn ?v ?y ?z))

Kuvaa kyselyjädestelmän toiminta evaluoitaessa kyselyä

(append-to-form (a b) ?x (a b c d))

Esitä vastauksessasi kaikki tarvittavat unifikaatiot ja niissä syntyvät sidonnat.

(Vihje: evaluoinnissa tarvitaan kolme unifikaatiota.)