Osa 1: Kysymykset 1-2
Osa 2: Kysymykset 3-5
1. Algoritmin käsite ja algoritmin laatiminen imperatiivisessa paradigmassa. Mitä tarkoitetaan (algoritmi)moduulilla ja mitä etua moduulien käytöllä saavutetaan.
2.
a) Määrittele tarkasti binääripuu sekä järjestetty eli
lajiteltu binääripuu. Kerro miten listan alkioiden järjestämisessä
(eli lajittelussa) voidaan käyttää järjestettyä binääripuuta
hyödyksi. Selitä algoritmin idea esimerkkilistalla 9, 4, 15, 1,
7, 10.
b) Kirjoita moduuli, joka muodostaa parametrina annetusta lukuja sisältävästä listasta järjestetyn binääripuun.
3. Esittele käsitteet laskettavuus, osittainen laskettavuus ja kompleksisuus sekä tarkastele niiden suhtautumista toisiinsa. Määrittele myös ns. pysähtymisongelma ja kerro sen liittyminen em. käsitteisiin.
4. Esitä kiikun (yhden bitin muistava looginen piiri) toimintaperiaate ja osoita totuustaulun avulla, että seuraava looginen piiri toimii kiikkuna. Selitä myös miten totuustaulun rivien arvot on päätelty.
5. Vertaile syvyys- ja leveyashakua ja niiden algoritmeja (esitä algoritmien perusidea). Sovella algoritmeja (ja esitä tarvittavien tietorakenteiden sisältö) seuraavaan labyrinttiin ja esitä missä järjestyksessä haku etenee käyttäen näitä hakumenetelmiä, kun heuristiikkana on i, e, p, l (eli pyritään ensin aina itään, sitten etelään jne.).
