Jan Janoušek (FIT ČVUT), Náhled do algoritmů indexování datových struktur - popularizační přednáška

FJFI ČVUT pozýva na prednášku z cyklu fakultných kolokvií o fyzike a matematike.

Abstrakt:
Každý z nás denně využívá výsledky indexování dat, např. při vyhledávání ve vyhledávači Google nebo v různých dalších fulltextových databázích. Základním rysem indexování je, že doba vyhledávání na základě dotazu je závislá od velikostí dotazu a není tolik (dokonce někdy vůbec) závislá na množství zaindexovaných dat, ve kterých se vyhledává. V popularizační přednášce budou představeny základní principy indexování textu na úrovni vlastních algoritmů, kdy doba vyhledání výskytů vzorku závisí pouze na velikosti vzorku (a počtu jeho výskytů) a nezávisí na velikosti textu, ve kterém se vyhledává. Představíme ukázku jak tyto principy souvisí s principy jiných efektivních algoritmů pro komplikovanější úlohy zpracování textu. Dále ukážeme, jak lze podobné principy využít pro případ stromových datových struktur.