Logo ČVUT
Loading...
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2011/2012

Efektivní vyhledávání v textech

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
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
místnost T9:347
Holub J.
09:15–10:45
(přednášková par. 1)
Dejvice
NBFIT učebna
místnost T9:347
Jaroš J.
12:45–14:15
LICHÝ TÝDEN

(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
Út
St
Čt

Rozvrh na letní semestr 2011/2012:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 9. 7. 2012
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1432706.html