Ohjelmointiprojekti (merkkijonomenetelmät, kevät 2005)
Projektin (alustava) kuvaus
Projektissa toteutetaan jokin luentojen aiheisiin liittyvä algoritmi.
Toteutuksen toimivuutta ja tehokkuutta testataan sopivalla aineistolla. Toteutuskielenä esim. C, C++ tai Java.
Kurssin päätteeksi järjestetään posteritilaisuus, johon kukin opiskelija(ryhmä) laatii algoritmin toimintaa ja kokeellisia
tuloksia esittelevän posterin. Toteutetun algoritmin lähdekoodi sekä ohjeet sen
kääntämiseen tulee toimittaa harjoitustyön ohjaajalle viikkoa ennen posteritilaisuutta. Projektin voi
tehdä kahden hengen ryhmissä.
Aikataulu
- Luentojen ja laskuharjoitusten yhteydessä voi tulla varaamaan aiheen. Katso alla oleva aihelistaus.
- Kurssin viimeisissä laskuharjoituksissa osa ajasta on varattu harjoitustyön ohjaukseen.
- Projektin suunnitelma palautetaan 4.4. mennessä.
- Toteutettu algoritmi on palautettava 26.4. mennessä.
- Posteriesittely järjestetään tiistaina 3.5. klo 10-13 salissa Z.
- Postereiden ohjausta järjestetään viikolla 17.
Arvostelu
Projektista voi saada 20p. Arvostelussa huomioidaan toteutuksen, testauksen ja posteriesityksen taso, sekä aiheen vaikeus.
Suunnitelma
Projektista palautetaan 4.4. mennessä vapaamuotoinen suunnitelma, josta selviää ainakin
- Tehtävän kuvaus, esim. mitkä algoritmit toteutetaan ja miten niitä vertaillaan.
- Toteutuskieli ja -ympäristö.
- Työnjako ryhmässä.
Suunnitelma voi olla kirjoitettu esimerkiksi ranskalaisilla viivoilla. Suunnitelman
esitystapa ei vaikuta arvosteluun.
Posteri
Kukin ryhmä tekee posterin (kokoa A1), joka sisältää mm.
- Algoritmin kuvauksen: Minkä ongelman algoritmi ratkaisee,
algoritmin perusidea (kuvin havainnollistettuna), mitä muita algoritmeja samaan ongelmaan tunnetaan.
- Toteutuksen kuvauksen: Mitä muutoksia alkuperäiseen (perustelu), kuten tietorakenneratkaisut,
heuristiikat.
- Suoritusympäristön kuvauksen, kuvauksen kokeissa käytetystä datasta, ym.
- Kokeelliset tulokset esitettynä taulukoin, diagrammein, ym.
- Kokeellisissa tuloksissa mm. vertailut muihin menetelmiin (esim. toisen ryhmän eri algoritmin toteutukseen samaan ongelmaan),
sekä oman menetelmän tarkempi vertailu eri parametrien arvoilla (syötteen pituus, aakkoston koko, sallittujen virheiden määrä, ym.)
- Tulosten tulkinta (millä syötteellä algoritmi toimii hyvin/huonosti)
- Esitä asiat siinä muodossa, että myös kurssia käymätön voi asian ymmärtää.
Teknisiä ohjeita:
- Posteritelineeseen mahtuu noin 3 x 3 A4-kokoista arkkia leveyssuunnassa (plus otsikko).
- A4-palasista koostuvan posterin voi tehdä esim. Windowsin Powerpointilla tai Linuxissa OpenOfficen vastaavalla työkalulla tai LaTeXilla (google: latex poster).
- Värejä kannattaa käyttää rohkeasti.
- Posteritelineet ja tykötarpeet posterin pystytykseen tulevat talon puolesta.
Uusi nopea variantti Boyer-Moore
algoritmista: Artikkelissa [CF03] on
kuvattu ns. Forward-Fast-Search-algoritmi, joka kokeiden mukaan
toimii usein nopeammin kuin aikaisemmat Boyer-Moore-algoritmin
variaatiot (joita on useita). Tehtävänä on toteuttaa tämä
algoritmi, ja verrata sen toimintaa esim. Boyer-Moore-Horspool
algoritmiin, tai johonkin muuhun helposti toteutettavaan
varianttiin.
Eliminointimenetelmä:
Tehtävänä on toteuttaa luennolla kuvattu eliminointimenetelmä.
Siinä tarvittavan witness taulukon W lineaariaikainen
muodostusalgoritmi on kuvattu 2. laskuharjoituksen 4. tehtävän
mallivastauksessa. Menetelmän nopeutta voi verrata esimerkiksi
Knuth-Morris-Pratt-algoritmiin.
Aho-Corassic-algoritmi:
Tehtävänä on toteuttaa luennolla kuvattu Aho-Corassic-algoritmi
sekä jokin/joitakin sen sovelluksia. Esimerkiksi
luennolla esitetyt Bird-Baker-algoritmi
kaksi-ulotteiseen merkkijononsovitukseen ja/tai
hahmon ositukseen perustuva seulontamenetelmä
likimääräiseen merkkijononhakuun. Työssä haasteena on
tilasiirtymien tehokas toteutus (vaihtoehtoina mm. listat,
taulukot, tasapainoiset hakupuut, hajautus, ym.).
Kalain algoritmi hahmonsovitukseen
jokerimerkeillä: Tehtävänä on toteuttaa artikkelissa
[Kal02] kuvattu O(n log m) ajassa toimiva
satunnaisalgoritmi hahmonsovitukseen jokerimerkeillä. Toteutusta
voi verrata esimerkiksi triviaalialgoritmiin tai
shift-or-algoritmin yleistykseen (Laskuharjoitus 3, tehtävä 3).
Lävistäjämenetelmä:
Tehtävänä on toteuttaa luennoilla kuvattu lävistäjämenetelmä
kahden merkkijonon editointietäisyyden laskentaan. Tällä
tarkoitetaan tehostettua versiota algoritmista, joka toimii
ajassa O(sm) ja tilassa O(s min(s,m)), missä s on vertailtavien
jonojen editointietäisyys. Menetelmän nopeutta tulee verrata
esimerkiksi O(mn) aikaiseen perusalgoritmiin.
Myersin bittirinnakkainen
algoritmi: Tehtävänä on toteuttaa luennoilla kuvattu
Myersin bittirinnakkainen algoritmi likimääräiseen
hahmonsovitukseen, sekä mahdollisesti tämän yleistys tapaukseen
jossa hahmon pituus on suurempi kuin tietokoneen sananpituus.
Toteutusta tulisi verrata perus-dynaamiseen ohjelmointiin.
Binäärihaku
loppuosataulukosta: Tehtävänä on toteuttaa luennoilla
kuvattu O(m + log n) ajassa toimiva merkkijonojen binäärihaku
loppuosataulukolle. Loppuosataulukon voi muodostaa jollakin
valmiilla toteutuksella. Toteutusta tulisi verrata
yksinkertaisempiin O(m log n) ajassa toimiviin
hakualgoritmeihin.
RMQ-esiprosessointi:
Taulukon T osaväliminimi (range minimum) RM(i,j) on osataulukon
T[i..j] pienin alkio. Mikä tahansa taulukko on mahdollista
esiprosessoida lineaarisessa ajassa niin, että mikä tahansa
osaväliminimi voidaan laskea vakioajassa. Tehtävänä on toteuttaa
artikkelin [AGKR02] luvussa 2.2 on kuvattu
algoritmi tähän tarkoitukseen.
Shift-or-algoritmi superaakkostossa:
Artikkelissa [Fre03] on kuvattu
shift-or-algoritmin muunnelma tilanteeseen, jossa useampi tekstin merkki
on pakattu yhteen supermerkkiin. Tehtävänä on toteuttaa algoritmi ja
verrata sitä normaaliin shift-or-algoritmiin.
Yksinkertainen seulontamenetelmä
Artikkelissa [GL89] on kuvattu
yksinkertainen seulontamenetelmä likimääräiseen hakuun. Menetelmä
perustuu merkkijakauman ylläpitoon hahmon pituisessa tekstin ikkunassa;
likimääräisessä esiintymässä pitää merkkijakaumien täsmätä sopivalla
tarkkuudella. Menetelmä on kuvattu k epätäsmäystä -ongelmalle, mutta
työssä on tarkoitus muokata se k virhettä -ongelmaan.
Loppuosapuun ja LZW-pakatun loppuosataulukon vertailu.
Harva dynaaminen ohjelmointi.
Geneerinen Boyer-Moore-Horspool.
Oma aihe
- [AKGR02]
- S. Alstrup, C. Gavoille, H. Kaplan, T. Rauhe: Nearest common
ancestors: a survey and a new distributed algorithm Proc. 14th
Symposium on Parallel Algorithms and Architectures (SPAA '02).
Sivut 258-264, 2002.
- [CF03]
- D. Cantone ja S. Faro:
Forward-Fast-Search: Another Fast Variant of the Boyer-Moore String
Matching Algorithm. Teoksessa Proc. Prague Stringology
Conference (PSC '03), sivut 10-24, 2003.
- [Kal02]
- A. Kalai: Efficient
Pattern-Matching with Don't Cares. Proc. 13th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA '02), sivut 655-656, 2002.
- [Fre03]
- Kimmo Fredriksson:
Shift-or string matching with
super-alphabets. In Information Processing Letters (IPL), sivut (87:)201-204, 2003.
- [GL89]
- R. Grossi ja F. Luccio: Simple and efficient string matching with
k mismatches. In Information Processing Letters (IPL), sivut (33(3)):113-120, 1989.
Pasi Rastas
