Jan Konečný - Výuka - KMI/ALS1 Algoritmy a složitost 1

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: středa: 8:00 - 9:30
Cvičení: středa: 9:45 - 11:15

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 ISBN 1-85233-977-.
Skiena S. S. The Algorithms Design Manual. Springer, New York, 1998. ISBN 0-387-94860-0.

Slajdy z přednášek

20.9.2017 -- Intro a BST L1.pdf
27.9.2017 -- Catalanova čísla, optimální stromy L2.pdf
4.10.2017 -- Hašování L3.pdf
11.10.2017 -- AVL stromy L4.pdf
18.10.2017 -- Pagerank L5.pdf
25.10.2017 -- R-tree L6.pdf, demonstrace R-stromů: linearní split, kvadratický split, bruteforce split.
1.11.2017 -- Varianty R-stromů: R+,R* L7.pdf, demonstrace R+-stromů a R*-stromů.
8.11.2017 -- Další Varianty R-stromů zdroj a kd-stromy kd.pdf.
15.11.2017 -- Metrické stromy L9.pdf.
22.11.2017 -- Metrické stromy podruhé (BK-tree, m-tree).
29.11. a 6.12.2017 -- SVD LA.pdf LB.pdf .

Úkoly

viz L1.pdf

Popište bijekci mezi mezi korektně uzávorkovanými výrazy (popř. pohořími nebo naddiagonálními cestami v mřížce) a binarními vyhledavacími stromy (popř. handshaky nebo triangulacemi polygonu); viz L2.pdf

Naprogramujte dokonale hašování pro 4888 hodnot, experimentálně porovnejte rychlost vyhledávání s vyhledáváním v setřízeném poli.L3.pdf (10b)

Rekonstuujte tabulku ze slajdu 32 L4.pdf (10b)

Naprogramujte výpočet rankingu z původní matice P (viz poslední slajd; pro test použijte první matici ze slajdů) L5.pdf (5b + 5b při použití efektivní reprezentace řídkých matic)

Naprogramujte grafickou demonstraci R-stromu (10b)

Navrhněte algoritmus na výpočet Hilbertovy hodnoty (10b)

Naprogramujte grafickou demonstraci vp-stromu (10b)

Studijní materiály

Zkouška

ústní formou.

Požadavky na zápočet

domácí úkoly.