Yliopiston etusivulle Suomeksi Inte på svenska No english version available
Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

58131 - Tietorakenteiden harjoitustyö - syksy 2010

Kurssikuvaus

Kurssin tarkoitus on, että opiskelija suunnittelee ja toteuttaa itse ohjelman, joka ratkaisee jonkin laskennallisesti vaativan tehtävän käyttäen siihen erityisesti soveltuvia algoritmeja ja tietorakenteita (aihe-ehdotuksia löytyy tämän sivun lopusta).

Arvostelu

Labra on arvosteltu. Tarkentuneet arvosteluperusteet täällä.

Aikataulu

  • Aloitus to 9.9. klo 14-16 salissa A218
  • Ohjausajat ma klo 14-17 ja to 14-16 salissa B121
  • Tarvittaessa on mahdollista sopia myös yo. aikojen ulkopuoleinen ohjausaika
  • Työn etenemisen aste on raportoitava viikoittain
  • Palautusten deadline on pe 15.10. klo 23.59
  • Lahes valmis työ käydään demoamassa viimeisen labraviikon aikana

Ohjeita työn tekemiseen

Työn tekemisessä ja arvostelussa painotetaan laitoksen muita harjoitustöitä vähemmän dokumentointia. Ohjelmakoodin on kuitenkin oltava mahdollisimman selkeää, metodien on oltava lyhyitä, luokkien, muuttujien ja metodien on oltava kuvaavasti nimettyjä ja ohjelman rakenteen muutenkin kaikin puolin selkeä. Ohjelma toteutetaan Java-kielellä, sen ohjelmointikäytänteitä noudattaen. Myös muiden kielten käyttö on mahdollista.

Ohjelman lopullisessa toteutuksessa ei tule käyttää Javan valmiita tietorakenneluokkia (esim. HashMap) tai algorimeja (esim. Collections.sort). Kurssin yksi tavoite on oppia toteuttamaan itse tietorakenteita, ei käyttämään muiden toteuttamia. Nyrkkisääntönä vain perustietotyyppejä, taulukoita ja merkkijonoja saa käyttää, muu on tehtävä itse, erityisesti Tietorakenteet-kurssilla opetellut rakenteet. Javan muita apuvälineitä, kuten tiedostonkäsittelyluokkia, saa tietenkin käyttää. Jos olet epävarma jonkin luokan käyttämisestä, kysy ohjaajalta. Esim. ArrayListin käyttö on sallittua tietyissä tilanteissa.

Suosittelen vahvasti, että työ tehdään vaiheittaisesti siten, että ensin laitetaan kuntoon algoritmin ydin käyttäen apuna Javan valmista kalustoa. Esim. Huffman-koodauksessa tarvitaan prioritettijonoa eli minimikekoa. Määritellään rajapinta: 

public interface Puujoukko {
    public Solmu poistaPieninPuu();
    public void lisaaPuu(Solmu s);
    public boolean puitaJaljella();
    public boolean yliYksiPuuJaljella();
}
Aluksi toteutetaan rajapinta Javan valmiin kaluston avulla: 
import java.util.PriorityQueue;

public class PQPuujoukko implements Puujoukko {
    PriorityQueue puut;

    public PQPuujoukko() {
        puut = new PriorityQueue();
    }
    
    public Solmu poistaPieninPuu() {
        return puut.poll();
    }

    public void lisaaPuu(Solmu s) {
        puut.add(s);
    }

    public boolean puitaJaljella() {
        return !puut.isEmpty();
    }

    public boolean yliYksiPuuJaljella() {
        return puut.size()>1;
    }
}
ja käytetään prioriteetijonoa algoritmissa: 
    private Solmu teePuu(){
        Puujoukko puut = new PQPuujoukko();
        //...

        while( puut.yliYksiPuuJaljella() ){
            Solmu eka = puut.poistaPieninPuu();
            Solmu toka = puut.poistaPieninPuu();
            // ...
            puut.lisaaPuu(uusi);
        }

        Solmu thePuu = puut.poistaPieninPuu();
        return thePuu;
    }
Kun algoritmi on kunnossa, toteutetaan oma rajapinnan Puujoukko toteuttava luokka.

