Tietojenkäsittelytieteen laitos

Luento.

Luento.

Luento. Luentokalvot 1-50 ovat nyt saatavilla PostScript (PS) ja Portable Document Format (PDF) -muodoissa. Myös ensimmäisten laskuharjoitusten tehtävät ovat nyt saatavilla PS ja PDF -muodoissa.

(GhostView on ilmainen PS- ja PDF-tiedostojen katselu- ja tulostusohjelma.)

Luento. Lambda-termien normalisoijan beta voit kopioida itsellesi lähdekielisenä tiedostona "beta.scm". Saat ladattua tämän tiedoston drscheme-istuntoosi komennolla (load "beta.scm").

Tiedosto antaa käyttöösi funktion (beta 'termi) joka ottaa syötteenään termin ja palauttaa sen normaalimuodon.

Tämä termi on

muuttuja

joka esitetään symbolina (ei kuitenkaan symbolina ^).

sovellus

joka esitetään (termi1 termi2).

Sisäkkäiset sovellukset ((termi1 termi2) termi3) voidaan lyhentää (termi1 termi2 termi3).

abstraktio

joka esitetään (^ muuttuja termi).

Sisäkkäiset abstraktiot (^ muuttuja1 (^ muuttuja2 termi)) voidaan lyhentää (^ muuttuja1 muuttuja2 termi).

vakio

joka esitetään numerona tai symbolina. Annettu symboli tulkitaan vakioksi jos sitä ei ole abstrahoitu. Vakiosymboli ei myöskään saa olla muotoa xnumero koska tällaiset symbolit on varattu muuttujien tulostusasuksi.

Harjoitusryhmä.

Luento. Luentokalvot 51-84 ovat nyt saatavilla PS- ja PDF-muodoissa. Myös toisten laskuharjoitusten tehtävät ovat nyt saatavilla PS- ja PDF-muodoissa.

Harjoitusryhmä.

Luento.

Harjoitusryhmä.

Luento. Luentokalvot 85-108 ovat nyt saatavilla PS- ja PDF-muodoissa. Myös kolmansien laskuharjoitusten tehtävät ovat nyt saatavilla PS- ja PDF-muodoissa. HUOM! Tehtävän 3.2 tulosesimerkissä on lyöntivirhe: arvon pitäisi olla (1 1 1 2 3 4 5).

Harjoitusryhmä.

Luento.

Harjoitusryhmä.

Luento. Luentokalvot 109-128 ovat nyt saatavilla PS- ja PDF-muodoissa. Myös neljänsien laskuharjoitusten tehtävät ovat nyt saatavilla PS- ja PDF-muodoissa.

Harjoitusryhmä. Näissä harjoituksissa ilmeni DrScheme-toteutuksesta seuraava piirre:

Welcome to DrScheme, version 202.
Language: Standard (R5RS).
> '(1 . 2 . 3)
(2 1 3)
> 

Lauri Alanko kertoi jälkeenpäin, että kyseessä on tämän toteutuksen ikioma laajennus, josta on kerrottu PLT MzScheme: Language Manual -käsikirjan luvussa 14.3. (It wasn't a bug, it was a feature.)

Luento. Luentokalvot 129-148 ovat nyt saatavilla PS- ja PDF-muodoissa. Myös viidensien laskuharjoitusten tehtävät ovat nyt saatavilla PS- ja PDF-muodoissa. Osassa näistä tehtävistä tarvitset luennolla olleen samastusalgoritmin Scheme-lähdekoodia, jonka saat seuraavista kolmesta tiedostosta: unify.scm, term.scm ja binding.scm. Ne ovat osa Scheme-kielistä sääntötulkkia.

Harjoitusryhmä.

Harjoitusryhmä.

Luento.

Harjoitusryhmä.

Luento. Luentokalvot 149-173 ovat nyt saatavilla PS- ja PDF-muodoissa. Myös kuudensien laskuharjoitusten tehtävät ovat nyt saatavilla PS- ja PDF-muodoissa. Joissakin tehtävissä tarvitset luennoilla ollutta kuningatar Victorian jälkeläisten sukupuuta Prolog-kielellä, joka saat täältä. Lisäksi voit noutaa Scheme-kielisen sääntötulkin loput kaksi lähdekooditiedostoa rule.scm ja shell.scm.

Harjoitusryhmä.

Luento. Voit noutaa täältä luennoilla läpikäydyt Prolog-esimerkit lisäyksestä 2-3-hakupuuhun ja totuusarvojen etsijästä.
HUOM! Hakupuuesimerkissä oli ohjelmointivirhe! Se on nyt korjattu; hae tiedosto uudelleen. Vastaava korjattu kalvo 175 on myös saatavilla PS- ja PDF-muodoissa.

Harjoitusryhmä.

Luento. Luentokalvot 174-201 ovat nyt saatavilla PS- ja PDF-muodoissa. Myös seitsemänsien laskuharjoitusten tehtävät ovat nyt saatavilla PS- ja PDF-muodoissa.

Harjoitusryhmä.

Luento.

Harjoitusryhmä.

Luento. Viimeiset luentokalvot 202-235 ovat nyt saatavilla PS- ja PDF-muodoissa. Myös kahdeksansien eli viimeisten laskuharjoitusten tehtävät ovat nyt saatavilla PS- ja PDF-muodoissa.

Harjoitusryhmä.

Harjoitusryhmä.

Harjoitusryhmä. HUOM! Tämä ryhmä kokoontuukin siis tuntia aiemmin kuin normaalisti. Jos pääset paikalle vasta klo 14, niin saat silti tekemistäsi tehtävistä lisäpisteet.

Kurssikoe. Koealue käsittää luennoilla ja laskuharjoituksissa esillä olleet asiat. Huomaa ennakkotietoja myöhäisempi kellonaika!

Kaikki luentokalvot 1-235 ovat nyt saatavilla pienennettynä PS- ja normaalikokoisena PDF-muodossa.

Tulokset ovat nähtävillä cum laude -kurssikokeiden ilmoitustaululla salissa A412.

Arvosteluun voi tutustua 20.12.2002 klo 10-11 salissa C475.

Lauri Alanko korjasi tehtävät 2 ja 4. Niiden malliratkaisut ovat verkossa.

Luennoija korjasi tehtävät 1 ja 3. Niiden malliratkaisut ovat alla:

; Lista 1 on listan 2 alilista jos lista 2 sisaltaa listan 1
; alkiot samassa jarjestyksessa muttei valttamatta perakkain.
; Palautetaan #f jos argumentti ei ole aito lista.
(define (subseq? list-1 list-2)
  (or (and (null? list-1)
           (list? list-2))
      (and (pair? list-1)
           (pair? list-2)
           (subseq? (if (equal? (car list-1)
                                     (car list-2))
                             (cdr list-1)
                             list-1)
                         (cdr list-2)))))

(define (subseqs list-2)
  (cond ((null? list-2)
         '(()))
        ((pair? list-2)
         (let ((tail-subs (subseqs (cdr list-2))))
           (let filter ((head-subs (map (lambda (tail-sub)
                                          (cons (car list-2)
                                                tail-sub))
                                        tail-subs))
                        (uniques tail-subs))
             (if (null? head-subs)
                 uniques
                 (filter (cdr head-subs)
                         (if (member (car head-subs)
                                     tail-subs)
                             uniques
                             (cons (car head-subs)
                                   uniques)))))))
        (else
         ())))

; Notaation yksinkertaistamiseksi laiskojen listojen perusperaatiot:
(define stream-null
  '())
(define-syntax stream-cons
  (syntax-rules ()
    ((_ a s) (cons a (delay s)))))
(define stream-car car)
(define (stream-cdr s)
  (force (cdr s)))
(define (stream-null? s)
  (eq? s stream-null))

; Muita operaatioita laiskoille listoille:
(define (stream-map f s)
  (let mapper ((t s))
    (stream-cons (f (stream-car t))
                 (mapper (stream-cdr t)))))

(define (stream-merge ord stream-1 stream-2)
  (let merger ((s1 stream-1)
               (s2 stream-2))
    (if (ord (stream-car s1)
             (stream-car s2))
        (stream-cons (stream-car s1)
                     (merger (stream-cdr s1)
                             s2))
        (stream-cons (stream-car s2)
                     (merger s1
                             (stream-cdr s2))))))

(define (stream-dropwhile p s)
  (let drop ((t s))
    (if (p (stream-car t))
        (drop (stream-cdr t))
        t)))

; Luonnollinen luku n on Ramanujan joss on luonnolliset luvut
; p<q<=r<s siten, etta p^3+s^3=n=q^3+r^3.
; Tuotetaan ne laiskana listana.
; Idea:
; 1. Lista "cubes" on luonnollisten lukujen u kuutiot u^3 jarjestyksessa.
; 2. Lista "cube-sums" on kuutiosummat v^3+w^3 jarjestyksessa missa v<=w.
;    Se saadaan yhdistamalla listaa "cubes" itseensa sopivasti.
; 3. Luku n on Ramanujan joss se toistuu listassa "cube-sums".
(define (ramanujan)
  (let clean ((dirty (let cube-sums ((cubes (stream-map (lambda (x)
                                                          (* x x x))
                                                        (letrec ((from (lambda (m)
                                                                         (stream-cons m
                                                                                      (from (+ m 1))))))
                                                          (from 0)))))
                       (let ((cubes-car (stream-map (let ((add (stream-car cubes)))
                                                      (lambda (x)
                                                        (+ add x)))
                                                    cubes)))
                         (stream-cons (stream-car cubes-car)
                                      (stream-merge <
                                                    (stream-cdr cubes-car)
                                                    (cube-sums (stream-cdr cubes))))))))
    (if (= (stream-car dirty)
           (stream-car (stream-cdr dirty)))
        (stream-cons (stream-car dirty)
                     (clean (stream-dropwhile (lambda (x)
                                                (= x
                                                   (stream-car dirty)))
                                              dirty)))
        (clean (stream-cdr dirty)))))

Ensimmäinen erilliskoe. Koealue sama kuin kurssikokeessa. Tässä kokeessa huomioidaan kurssin aikana kerätyt lisäpisteet tehdyistä laskuharjoituksista.

Toinen erilliskoe. Koealue sama kuin kurssikokeessa. Tästä kokeesta alkaen lisäpisteet jäävät huomiotta.