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.

Studijní materiály

• L1 -- přednáška 22.9. (update 23.9.: oprava indexů, doplnění info harmonických číslech, oprava drobných typografických chyb; upload 17.9.2015)
• L2 -- přednáška 29.9. (update 23.9.: typografické úpravy; upload 24.9.2015)
• L3 -- přednáška 6.10. (update 18.10.: neprobraná část odstraněna a přesunuta do L4; update 5.10.: doplnění specifikace vyvažovacích cest, srovnání názvosloví s předchozími lekcemi, doplnění chybejicího kroku A1 v algoritmu, oprava chyb; upload 3.10.2015)
• L4 -- přednáška 20.10. (update 20.10.2015: opravy drobných chyb ;update 20.10.2015: úprava pseudokódu A, přidány B,C, a obrázek specifikace externích uzlů; upload: 18.10.2015)
  L4a -- dodatečný materiál k přednášce 20.10. (update 18.10.2015: přesunuto z L3 k L4; upload 6.10.2015)
• L5a -- dodatečný materiál k přednášce 27.10. (upload 23.10.2015)
• L6 -- přednáška 3.11. (update 25.11.2015: spellcheck; update 7.11.2015: přidány podprostory, prídána aproximace matic, výpočet přesunut do L7, opravy drobných chyb, upload 30.10.2015)
• L7 -- přednáška 10.11. (update 25.11.2015: spellcheck; update 24.11.2015: doplnění Householderva reflektoru; upload 7.11.2015)
  L7a -- dodatečný materiál k přednášce 10.11. (bidiagonalizace) (upload 23.11.2015)
  L7b -- dodatečný materiál k přednášce 10.11. (QR-rozklad 3diagonální symetrické matice pomocí rotací) (upload 26.11.2015)
  L7c -- dodatečný materiál k přednášce 10.11. (QR-algoritmus) (upload 26.11.2015)
• L8 -- přednáška 24.11. (update 25.11.2015: přidán obrázek, spellcheck; upload 14.11.2015)
  L8a -- dodatečný materiál k přednášce 24.11. (upload 14.11.2015)
• L9 -- přednáška 1.12. (upload 30.11.2015)
  
• LA -- přednáška 8.12. (upload 11.12.2015)
  
• další budou průběžně doplněny.

Zápočtové úkoly

• Vytvořte dokonalé hašování pro 4888 klíčů a porovnejte rychlost vyhledávání s vyhledáváním v uspořádaném poli (motivace Cactus Kev’s Poker Hand Evaluator).
• Naprogramujte vkládání do AVL stromu a ověřte hodnoty v tabulce v L4, str. 4 (zrekonstuujte tabulku).
• Naprogramujte výpočet Pageranku z matice Q (podle L5a, str 29).
• Naprogramujte Householderovu bidiagonalizaci.
• Naprogramujte demonstraci R-stromu (2d), s kvadratickým splitem -- udělejte grafický výstup zobrazující rozložení obdélníků.
• další budou doplněny.

Zkouška

Požadavky na zápočet