58093-3 Merkkijonomenetelmät (4 ov), kevät 2005

Ajankohtaista

Erilliskokeen 10.6. tulokset (Intranet)
Arvosteluun voi tutustua ottamalla yhteyttä luennoijaan.

Tulokset (Intranet)
Arvosteluun voi tutustua ottamalla yhteyttä luennoijaan.

Ohjelmointiprojektin tulokset niille, jotka eivät osallistuneet kurssikokeeseen (Intranet).

Vastaa kurssikyselyyn.

Koetta (to 12.05. klo 9-13 A111 ja B123) varten voi harjoitella tekemällä harjoittelutehtäviä.

Kurssin loppuohjelma:

• ma 18.4. Viimeiset laskarit ja viimeinen luento. Luennon aiheena on laitoksella kehitteillä oleva merkkijonoalgoritmien kirjasto.
• ti 26.4. Projektin ohjelmien palautus (sähköpostitse Pasi Rastaalle). Huom. mukana on oltava käännös- ja käyttöohjeet.
• pe 29.4. klo 10-12 sali C221. Mahdollisuus tutustua posteritauluun ja nähdä esimerkkipostereita.
• ti 3.5. klo 10-13 sali C222. Posterinäyttely. Klo 10-11 Posterien asettelu. Klo 11-13 laitoksen henkilökuntaa vierailee katsomassa postereita.

Luento maanantaina 11.4. on peruutettu. Sen sijasta pidetään ylimääräinen luento viikkoa myöhemmin maanantaina 18.4.

Harjoitus 8 pidetään poikkeusellisesti keskiviikkona 6.4. klo 10:15-12 salissa CK107. Siis maanantaina 4.4. ei ole harjoituksia (mutta luento on).

Ohjelmointiprojektin suunnitelma on palautettava 4.4. Sen voi jättää esim. luennolla tai sähköpostitse.

Pääsiäinen

• Viikolla 12 (ennen pääsiäistä) luennot ja laskarit normaalisti 21.3. ja 23.3.
• Viikolla 13 (pääsiäisen jälkeen) ei ole luentoja eikä laskareita

Ohjelmointiprojektin ohjeita ja aiheita on nyt nähtävillä.

Tiistain laskuharjoitusryhmä on peruutettu osanottajien vähyyden vuoksi. Ota yhteyttä luennoijaan tai harjoitusten vetäjään, jos maanantain ryhmä ei ehdottomasti sovi.

Asema opetuksessa

• Valinnainen laudatur-kurssi, joka soveltuu erityisesti algoritmien erikoistumislinjan sekä bioinformatiikan ja laskennallisen biologian suuntautumisvaihtoehdon opiskelijoille
• Esitiedot: Tietorakenteet, Ohjelmoinnin ja laskennan perusmallit
  Lisäksi hyödyllisiä: Laskennan Teoria, Algoritmien suunnittelu ja analyysi

Luennot

Juha Kärkkäinen | 31.01.-13.04. | ma, ke 12-14 | C222

Muistiinpanot

• 31.1. ja 2.2.
• 7.2. ja 9.2.
• 14.2. ja 16.2.
• 21.2. ja 23.2.
• 28.2. ja 2.3.
• 7.3. ja 9.3.
• 14.3. ja 16.3.
• 21.3. ja 23.3.
• 4.4. ja 6.4.
• 13.4.

Harjoitukset

Pasi Rastas | 07.02.-18.04. | ma 10-12 | C221
(peruutettu: Pasi Rastas | 08.02.-19.04. | ti 10-12 | DK117)

Tehtävät

• 7.1.
• 14.1.
• 21.1.
• 28.1.
• 7.3.
• 14.3.
• 21.4.
• 6.4.
• 11.4.
• 18.4.

Ohjelmointiprojekti

Ohjeita ja aiheita

Kurssikoe

to 12.05. klo 9-13 A111 ja B123

Kurssin suorittaminen

Laskuharjoitukset (10 p.) + ohjelmointiprojekti (20 p.) + koe (30 p.) = 60 p.

• Harjoituksista saatava maksimipistemäärä on 10 pistettä. Maksimipisteet saa merkitsemällä noin 80 % harjoitustehtävistä.
  Kokeeseen osallistuvan tulee merkitä vähintään 20 % harjoitustehtävistä.
• Kurssiin kuuluu pakollinen ohjelmointiprojekti.
  Ohjelmointiprojektista saatava maksimipistemäärä on 20 pistettä.
  Toteutetaan luennoituihin aiheisiin liittyvä algoritmi, suoritetaan testejä ja tuloksista kirjoitetaan posteri, joka esitellään posterinäyttelyssä. Aiheet jaetaan noin puolessa välissä kurssia.
• Kokeesta saatava maksimipistemäärä on 30 pistettä.

Kurssimateriaali:

Kurssin aikana valmistuu luentomuistiinpanot, jotka pohjautuvat varsinkin alkuosaltaan V. Mäkisen luentomuistiinpanoihin syksyn 2003 kurssilta.

Alustava sisältö

• Johdanto
• Tarkka hahmonsovitus
  • Knuth-Morris-Pratt-algoritmi
  • Boyer-Moore-algoritmi
  • Karp-Rabin-algoritmi
  • Eliminointimenetelmä
  • Shift-Or-algoritmi
  • Aho-Corasick-algoritmi
  • Hahmonsovitus äärellisen automaatin avulla
  • Hahmonsovitus jokerimerkeillä
  • Kaksiulotteinen hahmonsovitus
• Likimääräinen hahmonsovitus
  • Editointietäisyys
  • Editointietäisyyden laskeminen
  • Lävistäjämenetelmä
  • Harva dynaaminen ohjelmointi
  • Yleinen editointietäisyys
  • Lyhimmän kiertotien menetelmä
  • Hahmon likimääräisien esiintymien etsiminen
  • Myersin bitti-rinnakkainen algoritmi
  • Odotusarvoisesti tehokkaat algoritmit - seulontamenetelmät, hahmon ositus
  • Galil-Giangarlo-algoritmi k epätäsmäystä -ongelmaan
• Merkkijonojen järjestäminen ja haku
  • Radix sort
  • Multikey quicksort
  • Trie
  • Ternääripuu
  • Binäärihaku
• Loppuosarakenteet
  • Loppuosapuut ja -automaatit
  • Ukkosen "online" loppuosapuun muodostusalgoritmi
  • Loppuosataulukko
  • Loppuosien järjestämisalgoritmit
  • Loppuosarakenteiden sovelluksia

Kirjallisuutta

1. A. Aho: Algorithms for finding patterns in strings. Teoksessa Handbook of Theoretical Computer Science, Vol. A, Elsevier, 1990, 255-300.
2. T. Bell, J. Cleary, I. Witten. Text Compression. Prentice-Hall, 1990.
3. M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994.
4. M. Crochemore and W. Rytter. Jewels of Stringology. World Scientific Publishing, 2002. (KK)
5. D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
6. G. Navarro and M. Raffinot. Flexible Pattern Matching in Strings. Cambridge University Press, 2002.
7. B. Smyth. Computing Patterns in Strings. Addison Wesley, 2003.
8. G. Stephen. String Searching Algorithms. Lecture Notes Series on Computing 3, World Scientific Publishing, 1994.

Linkkejä

• Exact String Matching Algorithms: kuvauksia, koodia, java-animaatioita
• Pattern Matching Pointers: linkkikokoelma