Kannattaa huomata, että Javan PriorityQueue-luokalla ei ole operaatiota, jonka avulla jonossa olevan olion avain-arvoa voisi muuttaa. Ainakin A*:ssä tälläistä tarvittaisiin. Asian voi hoitaa siten, että ensin poistaa olion, sitten muuttaa avaimen arvoa ja lisää alkion takaisin jonoon. Tapa on tehoton sillä poisto jonosta vie aikaa O(n). Muuta keinoa ei kuitenkaan ole.

Kannattaa siis pyrkiä toteuttamaan algoritmin ydin nopeasti rajapintojen takana olevien Javan valmiiden tietorakenteiden avulla ja sen jälkeen hankkiutua eroon valmiista kalustosta toteuttamalla rajapintojen takana olevat rakenteet itse.

Jos olet tähän asti ohjelmointu tekstieditoria käyttäen, suosittelen vahvasti jonkun IDE:n esim. NetBeansin tai Eclipsen käyttöön siirtymistä. Ohjeita NetBeans-noviiseille

Koodin kommentointi ja dokumentointi

Jokainen luokka, metodi ja tietorakenteiden kannalta oleellinen ja sisällöltään vähemmän kuin itsestäänselvä muuttuja ja attribuutti on syytä kommentoida. Metodien kommenttien tulee sisältää niiden parametrien ja paluuarvon merkitykset. Metodien sisäinen kommentointi ei ideaalitapauksessa pitäisi olla tarpeen, sillä metodien tulee olla kuvaavasti nimettyjä, kompakteja ja yksinkertaisia, helposti hahmotettavia kokonaisuuksia. Jos metodin toimintaa kuitenkin on vaikea hahmottaa pelkän koodin ja metodin yleiskommentin perusteella, voidaan sen koodia kommentoida sisäisestikin.

Yleisesti ottaen kannattanee käyttää formaalimuotoisia JavaDoc-kommentteja luokille, attribuuteille ja metodeille. Tätä ei kuitenkaan vaadita, kunhan mainitut asiat kommenteista löytyvät.

Dokumentoinnin tulee sisältää seuraavat osat:

  • Aiheen määrittely (kirjoitetaan pääosin 1. viikolla), josta käy ilmi
    • mitä algoritmeja ja tietorakenteita tarkalleen ottaen käytetään
    • miten ohjelmalle annettavia syötteitä tulkitaan
    • halutut aika- ja tilavaativuudet
  • Käyttöohje, josta käy ilmi
    • miten ohjelmakoodi käännetään
    • miten ohjelma suoritetaan ja sen eri toiminnallisuuksia käytetään
    • minkä muotoisia syötteitä ohjelma hyväksyy
  • Toteutuksen kuvaus algoritmien ja tietorakenteiden osalta
    • ohjelman yleisrakenne
    • perustelut valittujen ratkaisujen käyttöön
    • aika- ja tilavaativuudet
  • Suorituskyky- ja O-analyysivertailu, mikäli työ on vertailupainotteinen
  • Testaus (josta lisää alla)
  • Selostus toteutuksen puutteista (jos on) ja mahdolliset parannusehdotukset
  • Lähteet

Jouni Sirenin esimerkkidokumentti antanee hyvän kuvan siitä, mitä dokumentin tulisi sisältää.

Palautetun työn tulee sisältää testausraportti, josta käy ilmi:

  • mitä on testattu
  • millä syötteillä (erityisen tärkeää vertailupainotteisessa työssä)
  • miten testit on toistettavissa

Testaus on ideaalitapauksessa suoritettava ohjelma. Tällöin testi on helposti toistettavissa, mikä helpottaa toteutuksen tekoa jo varhaisessa vaiheessa. On erittäin suositeltavaa käyttää testaukseen JUnitia.

Tuntikirjanpito

Harjoitustyön tekijät pitävät tuntikirjanpitoa koko kurssin ajan. Kaikki harjoitustyöhön jollakin tavalla liittynyt aika kirjataan henkilökohtaiseen tuntikirjanpitoon puolen tunnin tarkkuudella. Myös ajankäytön tarkoitus merkitään. Esimerkiksi: 
Päivämäärä    Ajankäyttö    Tarkoitus
--------------------------------------------------
ma 25.7.      1,5 h         Ensimmäinen tapaaminen
ma 25.7.      3,0 h         Aiheisiin tutustuminen
ke 27.7.      0,5 h         Vapaaehtoinen ohjaus, aiheen valinta
to 28.7.      2,0 h         Tietorakenteiden suunnittelua
 .             .             .
 .             .             .
 .         +   .             .
           --------
           = 83,0 h
Tuntikirjanpitoihin suhtaudutaan vain tilastollisella mielenkiinnolla, eikä työnsä nopeasti tehneitä missään nimessä rangaista vähäisestä tuntimäärästä. Tarkoitus on selvittää harjoitustyöaiheiden todellisia vaativuuksia. Tuntikirjanpito auttaa vastaisuudessa sovittamaan harjoitustöiden aiheita tasavertaisiksi. Tuntikirjanpito palautetaan harjoitustyön dokumentin liitteenä. Tuntikirjanpidon laiminlyöminen vaikuttaa harjoitustyön arvosteluun.

Palautus

Työstä tulee palauttaa lähdekoodit, toteutusdokumentti, käyttöohjeet sekä muut tarpeelliset tiedostot pakattuna yhteen tiedostoon (esim. tar.gz tai zip). Javalla toteutetuista töistä palautetaan myös jar-tiedosto, jonka generointi ainakin NetBeansilla on vaivatonta, ks yllä oleva NetBeans-ohje. Testaukseen käytettävät testisyötteet ja -ohjelmat kannattaa palauttaa. Työn tulee olla käännettävissä ja ajettavissa Tietojenkäsittelytieteen laitoksen koneilla. Työn kääntäminen ja ajaminen tulisi onnistua mukana toimitettavien käyttöohjeiden avulla. Dokumentit tulisi palauttaa .txt-, .html- tai .pdf -muotoisina.

Valmis työ on palautettava viimeistään 15.10. klo 23.59, työ on käytävä demoamassa viimeisen viikon aikana

Arvostelu

Harjoitustyö pisteytetään seuraavien kriteereiden mukaan:
  • 30 p Ohjelma toimii oikein sallituilla syötteillä (testauksen syöteaineiston kattavuus vaikuttaa luonnollisesti pistemäärään)
  • 20 p Käytetyt tietorakenteet ja algoritmit ovat tehokkaita ja ongelman ratkaisuun sopivia. Tehokkuus tulkitaan yleisesti ottaen Tietorakenteet-kurssin hengessä
  • 10 p Toteutus on selkeä ja hyvin dokumentoitu

Harjoitustyön hyväksymisraja on 30 pistettä, mikä vastaa arvosanaa 1. Arvosanaan 5 riittää 50 pistettä.

Vertailupainotteisessa työssä vertailun maksimipistemäärä on 10 — tällöin oikeellisuudesta saa enintään 25 p ja tehokkuudesta 15 p.

Näiden arvostelutekijöiden lisäksi on tietysti oleellista, että työssä vaaditut osat on toteutettu itse kurssin aikana. Lisäksi ainakin seuraavat seikat vaikuttavat pisteytykseen:

  • Työ valmistuu määräajassa, Jokaista määräajan jälkeen käytettyä ylimääräistä päivää kohden vähennetään 5 pistettä.
  • Työ on testattu kattavasti (ainakin jonkinlainen testaus tulee löytyä)
  • Aiheen vaikeus
  • Opiskelija raportoi säännöllisesti työn edistymisestä käymällä ohjauksissa
  • Työtuntikirjanpito on tehty (tuntimäärä ei vaikuta)

Mahdollisia aiheita

Sanaindeksi

Sanaindeksi on tietorakenne, johon luetaan tekstiaineisto. Tämän jälkeen rakenne osaa hakea syötteenä annettuja sanoja tai sananalkuja sisältävät rivit (AND-hakuna, ks. esimerkki) ja tulostaa ne. Ohjelman on tuettava useamman sanan hakemista kerrallaan useammasta tiedostosta. Ajatus on, että aineiston jäsentäminen muistiin on kerran suoritettava raskas toimenpide, mutta tämän jälkeen voidaan tehdä useita hakuja nopeasti. Käytä trie-rakennetta ja toteuta lasten talletus jollain tehokkaalla tavalla. Tehokas indeksoija myös säilyttää tekstitiedoston levyllä, ja hakee pyynnöstä vain tarvittavat osat siitä (ks. RandomAccessFile).

Esimerkki toiminnasta: 
> hae vanha

