Efektivní vyhledávání v textech
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
MI-EVY | Z,ZK | 4 | 2+1 | česky |
- Přednášející:
- Jan Holub (gar.)
- Cvičící:
- Jakub Jaroš
- 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:
- Osnova přednášek:
-
1. Úvod, základní definice.
2. Border array a přesné vyhledávání.
3. Algoritmy přesného vyhledávání.
4. FFT ve vyhledávání.
5. Úplné indexování textu: Suffix array.
6. Úplné indexování textu: Suffix tree, konstrukce LCP.
7. Úplné indexování textu: factor, suffix automata, on-line konstrukce.
8. Succinct data structure: metody rank & select.
9. Succinct data structure: wavelet tree.
10. FM-Index.
11. Reprezentace slovníku, kontrola pravopisu.
12. Přibližné vyhledávání.
13. Vyhledávání v bioinformatice a v muzikologii.
- Osnova cvičení:
-
1. bude brzy doplněno
- 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:
-
Crochemore, C., Rytter, W. ''Jewels of Stringology''. World Scientific Publishing Company, 2003. ISBN 9810248970.
Navarro, G., Raffinot, M. ''Flexible Pattern Matching in Strings''. Cambridge University Press, 2008. ISBN 0521039932.
- Poznámka:
-
Rozsah=prednasky+proseminare+cviceni2p+1c, Prednasejici: doc. Ing. Jan Holub Ph.D.
- Rozvrh na zimní semestr 2011/2012:
-
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 Út St Čt Pá - Rozvrh na letní semestr 2011/2012:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Zaměření Systémové programování - verze pro ty, kteří se zapsali v roce 2010 (povinný předmět zaměření)
- Zaměření Systémové programování - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět zaměření)
- Zaměření Systémové programování - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět zaměření)