Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

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

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.
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 2007 kurssin muistiipanoihin.

Alustava sisältö

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ä


Juha Kärkkäinen
Last modified: Fri Dec 5 19:14:35 EET 2008