Merkkijonoalgoritmit-seminaari (2-3 ov) L

Ohjelma

Yleistä

Seminaari on luonteeltaan opintoseminaari.

Merkkijonomenetelmät on algoritmitutkimuksen erikoisala, jonka tyypillisiä tutkimuskohteita ovat:

• merkkijonohahmon etsintä tekstistä (tarkka/likimääräinen)
• merkkijonojen talletusrakenteet, indeksointi
• tiedonhaku (information retrieval)
• tekstin tiivistäminen

Seminaarissa paneudutaan uusimpiin merkkijonoalgoritmeihin.

Esitiedot: T-106.410 tai vastaavat tiedot.

Hallinnollinen nimi: T-106.850 Ohjelmistotekniikan seminaari

Opettaja: prof. Jorma Tarhio

Ilmoittautuminen: Lähetä sähköpostia opettajalle jorma.tarhio@hut.fi. Kerro nimesi, opiskelijanumerosi ja pääaineesi.

Kieli: Esitelmä voidaan pitää suomeksi tai englanniksi.

Osallistujat

Ohjeita

• Hyväksytty suoritus
  • Esitelmä
  • Kirjallinen esitys
  • Lyhennelmä
  • Opponointi
  • Läsnäolo vähintään 70%
  • Osallistuminen keskusteluun
• Esitelmä
  • Pituus 60-80 min
• Kirjallinen esitys
  • Verkkosivu html- tai pdf-muodossa (tekstinä 8-12 sivua)
  • Lähetä URL opettajalle n. viikkoa ennen esitelmää (vaikka sivu olisikin vielä keskeneräinen).
  • Tekstin tulisi olla valmis esitelmää edeltävänä perjantaina klo 12.
• Lyhennelmä
  • Pituus 1-3 sivua
  • Jaetaan monistettuna (n+2 kpl) esitelmän yhteydessä (n = osallistujien määrä).
• Laajuus
  • 1 esitelmä ym. + 1 opponointi = 2 ov
  • 2 esitelmää ym. + 2 opponointia = 3 ov

Aiheita

Hyökkäyksen havaitseminen

J. Kuri, G. Navarro: Fast Multipattern Search Algorithms for Intrusion Detection. In Proc. SPIRE'2000, pages 169-180, 2000.

FM-indeksi

P. Ferragina, G. Manzini: An experimental study of an opportunistic index. In Proc. 12th ACM Symp. on Discrete Algorithms (SODA'01), pages 269-278, 2001.

Säännöllisen lausekkeen täsmäys

G. Navarro, M. Raffinot: Flexible Pattern Matching in Strings. Cambridge University Press, 2002.

Episoditäsmäys

G. Das, R. Fleischer, L. Gasieniec, D. Gunopulos, J. Kärkkäinen. Episode matching. In Proc. CPM'97, LNCS 1264, Springer, pp. 12-27, 1997.
H. Mannila, H. Toivonen, A. I. Verkamo. Discovering frequent episodes in sequences. In Proc. KDD'95, AAAI Press, pp. 210-215, 1995.

Googlen sivunrankkausmenetelmä

L. Pretto: A Theoretical Analysis of Google's PageRank. SPIRE 2002: 131-144.
L. Page, S. Brin, R. Motwani, T. Winograd: The PageRank citation ranking: Bringing order to the web. Stanford Digital Libraries Working Paper, 1998.

Tiedon klusterointi

A.K. Jian, M.N. Murty, and P.J. Flynn. Data clustering: A review. ACM Computing Surveys, vol 31, no. 3, September 1999.