58093-3 Merkkijonomenetelmät (6 op), kevät 2007, periodi III

Kurssilla tutustutaan merkkijonojen käsittelyssä tarvittaviin algoritmeihin ja tietorakenteisiin. Tarkasteltavia ongelmia ovat mm. merkkijonohahmon tarkan tai likimääräisen esiintymän etsiminen tekstistä, merkkijonojoukon järjestäminen ja toistuvien osajonojen etsiminen merkkijonoista.

Ajankohtaista

• Tulokset (Intranet).
• Ohjelmointiprojektin pisteet muille kuin kokeessa hyväksytyille (Intranet).
  Ohjelmointiprojektin suorittaneet voivat suorittaa kurssin erilliskokeella, joista ensimmäinen on ti 5.6. klo 16-20 salissa A111.
• Ohjelmointiprojektisivulla on tarkennettu aikataulu ja uusia ohjeita testauksesta.
• Kokeen tulokset ja laskareista saatavat pisteet (Intranet).
  
• Tehtyjen laskarien erittely (Intranet)
• Koetta (to 1.3. klo 16-19 A111) varten voi harjoitella tekemällä lisätehtäviä. Mukana on tärppejä.
• Ohjelmointiprojektin ohjeita ja aiheita on nyt nähtävillä. Aiheita tulee vielä myöhemmin lisää. Aihe on valittava viimeistään laskareissa 9.2.

Asema opetuksessa

• Valinnainen laudatur-kurssi, joka soveltuu erityisesti algoritmien erikoistumislinjan sekä bioinformatiikan ja laskennallisen biologian suuntautumisvaihtoehdon opiskelijoille.
• Soveltuu algoritmien erikoistumislinjan pakolliseksi syventäväksi kurssiksi. Kurssin laajuus on supistunut 8 op:stä 6 op:een, mutta "puuttuvat" 2 op:tä voi korvata valinnaisilla linjakohtaisilla kursseilla.
• Esitiedot: Tietorakenteet, Laskennan mallit (tai sen edeltäjä Ohjelmoinnin ja laskennan perusmallit)
  Lisäksi hyödyllisiä: Algoritmien suunnittelu (ja analyysi), Laskennan Vaativuus (tai sen edeltäjä Laskennan Teoria)

Luennot

Juha Kärkkäinen | 16.01.-22.02. | ti 12-14 C222, to 14-16 B222

Muistiinpanot

• 16.1. ja 18.1.
• 23.1. ja 25.1.
• 30.1. ja 1.2.
• 6.2. ja 8.2.
• 13.2. ja 15.2.
• 20.2. ja 22.2.

Harjoitukset

Jarkko Toivonen | 26.01.-23.02. | pe 10-12 CK107

Tehtävät

• 26.1.
• 2.2.
• 9.2.
• 16.2.
• 23.2.

Kurssikoe

to 1.3. klo 16-19 A111

Ohjelmointiprojekti

Kurssiin kuuluu ohjelmointiprojekti.

• Toteutetaan luentojen aihepiiriin liittyvä algoritmi, suoritetaan testejä ja tuloksista tehdään posteri, joka esitellään posterinäyttelyssä.
• Aiheiden valinta: 09.02. mennessä
• Projektisuunnitelman palautus: 23.02.
• Projekti jatkuu itsenäisenä työskentelynä periodin IV aikana sen noin 5. viikolle, jolloin tulokset esitetään posterina (19.04.).

Ohjeita ja aiheita

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ä.
• Kokeesta saatava maksimipistemäärä on 30 pistettä.

Tai erilliskoe (40 p.) + ohjelmointiprojekti (20 p.) = 60 p.

• Ohjelmointiprojekti vaaditaan myös erilliskokeeseen osallistuvilta.

Kurssimateriaali:

Kurssin aikana valmistuu luentomuistiinpanot, jotka pohjautuvat kevään 2005 kurssin muistiipanoihin.

Alustava sisältö

• Johdanto
• Tarkka hahmonsovitus
  • Knuth-Morris-Pratt-algoritmi
  • Boyer-Moore-algoritmi
  • Karp-Rabin-algoritmi
  • Eliminointimenetelmä
  • Shift-Or-algoritmi
  • Aho-Corasick-algoritmi
• Likimääräinen hahmonsovitus
  • Editointietäisyys
  • Editointietäisyyden laskeminen
  • Hahmon likimääräisien esiintymien etsiminen
• Merkkijonojen järjestäminen ja haku
  • Radix sort
  • Multikey quicksort
  • Trie
  • Ternääripuu
  • Binäärihaku
• Loppuosarakenteet
  • Loppuosapuut ja -automaatit
  • 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. M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994.
3. M. Crochemore and W. Rytter. Jewels of Stringology. World Scientific Publishing, 2002. (KK)
4. D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
5. G. Navarro and M. Raffinot. Flexible Pattern Matching in Strings. Cambridge University Press, 2002.
6. B. Smyth. Computing Patterns in Strings. Addison Wesley, 2003.
7. 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

---

Juha Kärkkäinen