Johdatus tietojenkäsittelytieteiseen Tentti 20.12.2004

JTKT I -kysymykset


1. Miten toimii asteittain tarkentava menetelmä algoritmien rakenteiden suunnittelussa. Mitä yhteyksiä sillä on modulaarisuuteen? Mitä pitää ottaa huomioon sitä käytettäessä?
   
   
2. a) Mitä tarkoitetaan tietotyyppien abstrahoinnilla?
   b) Miten abstrahointi näkyy listan määrittelyssä?
   
   
3. 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 hyväksi. 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.
   
   JTKT II -kysymykset
   
   
4. a) Esitä kääntäjän toiminta ja tarvittavat vaiheet käännettäessä korkean tason kielellä kirjoitettua ohjelmaa konekielelle.
   
   b) Tarkastellaan a)-kohtaa. Esitä esimerkkinä (myös konekielinen koodi) mitä tapahtuu toistorakenteelle (jäsennyksessä ei tarvitse muistaa luentomonisteen kielioppia). Voit käyttää symbolista tai ei-symbolista konekieltä.
   
   k:=1
   WHILE n>0 DO
   k:=k * n
   n:=n - 1 ENDWHILE
   
   
5. Selitä kompleksisuuden käsite. Mitä sillä mitataan? Mitä eroa on tehtävän ja algoritmin kompleksisuudella?
   
   
6. Selitä lyhyesti
   a) pysähtymisongelma
   b) ekvivalenssiongelma
   c) osittainen laskettavuus