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: úterý: 12:15 - 13:45
Cvičení: úterý: 16:45 - 18: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.

Studijní materiály

L1 Hašování

L1s Hašování

L2 Dokonalé hašování, BST

L2s BST + Optimalní stromy

L3 Catalanova čísla, vyvážené stromy

L4 AVL stromy

L4 Pagerank

L5 R-stromy

L6 Varianty R-stromů

demonstrace vkládání do R-stromu, m=2,M=5, lineární split

demonstrace vkládání do R-stromu, m=2,M=5, kvadratický split

demonstrace vkládání do R-stromu, m=2,M=5, bruteforce split

demonstrace vkládání do R*-stromu, m=2,M=5,p=2, bez optimalizace ChooseSubtree (nutno upravit, nepokouší se o reinsert na nelistových úrovních).

demonstrace vkládání do R+-stromu, m=2,M=5.

Metrické stromy.

Zkouška

ústní formou.

Požadavky na zápočet

domácí úkoly; první bude zadán už na prvním cvičení.

Zápočtové úkoly

1] Vypočítejte dokonalou hašovací funkci pro 4888 různých číselných hodnot
(náhodně vygenerovaných; nechte si prostor aby bylo možné najít vyšší pročíslo).
  Proveďte rychlostní srovnání s vyhledáváním v setřízeném poli.

2] Sestavte optimální strom pro klíče s vahami.
P = (5 1 2 0 4 3 2 2 2 3 4 0 3 3 3 3 2 4 2 1 5 3 3 4 2 5 3 0 4 4 0 3 1 1 2 0 3 1
     5 1 2 3 0 1 3 4 0 3 5 2 5 0 0 0 2 2 3 2 4 0 3 1 3 5 1 0 4 0 1 3 5 3 4 0 5 3 
     3 0 4 2 5 4 4 1 1 0 0 2 2 4 3 2 2 0 5 1 0 0 0 1 0 1 1 1 3 4 1 1 2 2 5 4 2 3
     5 3 3 4 2 0 4 0 2 3 0 4 5 3 3 4 4 2 0 1 3 0 1 0 4 3 4 4 2 2 3 4 5 0 3 0 3 3
     4 5 2 1 2 4 3 5 1 5 5 0 3 0 4 0 3 2 3 1 2 3 1 4 1 5 1 0 3 0 2 5 3 1 0 4 3 4
     1 3 0 0 5 0 5 3 1 5 4 1 3 3 3 5 3 2 3 1 0 1 1 0 4 5 5 5 3 5 1 1 2 0 4 4 5 0
     0 1 3 2 2 0 4 1 2 3 2 0 5 1 2 5 2 5 0 4 3 5 5 3 2 2 0 3 3 1 4 1 0 4 3 0 1 3
     0 2 3 5 3 2 2 4 4 3 4 0 1 1 0 4 1 1 1 5 2 1 1 1 4 0 1 3 1 3 0 3 5 3 0 5 4 5
     3 4 3 3 5 5 4 2 5 5 0 5 0 1 400 3 3 1 0 5 2 0 1 1 2 0 1 5 0 5 2 3 0 1 0 5 3 5
     4 4 5 0 0 5 1 4 1 5 5 4 5 5 3 1 0 4 4 3 4 2 3 0 3 4 0 5 5 2 2 4 2 0 4 4 1 3
     2 1 0 4 4 3 2 2 2 0 4 1 5 4 5 1 2 0 5 4 4 0 4 0 2 5 3 2 2 1 5 3 0 2 5 2 2 1
     4 2 3 3 4 3 5 0 2 0 1 3 0 0 2 2 5 1 2 3 0 5 3 0 4 3 1 5 2 3 5 3 2 1 2 4 4 2
     0 5 3 1 0 2 1 4 5 1 3 3 4 4 5 0 1 4 4 5 2 1 1 0 1 3 2 3 2 1 0 1 0 4 5 1 4 4
     3 1 2 1 0 1 3 4 5 4 5 3 5 0 5 2 1 5 1 0 1 0 5 1 0 3 4 3 5 1 3 5 5 3 1 4 2 0
     3 1 0 4 2 4 2 0 1 1 3 2 2 0 5 1 2 0 5 2 4 3 3 1 0 4 3 5 3 2 5 3 2 2 3 2 1 5
     0 3 0 2 0 1 2 4 4 5 3 0 0 1 4 5 0 3 2 1 4 5 1 0 4 1 5 2 3 2 3 5 1 3 5 2 5 1
     2 1 3 0 4 3 2 3 5 1 3 1 5 5 3 2 5 4 3 1 2 0 3 0 5 2 3 4 3 3 1 4 1 0 3 0 3 2
     3 5 2 4 0 4 3 5 3 4 3 0 3 5 2 2 0 2 3 3 4 0 4 0 4 3 1 1 3 2 2 5 3 1 3 4 1 2
     5 0 1 5 0 2 3 1 1 2 4 1 4 3 5 4 2 2 3 1 4 5 5 4 3 5 2 0 5 2 3 3 2 0 4 1 1 5
     2 2 0 0 2 5 2 1 0 2 2 3 3 3 3 5 2 2 1 3 1 3 2 3 3 2 4 3 3 5 0 4 4 4 0 4 1 2
     4 0 5 0 5 1 2 4 0 0 4 4 1 4 0 5 0 0 4 0 0 0 4 5 0 1 2 2 4 5 1 5 2 0 5 4 5 3
     1 3 3 0 4 3 3 3 5 4 5 0 2 2 0 3 3 2 5 5 3 0 5 5 3 3 4 2 4 1 3 4 4 5 4 2 2 0
     1 2 2 0 1 5 4 4 0 2 5 4 1 2 0 0 5 1 2 4 0 5 3 4 1 0 5 1 1 0 4 3 5 1 3 0 5 0
     5 4 4 5 2 2 3 4 1 5 4 4 5 300 2 4 4 1 3 3 1 4 4 3 4 0 4 0 3 5 4 1 4 5 0 3 3 1
     1 2 2 3 2 2 5 4 1 1 5 5 3 3 4 4 0 2 3 5 5 5 4 5 3 1 1 0 1 2 0 5 5 0 2 0 4 2
     2 3 0 3 3 5 2 3 3 4 5 0 0 4 5 1 0 1 2 5 2 0 1 0 4 1 2 2 2 5 1 1 4 1 3 5 3 4
     5 5 4 3 0 2 1 3 0 3 0 2000)

