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

• 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

Výukové materiály

• 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)

Výukové materiály z předchozího roku

• 23-09-2020: Analýza binárních vyhledávacích stromů; cvičení: Catalanova čísla; (použité výukové materiály: pdf)
• 30-09-2020: Analýza hašovacích tabulek; dokonalé hašování, cvičení: pokračování přednášky; (použité výukové materiály: pdf)
• 07-10-2020: Opět Catalanova čísla; konstrukce optimálních vyhledávacích stromů; (použité výukové materiály: pdf)
• 14-10-2020: R-stromy (nahrazující studijní materiály: pdf; demonstrace R-stromů: linearní split, kvadratický split, bruteforce split.)
• 21-10-2020: R* a R+-stromy (nahrazující studijní materiály: pdf; demonstrace R+-stromů a R*-stromů.)
• 04-11-2020: Hiblertovy R-stromy, linearní split (nahrazující studijní materiály: pdf)
• 11-11-2020: Statické R-stromy, vyhledávání nejbližších sousedů v R-stromech (nahrazující studijní materiály: pdf, pdf)
• 18-11-2020: Metrické stromy (nahrazující studijní materiály: pdf)
• 25-11-2020: Další metrické stromy (m-stromy) (nahrazující studijní materiály: pdf)
• 02-12-2020, 09-12-2020: Pagerank, analýza AVL stromů (nahrazující studijní materiály: pdf,pdf)

Doporučená literatura

• 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.

Požadavky na zápočet

Domácí úkoly

• Úkol 1: (5+2 body): Otestovat vliv mazání na vyváženost binárního vyhledávacího stromu. Zadání na slajdech pdf. Pozor, v posledním bodě má být 100x, nikoli 200x
• Úkol 2: (5+2 body): Sestavte optimální BST a 1000uzly pro váhy p1=1000, p2=p3=...=p1000=1 a q0=q2=...=q999 = 1, q1000=500. Srovnejte jeho výkon s dokonale vyváženým BST.
• Úkol 3: (5+2 body): Porovnejte vyhledávání v setříděném poli a hašovací tabulce s dokonalým hašováním pro 4888 různých hodnot (náhodně vygenerovaných, ne 1,...,4888 apod.)
• Úkol 4 (megaúkol): Vytvořte vizualizaci kroků algoritmů B+, B*, a R stromu:
  • B-stromy (vkládání 5, vkládání s preventivními splity 5, mazání 5, výstup do tikz 5)
  • B+-stromy (vkládání 5, výstup do tikz 5)
  • B*-stromy (vkládání 5, výstup do tikz 5)
  • R-stromy (vkládání 10, mazáni 7, výstup do tikz 5)
  • splity (každý s výstupem do tikz 5)
  • vše +40% bodů, pokud to budu chtít použít.
• Úkol 5: Vytvořte vizualizaci kroků algoritmů R+, R*, a Hilbertova stromu:
  • R+-stromy (vkládání 10, výstup do tikz 5)
  • R*-stromy (vkládání 5, výstup do tikz 5)
  • Hilberovy R-stromy (vkládání 10, výstup do tikz 5)
  vše +40% bodů, pokud to budu chtít použít.
• Úkol 6: Vytvořte vizualizaci kroků algoritmů statických R-stromů (každý 5) +40% bodů, pokud to budu chtít použít.
• Úkol 7: Vytvořte vizualizaci kroků algoritmů NN R-stromů (každý 7, vystup do tikz 5) +40% bodů, pokud to budu chtít použít.
• Úkol 8: Vytvořte vizualizaci vp-stromů (5 bodů), MVP-stromů (10 bodů), m-stromů (10 bodů)
• Úkol 9: Implementujte Pagerank (výpočet z matice Q) (5 bodů)
• Úkol 10: Implementujte výpočet SVD (15 bodů)