Johdatus tietojenkäsittelytieteeseen I (2 ov) 16.12.1999

1. Reduktiivinen ongelmanratkaisu ja algoritmien asteittainen tarkentaminen tietojenkäsittelytieteessä. Kiinnitä erityistä huomiota reduktion, rekursion ja modulaarisuuden välisen suhteen selittämiseen.

2. Oletetaan ettei kokonaislukujen kertolasku ole käytettävissä.

1. Kirjoita fuktionaalinen algoritmimoduuli, joka laskee kahden ei-negatiivisen kokonaisluvun tulon yhteen- ja vähennyslaskun avulla.
2. Yleistä sitten algoritmisi myös negatiivisille kokonaisluvuille lisäämällä siihen moduuli, joka osaa kertolaskun merkkisäännöt ("plus kertaa plus on plus, plus kertaa miinus on miinus,....").

3. Tarkastellaan binääripuita, joiden solmut ovat luonnollisia lukuja. Olkoon käytettävissä MODULE alkuluku(luku) RETURNS totuusarvo

1. Tee funktionaalinen algoritmimoduuli, joka laskee alkulukujen määrän parametrina annetussa binääripuussa.
2. Laadi sitten algoritmi, joka laskee montako eri alkulukua puussa on. Ohje: Täsmällisen ratkaisun laatiminen tehtävään ei ole aivan helppoa. Jäsennä kuitenkin ongelma mahdollisimman pitkälle ja kirjoita ratkaisustasi korkean tason kuvaus. Anna moduuliesi otsikot formaalisti; sisäisen kuvauksen voit tarvittaessa antaa luonnollisella kielellä.