Tietorakenteiden ja algoritmien harjoitustyö

Joensuun yliopisto, Tietojenkäsittelytieteen laitos

(Project on Data Structures and Algorithms, 2 cu)

Syksyllä 2005 töitä ohjaa ja jakaa Matti Tedre, huone T/B323, mmeri at cs.joensuu.fi.

Yleistä

Kurssi on vanhan opinto-ohjelman mukainen, mutta sillä voi korvata uuden opinto-oppaan mukaisen kurssin parityön.

Ohjelmointikielivaihtoehdot ovat Pascal, C ja Java.

Työ on tehtävä kahden kuukauden kuluessa sen antamisesta

Perusohjeena (mm. dokumentoinnista) käytetään Ohjelmoinnin peruskurssin työohjetta. Työn dokumennoinnissa keskitytään moduulien liittymien dokumentointiin sekä itse tehtäväalgoritmin toiminnan ja aikavaativuuden kuvaamiseen. Työn kannalta vähemmän tärkeiden osien (esim. käyttöliittymän) toteutusdokumentointi voi olla kevyempi, kunhan käyttöohje on riittävä. Ristiinviittaustaulun sijaan voi piirtää kuvan moduulien käytöstä ja kunkin moduulin aliohjelmien keskinäisistä kutsuista. Lisäksi on syytä piirtää kuva talletustietorakenteesta.

Kussakin työssä käytetty abstrakti tietorakenne (esim. verkko, joukko) tulee toteuttaa erikseen (voitava irrottaa muusta ohjelmasta). Tietorakenteen toteutuksen julkinen osa sisältää vain operaatiot ja tyypit.

Varsinaisen työnannon mukaisen algoritmin ja pääohjelman (tai esimerkkiohjelman) tulee käyttää toteutettuja abstraktin tietorakenteen operaatioita, eikä missään tapauksessa käyttää toteutuksen kenttiä suoraan.

Ohjelma koostuu siis useimmiten vähintään kolmesta moduulista:

Myös dokumentointi jakautuu absraktin tietorakenteen liittymän ja toteutuksen dokumentointiin, sekä varsinaisen algoritmin dokumentointiin.

Parityöt

Työn voi tehdä halutessaan myös parityönä. Tällöin työnanto sisältää yleensä kaksi erillista abstraktia tietotyyppia, algoritmin ja testauksen. Paritöissä työ suunnitellaan (mm. ADT liittymät ja testaus) ensin ja suunnitelma on hyväksytettävä ohjaajalla.

Työn dokumenteissa ja ohjelmakoodissa (moduuleissa, tarvittaessa aliohjelmissa) on oltava maininta siitä kumpi ko. osan on tehnyt. Jos osaan ovat osallistuneet molemmat, on kummankin osuus jaoteltava tarkemmin.

Parityössä molemmille annetaan sama arvosana jollei ym. selvitys, työn osien laatuerot (yhdessä tekijöiden kanssa keskusteltuna) anna aihetta erilliseen arvosteluun.

Ohjelmointikieli

C-kieliset ohjelmat tulee kirjoittaa ANSI-C:llä, ja niiden tulee kääntyä gcc-kääntäjällä. ADT:n liittymä tulee toteuttaa .h -tiedostona, ADT:n toteutus erillisenä .c -tiedostona, algoritmi omana moduulinaan ja pääohjelman vielä omana moduulinaan.

Pascal-kieliset ohjelmat voi kirjoittaa laajennetulla Pascalilla (mutta ei kuitenkaan esimerkiksi vain Turbo Pascalista tai Delphistä löytyviä kirjastoja käyttäen). Esimerkiksi string-tyypin käyttö on luvallista, mutta Turbo Pascalin crt-modulia ei tule käyttää. Näin ohjelman voi kääntää myös mm. cs:n gpc-kääntäjällä (kuten ohjaaja tekee). Kuten C:lläkin, ohjelmakoodi kannattaa jakaa erillisiksi ADT:n toteutustiedostoksi, algoritmitiedostoksi ja pääohjelmatiedostoksi.

Esimerkki Pascalin moduulien käytöstä löytyy tra-kurssin esimerkkeistä.

Java-kielisten töiden on käännyttävä ja toimittava cs:n Java-kääntäjällä ja tulkilla.

Muuta

Algoritmia testaavan ohjelman käyttöliittymä kannattaa valita helppokäyttöiseksi (yksinkertaiseksi), sillä ohjelmaa tulee testattua usein samalla syötteellä. Useimpiin töihin eräs hyvä tapa on käyttää syötteenä tekstitiedostoa. Käyttäjä siis luo oikeanlaisen tekstitiedoston ja ohjelma lukee syötteensä tästä tiedostosta (edellyttäen että tiedosto on oikeaa muotoa). Näin saman syötteen (vaikkapa monimutkaisemmankin verkon) testaaminen ohjelman kehityksen ja debuggauksen eri vaiheissa onnistuu kivuttomasti.

Jos ongelman algoritminen ratkaisu tuntuu vaikealta tai mahdottomalta, algoritmeja moneen apuun löytyy kirjallisuudesta (jota on lueteltu TRA-kurssin verkkosivulta). Rohkeasti vain kirjastoa käyttämään. Työn ohjaaja voi myös antaa kirjallisuusviitteitä. Varsinaisten TRA-kirjojen lisäksi (matematiikan hyllyistä) löytyvät verkkoteorian kirjat, erityisesti Harary: Graph Theory, ovat käyttökelpoisia. Tkt-kirjaston aineistokoneelta (kirjaston sisäpuolella) löytyy 9 hyvää algoritmikirjaa sähköisessä muodossa (Dr. Dobb's Essential Books on Algorithms and Data Structures). Kirjoista voi myös tehdä vapaatekstihaun. Kirjat löytyvä ko. koneen www-selaimen kirjanmerkeistä. CD-ROM on myös lainattavissa kirjastosta.

Checklist

Ennen työn palautusta kannattaa tarkastaa seuraavat asiat: