Opiskelutuotokset

Seuraavassa on listattu opiskeluuni liittyviä projektitöitä ja raportteja. Ohjelmia saa käyttää vapaasti ei-kaupallisiin tarkoituksiin.

Branching

Seminar: Exact Exponential Algorithms, syksy 2011
Seminaaripaperi ja esitelmä käsittelevät haarautumista vaikeiden kombinatoristen ongelmien ratkaisemisessa. Monille ongelmille ei tiedetä polynomiaikaista ratkaisua. Tyypillisesti tällaisiin ongelmiin on olemassa helppo eksponentiaaliaikainen triviaaliratkaisu joka käy kaikki mahdolliset kombinaatiot läpi. Haarautuminen on eräs perustavaa laatua oleva tapa suunnitella nopeampia eksponentiaalisia algoritmeja kyseisiin ongelmiin.

Dominointianalyysi

Approksimointialgoritmit, syksy 2010
Raportti ja esitelmä dominointianalyysista, vaihtoehtoisesta tavasta mitata approksimointialgoritmin hyvyyttä. Kombinatoristen optimointiongelmien likimääräiseen ratkaisuun tarkoitetuissa algoritmeissa analysoidaan tyypillisesti approksimointisuhdetta, eli sitä kuinka hyvin algoritmi pärjää verrattuna parhaaseen mahdolliseen ratkaisuun. Dominointianalyysissa sen sijaan mitataan algoritmin ratkaisujen suhteellista sijoittumista kaikkien mahdollisten ratkaisujen joukossa.

Natural Image Statistics: Overcomplete models & Lateral interactions and Feedback

Seminar: Neuroinformatics 2, kevät 2010
Esitelmä käsittelee seminaarikirjan Natural Image Statistics luvut 13 ja 14. Raportti on puolestaan lyhyt tiivistelmä koko kurssin sisällöstä. Seminaarissa käsiteltiin tapoja mallintaa luonnollisia (valo)kuvia ja oppia kuvista erilaisia tyypillisiä piirteitä. Menetelmät ovat läheisessä yhteydessä ihmisaivojen tapaan käsitellä nähtyä kuvaa.

Lyhimmän polun etsintä verkossa muistihierarkiatehokkaasti

Seminaari: Muistihierarkia-algoritmit, kevät 2009
Raportti käsittelee lyhimmän polun etsimistä verkossa halutusta lähtösolmusta verkon muihin solmuihin. Muistihierarkiatehokkuus on raportissa avainsana. Lyhimmän polun ongelma on hyvin tunnettu perinteisessä yksitasoisen muistin mallissa (RAM-malli). Nykyaikainen tietokone sisältää kuitenkin useita eri kokoisia ja nopeuksisia muistitasoja. Vaatimus muistihierarkiatehokkuudesta tarkoittaa, että algoritmin tulisi toimia tehokkaasti myös tällaisessa tilanteessa.

Kauppamatkustajan ongelman optimoija

Diskreetin optimoinnin harjoitustyö, kevät 2009
Ohjelma, joka pyrkii löytämään mahdollisimman lyhyen reitin kauppamatkustajan ongelmaan suuntaamattomassa verkossa. Ongelma on tunnetusti NP-kova, eli optimaalisen reitin löytämiseen ei tiedetä tehokasta (polynomiaikaista) algoritmia. Toteutukseni perustuu Lin-Kernighan-heuristiikkaan, joka pyrkii optimoimaan annettua reittiä vaihtelemalla kaaria sopivasti ristiin. Ohjelma osaa lukea TSPLIB-kokoelmassa käytettyä tiedostoformaattia. Toteutettu C-kielellä.

Likimääräinen hahmon etsintä bittirinnakkaisesti

Merkkijonomenetelmät, syksy 2008
Toteutettuja algoritmeja likimääräisen hahmon etsintään tekstiaineistosta sekä posteri, jossa algoritmeja verrataan. Pienryhmissä tehtävään projektityöhön sisältyi merkkijonoalgoritmin toteuttaminen ja vertailu muihin vastaaviin algoritmeihin. Yhdessä Paavo Koskisen kanssa valitsimme aiheeksemme likimääräisen hahmon etsinnän ja toteutimme Wu-Manberin sekä Myersin bittirinnakkaiset algoritmit sekä Ukkosen algoritmin. Algoritmit on toteutettu C-kielellä.

Yksinkertaisen monikulmion kolmiointialgoritmit

Tieteellisen kirjoittamisen kurssi / kandidaatin tutkielma, kevät 2008
Tutkielma käsittelee useita erilaisia yksinkertaisen monikulmion kolmiointialgoritmeja. Monikulmiota sanotaan yksinkertaiseksi, jos se on yhtenäinen eikä siinä ole reikiä. Kolmiointi tarkoittaa tässä tapauksessa monikulmion sisuksen jakamista kolmion muotoisiin osiin siten, että muodostuvien kolmioiden kulmapisteinä käytetään alkuperäisen monikulmion kulmapisteitä.

LZW-pakkaja ja -purkaja

Tietorakenteiden harjoitustyö, syksy 2006
LZW-algoritmia käyttävät ohjelmat tiedoston pakkaamiseen ja purkamiseen. Lempel-Ziv-Welch-algoritmissa pakattava tieto tiivistetään koodaamalla eri mittaisia datapätkiä vakiokokoisilla koodeilla. Kooditaulu muodostetaan pakkaamisen edetessä, ja pakkauksen hyötysuhde paranee loppua kohden. Kooditaulua ei kuitenkaan tallenneta pakattuun tiedostoon, vaan se voidaan rakentaa uudelleen purkamisen aikana. Toteutukseni on perusalgoritmin muunnos, joka käyttää vaihtelevaa koodipituutta ja tukee kooditaulun pakkauksenaikaista alustamista. Toteutuskielenä on Java.

Hiihtokisojen tulospalveluohjelmisto

Tietokantojen harjoitustyö, syksy 2006
Web-pohjainen hiihtokilpailujen väliaikatilanteen ja lopputulosten syöttämiseen ja seurantaan tarkoitettu ohjelmisto. Ideana on, että järjestäjät ovat kannettavien tietokoneiden ja verkkoyhteyden kanssa väliaikapisteillä syöttämässä väliaikoja. Yleisö pystyy seuraamaan verkkosivun kautta kilpailun tilannetta reaaliajassa. Toteutettu PHP:llä käyttäen PostgreSQL-tietokantaa.

Funktiopiirturi

Ohjelmoinnin harjoitustyö, kevät 2006
Yksinkertainen yhden parametrin funktioiden kuvaajien piirtämiseen tarkoitettu ohjelma. Funktio syötetään lausekkeena, joka voi sisältää yleisimpiä matemaattisia operaattoreita (+, -, ...) ja funktioita (sqrt, sin, ...). Ohjelmassa on mahdollista muuttaa suurennosta. Toteutettu Javalla.
Viimeksi muutettu 11.5.2016