Q = (5 10000 2 0 4 3 2 2 2 3 4 0 3 3 3 3 2 4 2 1 5 3 3 4 2 5 3 0 4 4 0 3 1 1 2 0 3 1
     5 1 2 3 0 1 3 4 0 3 5 2 5 0 0 0 2 2 3 2 4 0 3 1 3 5 1 0 4 0 1 3 5 3 4 0 5 3
     3 0 4 2 5 4 4 1 1 0 0 2 2 4 3 2 2 0 5 1 0 0 0 1 0 1 1 1 3 4 1 1 2 2 5 4 2 3
     5 3 3 4 2 0 4 0 2 3 0 4 5 3 3 4 4 2 0 1 3 0 1 0 4 3 4 4 2 2 3 4 5 0 3 0 3 3
     4 5 2 1 2 4 3 5 1 5 5 0 3 0 4 0 3 2 3 1 2 3 1 4 1 5 1 0 3 0 2 5 3 1 0 4 3 4
     1 3 0 0 5 0 5 3 1 5 4 1 3 3 3 5 3 2 3 1 0 1 1 0 4 5 5 5 3 5 1 1 2 0 4 4 5 0
     0 1 3 2 2 0 4 1 2 3 2 0 5 1 2 5 2 5 0 4 3 5 5 3 2 2 0 3 3 1 4 1 0 4 3 0 1 3
     0 2 3 5 3 2 2 4 4 3 4 0 1 1 0 4 1 1 1 5 2 1 1 1 4 0 1 3 1 3 0 3 5 3 0 5 4 5
     3 4 3 3 5 5 4 2 5 5 0 5 0 1 4 3 3 1 0 5 2 0 1 1 2 0 1 5 0 5 2 3 0 1 0 5 3 5
     4 4 5 0 0 5 1 4 1 5 5 4 5 5 3 1 0 4 4 3 4 2 3 0 3 4 0 5 5 2 2 4 2 0 4 4 1 3
     2 1 0 4 4 3 2 2 2 0 4 1 5 4 5 1 2 0 5 4 4 0 4 0 2 5 3 2 2 1 5 3 0 2 5 2 2 1
     4 2 3 3 4 3 5 0 2 0 1 3 0 0 2 2 5 1 2 3 0 5 3 0 4 3 1 5 2 3 5 3 2 1 2 4 4 2
     0 5 3 1 0 2 1 4 5 1 3 3 4 4 5 0 1 4 4 5 2 1 1 0 1 3 2 3 2 1 0 1 0 4 5 1 4 4
     3 1 2 1 0 1 3 4 5 4 5 3 5 0 5 2 1 5 1 0 1 0 5 1 0 3 4 3 5 1 3 5 5 3 1 4 2 0
     3 1 0 4 2 4 2 0 1 1 3 2 2 0 5 1 2 0 5 2 4 3 3 1 0 4 3 5 3 2 5 3 2 2 3 2 1 5
     0 3 0 2 0 1 2 4 4 5 3 0 0 1 4 5 0 3 2 1 4 5 1 0 4 1 5 2 3 2 3 5 1 3 5 2 5 1
     2 1 3 0 4 3 2 3 5 1 3 1 5 5 3 2 5 4 3 1 2 0 3 0 5 2 3 4 3 3 1 4 1 0 3 0 3 2
     3 5 2 4 0 4 3 5 3 4 3 0 3 5 2 2 0 2 3 3 4 0 4 0 4 3 1 1 3 2 2 5 3 1 3 4 1 2
     5 0 1 5 0 2 3 1 1 2 4 1 4 3 5 4 2 2 3 1 4 5 5 4 3 5 2 0 5 2 3 3 2 0 4 1 1 5
     2 2 0 0 2 5 2 1 0 2 2 3 3 3 3 5 2 2 1 3 1 3 2 3 3 2 4 3 3 5 0 4 4 4 0 4 1 2
     4 0 5 0 5 1 2 4 0 0 4 4 1 4 0 5 0 0 4 0 0 0 4 5 0 1 2 2 4 5 1 5 2 0 5 4 5 3
     1 3 3 0 4 3 3 3 5 4 5 0 2 2 0 3 3 2 5 5 3 0 5 5 3 3 4 2 4 1 3 4 4 5 4 2 2 0
     1 2 2 0 1 5 4 4 0 2 5 4 1 2 0 0 5 1 2 4 0 5 3 4 1 0 5 1 1 0 4 3 5 1 3 0 5 0
     5 4 4 5 2 2 3 4 1 5 4 4 5 3 2 4 4 1 3 3 1 4 4 3 4 0 4 0 3 5 4 1 4 5 0 3 3 1
     1 2 2 3 2 2 5 4 1 1 5 5 3 3 4 4 0 2 3 5 5 5 4 5 3 1 1 0 1 2 0 5 5 0 2 0 4 2
     2 3 0 3 3 5 2 3 3 4 5 0 0 4 5 1 0 1 2 5 2 0 1 0 4 1 2 2 2 5 1 1 4 1 3 5 3 4
     5 5 4 3 0 2 1 3 0 3 0 2 1)

     Proveďte rychlostní srovnání oproti vyváženému stromu
     (klíče a hodnoty mezi klíči vyhledávejte s pravděpodobnostmi odpovídající 
      vahám).

3] Naprogramujte výpočet Pagerank vektor mocninnou metodou. 
   Udělejte to bez epxlicitního výpočtu matice A.

4,5] Implementujte inkrementální vkládání do R-stromu.
     Experimentálně porovnejte tři základní metody splitu.

6]  Implementujte kd-strom a NN-search v nem.
    Použijte jinou metriku nez Euklidovskou.
    (Alternativa: implementuje NN-search pro R-strom z ukolu 4)

7]  Implementujte vp-strom a NN-search v nem.