58093-3 Merkkijonomenetelmät (4 ov), syksy 2003

Asema opetuksessa

Valinnainen laudatur-kurssi.

Esitiedot

Tietorakenteet, Ohjelmoinnin ja laskennan perusmallit

Ajankohtaista

• Koe tiistaina 9.12 klo 16-20 AUDITORIO.
• Kurssin tulokset. Koetehtävien ratkaisuideoita löytyy tästä.
• Ne jotka aikovat suorittaa kurssin erilliskokeella voivat tiedustella laskuharjoitus-/harjoitustyöpisteitänsä allekirjoittaneelta sähköpostitse. Erilliskokeen perusteella arvosana määräytyy koe+harjoitustyöpisteistä. Haluttaessa laskuharjoituspisteet otetaan huomioon.
• Erilliskokeita keväällä 2004: pe 16.1 ja ti 23.3.

Luennot

Veli Mäkinen | 16.9.-2.12. | ti 10-12, to 10-12 | sali A414

Kalvot

• 16.-18.9 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 25.9 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 30.9-2.10 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 7.-9.10 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 14.-16.10 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 21.-23.10 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 28.-30.10 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 4.-6.11 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 11.-13.11 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 18.-20.11 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 25.11-27.11 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)
• 2.12 (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)

• Koko kurssin kalvot (1 sivu/arkki) (2 sivua/arkki) (4 sivua/arkki)

Harjoitukset

Veli Mäkinen | 25.9.-4.12. | to 8.30-10 | sali A319
Anna Pienimäki | 25.9.-4.12. | pe 8.30-10 | sali B453

Laskuharjoitustehtävät:

• Harjoitus 1 (malliratkaisut)
• Harjoitus 2 (malliratkaisut)
• Harjoitus 3 (malliratkaisut)
• Harjoitus 4 (malliratkaisut)
• Harjoitus 5 (malliratkaisut)
• Harjoitus 6 (malliratkaisut)
• Harjoitus 7 (malliratkaisut)
• Harjoitus 8 (malliratkaisut)
• Harjoitus 9 (malliratkaisut)
• Harjoitus 10 (malliratkaisut)
• Lisätehtäviä (malliratkaisut)

Ohjelmointiprojekti

Kurssikoe:

ti 9.12. klo 16-20 AUDITORIO

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 aikaisempiin J. Tarhion, E. Ukkosen ja T. Hegedüksen laatimiin muistiinpanoihin sekä kirjallisuusluetteloissa mainittuihin kirjoihin. Suurin osa luennoitavista asioista löytyy kirjasta [4] (kirjaa saa www.amazon.com:sta hintaan 25 euroa).

Sisältö

• Johdanto
• Tarkka hahmonsovitus
  • Knuth-Morris-Pratt-algoritmi
  • Boyer-Moore-algoritmi
  • Rabin-Karp-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
• Hahmonsovitus staattisissa jonoissa
  • Loppuosapuut ja -automaatit
  • Ukkosen "online" loppuosapuun muodostusalgoritmi
  • Loppuosataulukko
  • Loppuosien järjestämisalgoritmit
  • Loppuosarakenteiden sovellukset: O(kn)-algoritmi k virhettä -ongelmaan
• Tiedon tiivistäminen
  • Entropia
  • Huffman-koodaus
  • Aritmeettinen koodaus
  • Ziv-Lempel-menetelmät
  • Burrows-Wheeler-menetelmä
  • Tietorakenteiden tiivistys - tiiviit loppuosarakenteet

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.