PředmětyPředměty(verze: 948)
Předmět, akademický rok 2023/2024
  
Efektivní vyhledávání v textech - N500001
Anglický název: Efficient Text Pattern Matching
Zajišťuje: ČVUT v Praze, Fakulta informačních technologií (500)
Fakulta: Vysoká škola chemicko-technologická v Praze
Platnost: od 2021
Semestr: zimní
Body: zimní s.:4
E-Kredity: zimní s.:4
Způsob provedení zkoušky: zimní s.:
Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
Počet míst: neurčen / neurčen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Úroveň:  
Je zajišťováno předmětem: M500001
Pro druh:  
Garant: Holub Jan prof. Ing. Ph.D.
Je záměnnost pro: M500001
Termíny zkoušek   Rozvrh   
Anotace -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
Studenti získají znalosti efektivních algoritmů vyhledávání v textových informacích. Naučí se pracovat s tzv. zhuštěnými datovými strukturami, které vynikají jak rychlostí přístupu tak úsporou místa v paměti. Získané znalosti budou schopni uplatnit při návrhu aplikací zabývajících se vyhledáváním v textu.
Výstupy studia předmětu -
Poslední úprava: Jirát Jiří Ing. Ph.D. (13.01.2014)

Studenti budou umět:

budou mít znalosti efektivních algoritmů vyhledávání v textových informacích.

pracovat s tzv. zhuštěnými datovými strukturami, které vynikají jak rychlostí přístupu tak úsporou místa v paměti.

uplatnit získané znalosti při návrhu aplikací zabývajících se vyhledáváním v textu.

Literatura -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)

Z:W.F. Smyth: ''Computing Patterns in Strings'', Pearson Addison Wesley (UK), 2003, 423 pp. ISBN-10: 0201398397

Z:M.Crochemore, W. Rytter: ''Jewels of Stringology''. World Scientific Publishing Company, 2003. ISBN-10: 9810248970.

Z:G.Navarro, M. Raffinot: ''Flexible Pattern Matching in Strings''. Cambridge University Press, 2008. ISBN-10: 0521039932.

Z:M.Crochemore, C. Hancart, T. Lecroq: ''Algorithms on Strings''. Cambridge University Press, 2007. ISBN-10: 0521848997

Studijní opory -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)

https://edux.fit.cvut.cz/courses/MI-EVY/

(nutné přihlášení)

Sylabus -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)

1. Úvod, základní definice, border array.

2. Úplné indexování textu: Suffix array.

3. Úplné indexování textu: Suffix tree, konstrukce LCP.

4. Úplné indexování textu: factor, suffix automata, on-line konstrukce.

5. Algoritmy přesného vyhledávání.

6. FFT ve vyhledávání.

7. Succinct data structure: metody rank & select.

8. Succinct data structure: wavelet tree.

9. FM-Index.

10. Reprezentace slovníku, kontrola pravopisu.

11. Přibližné vyhledávání.

12. Vyhledávání v bioinformatice a v muzikologii.

13. Vyhledávání v bioinformatice a v muzikologii.

Studijní prerekvizity -
Poslední úprava: Jirát Jiří Ing. Ph.D. (31.01.2014)

Znalosti konečných automatů a složitosti.

Zátěž studenta
Činnost Kredity Hodiny
Účast na přednáškách 1 28
Práce na individuálním projektu 2.2 61
Účast na seminářích 0.5 14
4 / 4 103 / 112
 
VŠCHT Praha