kalev1.txt:34:vyöltä vanhan Väinämöisen,
kalev1.txt:294:Vaka vanha Väinämöinen
kalev2.txt:46:Vaka vanha Väinämöinen
kalev2.txt:92:Silloin vanha Väinämöinen
kalev2.txt:104:Siitä vanha Väinämöinen
kalev2.txt:128:Vaka vanha Väinämöinen
kalev2.txt:146:Vaka vanha Väinämöinen
kalev2.txt:240:Siitä vanha Väinämöinen
kalev2.txt:260:Vaka vanha Väinämöinen
kalev2.txt:274:Sanoi vanha Väinämöinen:
kalev2.txt:290:Siitä vanha Väinämöinen
kalev2.txt:355:vaka vanha Väinämöinen
kalev2.txt:362:Siinä vanha Väinämöinen
kalev2.txt:368:Sanoi vanha Väinämöinen:

> hae vanha vaka

kalev1.txt:294:Vaka vanha Väinämöinen
kalev2.txt:46:Vaka vanha Väinämöinen
kalev2.txt:128:Vaka vanha Väinämöinen
kalev2.txt:146:Vaka vanha Väinämöinen
kalev2.txt:260:Vaka vanha Väinämöinen
kalev2.txt:355:vaka vanha Väinämöinen

A*-algoritmi

Huffman-koodiin perustuva tekstitiedostojen pakkausalgoritmi

Huffman-koodaus on 1950-luvulta peräisin oleva häviötön ja yleiskäyttöinen tiedontiivistystekniikka. Alkuperäisessä tekstissä useimmin esiintyvät merkit korvataan lyhyillä bittimuotoisilla koodisanoilla. Ohjelman tulee toimia bitittäisesti (ohje). Ohjelma ottaa parametrikseen tiedoston ja pakkaa sen. Ohjelman on osattava purkaa pakkaamansa tiedosto alkuperäiseen muotoonsa. Halutessaan voi toteuttaa myös adaptiivisen version algoritmista.

  • lisää infoa esim. Cormen ja M.A.Weiss:in tietorakennekirjat

Hakurakenteiden suorituskykyvertailu

  • toteuta seuraavista ainakin kaksi hakurakennetta ja vertaile niiden suorituskykyä
    • hajautusrakenne
    • AVL-puu
    • punamusta puu
    • AA-puu
    • splay-puu
    • ...

Kauppamatkustajan ongelma, tarkka- ja/tai aproksimaatioalgoritmi

Kahden toisiaan vastaavan algoritmin tai tietorakenteen vertailu

Säännöllisten lausekkeiden tulkki

Syötteeksi annetaan säännöllinen lauseke, josta ohjelma muodostaa lauseketta vastaavan tila-automaatin. Tämän jälkeen ohjelmalle voidaan syöttää merkkijonoja ja ohjelma kertoo täsmäävätkö ne lausekkeeseen. Ohjelman tulisi tukea ainakin katenaatiota, vaihtoehtoisuutta (alternation eli "a|b"), *-operaattoria (a*) ja alilausekkeita. Halutessaan työhön voi lisätä "+"- ja "?"-operaattorit sekä merkkiluokat ([A-Z]).

Esimerkkejä:

  • Lausekkeeseen kahvi(maito|kerma) täsmäävät merkkijonot "kahvimaito" ja "kahvikerma".
  • Binäärilukuja tunnistava lauseke: (0|1)(0|1)*
  • Liukulukuja tunnistava lauseke: (0|1|2|3|4|5|6|7|8|9)*.(0|1|2|3|4|5|6|7|8|9)* (hyväksyy myös merkkijonon ".")
  • Edellinen merkkiluokkia käyttäen: [0-9]*.[0-9]*
Viitteet: Laskennan mallit -kurssimateriaali, Sipser: Introduction To The Theory Of Computation, Implementing Regular Expressions

Pelin tekoäly

Lempel-Ziv-pakkaus

Monet yleisessä käytössä olevat pakkausohjelmat (zip, compress) käytävät jotain Lempel-Ziv -algoritmin varianttia. Näistä suositeltavin toteuttava on LZW-algoritmi. Ohjelma ottaa parametrikseen tiedoston ja pakkaa sen. Ohjelman on osattava purkaa pakkaamansa tiedosto alkuperäiseen muotoonsa.

Verkon maksimivirtaus

  • Ford-Fulkerson ja Edmund-Karp-algoritmit
  • ks. Cormen
  • lisätietoja

Oma aihe

  • ...

Lisää aiheita ja muutakin hyödyllistä löytyy aikaisempien tiralabrojen sivuilta

 
Palaute laitokselle | Tiedekunnan etusivulle | Yliopiston etusivulle