Eesti keeles:   Tekstialgoritmid I
Inglise keeles: Text algorithms I
Kood: MTAT.03.165

Maht: 2 ap

Loengud ja praktikumid - Jaak Vilo
Toimumine: 2002/2003 kevadsemester
(Eeldatavasti kolmapäeviti, kell 14-16 ja praktikumid kell 16-18)

Loeng: 18 t
Praktikum: 16 t
Iseseisev töö 46 t.
Hindamine: eksam

Eeldusaine: MTAT.03.003 "Algoritmid ja andmestruktuurid"

Kursuse käigus tutvustatakse sõnede täpse ja ligikaudse otsimise
algoritme, tekstide indekseerimise meetodeid, andmete pakkimise
meetodeid, andmetes mustrite tuvastamist, tekstide
kaevandamist ja tekstinfo otsinguid.



Loeng on tunniplaanis K. 14-16 L207.
Kui SUN klass sobib, siis saab praxi teha K 16-18 L203.



----------------------------------------------------------------------

Täpsustatud teemade loetelu (esialgne)

18 t = 9 nädalat

Nädal 1: 
   * Täpne otsimine
	- Triviaalne algoritm O(nm)
	- Knuth-Morris-Pratt O(m+n)
	- Boyer-Moore 
	- Rabin-Karp
	- Aho-Corasick (mitme sõne otsimine)

Nädal 2: 
	- Lõplikud automaadid ja regulaaravaldised 
	- Regulaaravaldiste otsimine

Nädal 3:
    * Ligikaudne otsimine
	- Stringide vahelise kauguse mõõdud
	- Dünaamiline programmeerimine
	- Otsimine pikast tekstist

Nädal 4:
	- Diagonaali meetod
	- q-gram meetodid - "filtreeri ja otsi"
	- Bitiparalleelsus - Shift/OR meetod
	- Aja painutamine - time warping
	- DNA- ja valkude kauguse mõõdud

Nädal 5:
    * Staatiliste tekstide indekseerimine
	- Sufiksi-puud
	- Sufiksi-massiivid

Nädal 6:
	- PAT-indeks ja OED projekt
	- Modernsed andmestruktuurid
	- Tekstinfo otsimine 
	- Tekstide kaevandamine

Nädal 7:
    * Tekstide pakkimine
	- Lempel-Ziv
	- Aritmeetiline kodeerimine

Nädal 8:
    * Probabilistlikud motiivid (Position Weight Matrices)
	- Informatsiooni sisaldus
	- Sequence logo
	- PWM otsimine

    * Stohhastilised grammatikad
	- HMM - Hidden Markov Models
	- SCFG - Stochastic Context Free Grammars

Nädal 9 
    * Mustrite tuvastamine (Pattern Discovery)
	- Mustrite tuvastamise põhimõisted
	- Erinevad mustrite klassid
	- Gibbs Sampling
	- Expectation Maximization

----------------------------------------------------------------------
Kirjanduse loetelu:

Gusfield, Dan: Algorithms on Strings, Trees, and Sequences (Cambridge
University Press, 1997)

Cormen, T.H., Leiserson, C.E., Rivest, R.L. Introduction to Algorithms
(MIT Press 1990), Chapter 34 (String Matching).

Pevzner, P.A. Computational Molecular Biology - An Algorithmic Approach
(MIT Press, 2000)

Baldi, Pierre, and Brunak, Soren, Bioinformatics - the Machine Learning
Approach 2nd edition, (MIT Press, 2001)

Durbin, R., Eddy, S., Krogh, A., Mitchison - Biological sequence
analysis - Probabilistic models of proteins and nucleic acids (Cambridge
University Press, 1998)

Jorma Tarhio, Merkkijonomenetelmät (luentomoniste) ~ 1995 University of
Helsinki

jt.