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.
- seminaaripaperi (PDF) [english]
- esitelmäkalvot (PDF) [english]
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.
- artikkelitiivistelmä (PDF)
- esitelmäkalvot (PDF)
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.
- esitelmäkalvot (PDF) [english]
- raportti (PDF) [english]
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.
- raportti (PDF)
- esitelmäkalvot (PDF)
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ä.
- raportti (PDF)
- esitelmäkalvot (PDF)
- lähdekoodit (ZIP)
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ä.
- kotisivu
- posteri (PDF)
- lähdekoodit (TAR.GZ)
- README (TXT)
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ä.
- tutkielma (PDF)
- esitelmäkalvot (PDF)
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.
- lähdekoodit ja dokumentaatio (TAR.GZ)
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.
- koko dokumentaatio (ZIP)
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.
- käännetty ohjelma (JAR)
- käyttöohje (HTML)
- lähdekoodit (ZIP)
- koko dokumentaatio (ZIP)