Jan Konečný - Výuka - KMI/ALS1 Algoritmy pro rozsáhlá data

Předmět pojednává o vybraných pokročilých algoritmech, zejm. algoritmech vyhledávání.

Pokročilé stromové struktury: vyvážené stromy, B-stromy, tries, R-stromy a jejich varianty, metrické stromy.
Hashování, analýza a pokročilé partie.
Vyhledávání v internetu, PageRank algoritmus.

Rozvrh předmětu

Přednáška: čtvrtek: 13:15 - 14:45
Cvičení: čtvrtek: 15:00 - 16:30

1. Experimentálně vychodnoďte vliv mazání na výšku (popř. očekávaný čas vyhledávání v) BST.
2. Prozkoumejte hašování ve svém oblíbeném prog. jazyce, najděte kolidující sadu klíčů.
3. Experimentálně porovnejte Bloomův filtr a podílový filtr.
4. Implementujte struktury z lekcí L06, L07, (kromě B-stromu) Mějte k tomu nějaký grafický výstup (pro ověření správnosti). Každá struktura se počítá jako jeden úkol.
5. Implementujte Hilbertův R-strom. Mějte k tomu nějaký grafický výstup (pro ověření správnosti).
6. Soubor demoRtreeLinear.pdf v (souboru k L07) obsahuje chybu, (pickSeeds vybere menší normalizovanou separaci, ne větší) Za vytvoření ekvivalentního souboru (s opravenou chybou) nabízím zápočet (tj. nejen jeden splněný úkol).
7. Implementujte struktury MVP-strom. Mějte k tomu nějaký grafický výstup (pro ověření správnosti)

23-09-2021: Analýza binárních vyhledávacích stromů; cvičení: Catalanova čísla; (použité výukové materiály: pdf)
30-09-2021: Optimální BST; Analýza hašování; cvičení: Catalanova čísla; (použité výukové materiály: pdf, pdf)
14-10-2021: Univerzální hašování, dokonalé hašování; cvičení: řídké matice a dokonalé hašování; (použité výukové materiály: pdf, pdf)
04-11-2021: B-stromy a jejich varianty, R-stromy; (použité výukové materiály: pdf; demonstrace R-stromů: linearní split, kvadratický split, bruteforce split.)
11-11-2021: R+-stromy, R*-stromy, Hilbertovy R-stromy; (použité výukové materiály: pdf, kd-stromy pdf, demonstrace R+-stromů a R*-stromů.)
18-11-2021: Statické R-stromy, topologické dotazy, dotazy na nejbližšího souseda. (použité výukové materiály: pdf)
25-11-2021: Metrické stromy (použité výukové materiály: pdf)
02-12-2021: Pagerank (použité výukové materiály: pdf)
09-12-2021: SVD (použité výukové materiály: pdf)

Knuth D. The Art of Computer Programming, Volume 3: Sorting and Searching. Second Edition. Reading, Massachusetts: Addison-Wesley, 1998. ISBN 0-201-89685-0
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. Second Edition. MIT Press, 2001. ISBN 0-262-53196-8.
Levitin A. Introduction to the Design and Analysis of Algorithms. Addison Wesley, 2003. ISBN 321-21076-X.
Manolopoulos Y., et al. R-Trees: Theories and Applications. Springer, 2005. ISBN 1-85233-977-.
Skiena S. S. The Algorithms Design Manual. Springer, New York, 1998. ISBN 0-387-94860-0.

Vypracování 5 domácích úkolů