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

• 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.
• Maticové metody ve vyhledávání.
• Vyhledávání v internetu, PageRank algoritmus.

Rozvrh předmětu

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.

Zápočtové úkoly

• Experimentálně prozkoumat vliv mazání v RBBST,
• Experimentálně dokonalé hašování s vyhledáváním v setřízeném poli (nebo ve vyváženém BSL),
• AVL stromy -- rekonstruovat poslední tabulku na slajdech,
• Demonstrační program pro R-stromy,
• Najít bijekci mezi BST a jinou sémantikou Catalanových čísel,
• Naprogramovat Pagerank.

Slajdy

• 30.9. složitost vyhledávání v BST v průměrném případě, průměrná výška BST, konstrukce vyváženého BST (pdf)
• 11.11. Catalanova čísla (pdf)
• ... zbytek doplnim

Zkouška

Požadavky na zápočet