Efektivní vyhledávání v textech

Garant předmětu:

Jan Holub

Přednášející:

Jan Holub

Cvičící:

Jan Holub

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

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.

Požadavky:

Znalosti základních datových struktur, základů programování a teorie automatů.

Osnova přednášek:

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.

Osnova cvičení:

1. Základní pojmy.

2. Úplné indexování textu

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

4. FFT ve vyhledávání

5. Succinct data structure

6. FM-Index, přibližné vyhledávání.

Cíle studia:

Vyhledávání je klíčovým úkolem v mnoha aplikacích. Jeho význam roste s rostoucím objemem získaných informací. Efektivní algoritmy a datové struktury pro vyhledávání jsou tak zásadní pro práci s informacemi, ale také v dalších oblastech, jako je počítačová bezpečnost (např. detekce vniknutí do systému, hledání virů). Tento předmět dá studentům dobrý přehled o takových algoritmech a datových strukturách.

Studijní materiály:

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

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

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

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

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/NI-EVY/

Další informace:

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

Rozvrh na zimní semestr 2023/2024:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost TH:A-s135 Holub J. 09:15–10:45 (přednášková par. 1) Thákurova 7 (budova FSv) As135
Út	místnost TH:A-1242 Holub J. 09:15–10:45 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Thákurova 7 (budova FSv) místnost TH:A-1242 Holub J. 09:15–10:45 SUDÝ TÝDEN (přednášková par. 1 paralelka 102) Thákurova 7 (budova FSv)
St
Čt
Pá

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (PS)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (VO)
• Master Specialization Digital Business Engineering, 2023 (VO)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (PS)