Johdatus tietojenkäsittelytieteeseen I 11.11.2002

1. a) Anna määritelmä abstraktille tietotyypille lista ja esitä listalle suoritettavat tyypilliset operaatiot (ei algoritmeja). Millaisia rakenteita ovat pino ja jono?

   b) Oletetaan, että lukuja sisältävä lista toteutetaan vektorina. Kirjoita moduuli, joka palauttaa parametrina annetun n-komponenttisen listan alkioiden summan.

2. Miten ohjelmien yleiskäyttöisyys ja siirrettävyys on parhaiten toteutettavissa imperatiivisissa ohjelmissa? Mitä suunnitteluseikkoja tulee tällöin ottaa huomioon?

3. Eläinlajien evolutionaarinen kehitys voidaan kuvata puurakenteena, jonka solmuja eri eläinlajit ovat. tällöin puun juurena on jokin muinainen kantaeläin, ja lehtinä ovat nykyiset eläinlajit

   a) Oletetaan, että puun ariteetti on 2. Kirjoita funktionaalinen algoritmimoduuli, joka saa parametrinaan evoluutiopuun ja palauttaa eläinlajien lukumäärän puussa

   b) Olkoon käytössä joukko erilaisia eläinluokkia tunnistavia algorimimoduuleja:

   MODULE nisäkäs(eläinlaji) RETURNS totuusarvo
   MODULE matelija(eläinlaji) RETURNS totuusarvo
   jne.

   Kirjoita funktionaalinen algoritmimoduuli, joka saa parametrinaan evoluutiopuun (ariteetti=2) ja palauttaa nisäkäslajien lukumäärän puussa.