58093-3 Merkkijonomenetelmät (6 op), syksy 2008, periodi I
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.-
Uutisia
- Kurssin tulokset (intranet).
- Ohjelmointiprojektin posteriesittely on 26.11. klo 8.30-12.00
salissa C222.
Ohjausta posterin tekoon järjestetään viikkoa aikaisemmin 19.11. klo 10-12 salissa C222. Tällöin on myös nähtävillä aikaisempien vuosien postereita. - Kurssikokeen tulokset ja laskuharjoituspisteet (intranet). Jos haluat tutustua arvosteluun, ota yhteyttä Juha Kärkkäiseen 27.-31.10. tai Jarkko Toivoseen sen jälkeen.
- Ohjelmointiprojektin ohjeisiin
on tullut täydennyksiä:
- Suunnitelma tehdään www-sivuna, joka tulee muiden kurssilaisten nähtäville, ja jota myöhemmin täydennetään toteutuksen dokumentaatioksi.
- Arvosteluperusteita on täydennetty.
- Ohjelmointiprojektin ohjeita ja aiheita on nyt nähtävillä.
Asema opetuksessa
- Valinnainen laudatur-kurssi, joka soveltuu erityisesti algoritmien (ja koneoppimisen) erikoistumislinjan sekä bioinformatiikan opiskelijoille.
- Soveltuu algoritmien erikoistumislinjan pakolliseksi syventäväksi kurssiksi (2005-2008 tutkintovaatimukset). 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, Laskennan vaativuus - Periodin II kurssilla Tiedon tiivistämisen tekniikat käytetään tämän kurssin tekniikoita.
Luennot
- Juha Kärkkäinen
| 02.09.-09.10. | ti, to 12-14 B222
- Luennot ti 16.9., to 18.9. ja ti 23.9. peruutettu.
- Korvaavat luennot ma 8.9., ma 15.9. ja ma 29.9. 12-14 B222
Luentomuistiinpanot
-
Harjoitukset
-
Jarkko Toivonen | 09.09.-07.10. | ti 10-12 CK111
Tehtävät
-
Kurssikoe
- ke 15.10. klo 9-12 A111, B123
-
Ohjelmointiprojekti
- Kurssiin kuuluu ohjelmointiprojekti.
- Toteutetaan luentojen aihepiiriin liittyvä algoritmi, suoritetaan testejä ja tuloksista tehdään posteri, joka esitellään posterinäyttelyssä.
- Aiheiden valinta: 30.09. mennessä
- Projektisuunnitelman palautus: 10.10. mennessä
- Projekti jatkuu itsenäisenä työskentelynä periodin II aikana sen noin 5. viikolle, jolloin tulokset esitetään posterina.
-
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 2007 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
- A. Aho: Algorithms for finding patterns in strings. Teoksessa Handbook of Theoretical Computer Science, Vol. A, Elsevier, 1990, 255-300.
- M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994.
- M. Crochemore and W. Rytter. Jewels of Stringology. World Scientific Publishing, 2002. (KK)
- D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
- G. Navarro and M. Raffinot. Flexible Pattern Matching in Strings. Cambridge University Press, 2002.
- B. Smyth. Computing Patterns in Strings. Addison Wesley, 2003.
- 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