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

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ý: 9:45 - 11:15
Cvičení: úterý: 11:30 - 13:00

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

25.9.2019 -- Složitost vyhledávání v BST L1.pdf (slajdy 8, 20-27)

Studijní materiály (z předchozího roku)

Následující studijní materály jsou z předchozí iterace tohoto kurzu. K té letošní je budu v průběhu semestru.

20.9.2018 -- Intro a BST L1.pdf
27.9.2018 -- Catalanova čísla, optimální stromy L2.pdf
4.10.2018 -- Hašování L3.pdf
11.10.2018 -- AVL stromy L4.pdf
18.10.2018 -- Pagerank L5.pdf
25.10.2018 -- R-tree L6.pdf, demonstrace R-stromů: linearní split, kvadratický split, bruteforce split.
1.11.2018 -- Varianty R-stromů: R+,R* L7.pdf, demonstrace R+-stromů a R*-stromů.
8.11.2018 -- Další Varianty R-stromů zdroj a kd-stromy kd.pdf.
15.11.2018 -- Metrické stromy L9.pdf.
22.11.2018 -- Metrické stromy podruhé (BK-tree, m-tree).
29.11. a 6.12.2018 -- SVD LA.pdf LB.pdf .

Úkoly (požadovaný počet: 60 bodů)

úkol 1: experimentálně porovnejte prům. čas vyhledávání v násl. stromech:
1) RBBST o 100 prvcích;
2) BST, který byl na začátku prázdný a do kterého
   bylo vloženo 200 prvků a následně 100 smazáno;
3) BST který byl na začátku prázdný a se kterým
   byly 100x vloženy dva nové prvky a jeden prvek
   smazán.



body: 5+2
včasné odevzdání: do 10.10. (včetně)
forma odevzdání: předvést na cvičení

------------------------------------------------------------

úkol 2: Vysvětlete konstrukci Catalanova trojúhelníku.

body: 5+2
včasné odevzdání: do 10.10. (včetně)
forma odevzdání: na papíře či v el. dokumentu

------------------------------------------------------------

úkol 3: Experimentálně porovnejte vyvážený a optimální strom o 1000
uzlech s vahamí:

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)

(Prvky vyhledávejte s četností odpovídající jejich vahám).

body: 5+2
včasné odevzdání: do 17.10.
forma odevzdání: předvést na cvičení nebo po dohodě



ukol 4:

Navrhněte dokonalé hašování pro 4888 náhodně zvolených
číselných klíčů. Experimentálně porovnejte s vyhledáváním
v setřízením poli.

body: 10+4
včasné odevzdání: do 6.11.
forma odevzdání: předvést na cvičení


ukol 5:
Naprogramujte výpočet Pageranku pomocí mocninné metody z prvotní
matice Q. (pro více detailů, viz 
http://phoenix.inf.upol.cz/~konecnja/vyuka/2017W/ALS1/L5.pdf
poslední slajd).

Bonusové body jsou za reprezentaci vstupní matice jako řídké matice
(vlastní nastudovaní a implementace)

Pro ukázku použijte první matici Q na slajdech.

body: 5+2 (+10)
včasné odevzdání: do 6.11.
forma odevzdání: předvést na cvičení


ukol 6:
Naprogramujte grafickou demonstraci R-stromu 2d s libovolným splitem.

body: 10+4
včasné odevzdání: do 20.11.
forma odevzdání: předvést na cvičení


ukol 7:
Navrhněte algoritmus (napište pseudokód) na hledaní
optimálního splitu se složitosti $O(n^d)$ (d = počet dimenzi, n =
počet zaznamů ke splitu).

body: 10+4
včasné odevzdání: do 4.12.
forma odevzdání: předvést na cvičení nebo poslat e-mailem


ukol 8:
Experimentalne porovnejte dva (tri) algoritmy hledani nejblizssich
sousedu v R-stromu.

body: 5(10)+3
včasné odevzdání: do 17.12.
forma odevzdání: předvést na cvičení

Zkouška

ústní formou.

Požadavky na zápočet

domácí úkoly.

BADAL        1V,2,3V,4V,5V,6V          (5+2)+5+(5+2)+(10+4)+(5+10)+(10+4)          = 62
BENES        1V,2V,3V,4V,5+,6V         (5+2)+(5+2)+(5+2)+(10+4)+(5+10)+(10+4)      = 64
CHALUPA      4V                        (10+4)                                      = 14
KAUFMAN      1V,2V,3V,4V,5+V,6V        (5+2)+(5+2)+(5+2)+(10+4)+(5+2+10)+(10+4)    = 66
MOLCIK       1V,4V                     (5+2)+(10+4)                                = 21
PANCHARTEK   1V                        (5+2)                                       =  7
PAVLU        1,2V,3,4                  5+(5+2)+5+10                                = 37
TUMA         1V,3V,4V,5V               (5+2)+(5+2)+(10+4)+(5+10)                   = 43
VACLAVEK     1V,3V,4V,5+V              (5+2)+(5+2)+(10+4)+(5+2+10)                 = 45
VRABKA       1V,2V,3V,4V,6V,7V         (5+2)+(5+2)+(5+2)+(10+4)+(10+4)+(10+4)      = 63
VYHNALEK     1V,2,3V,4V,5+V,6V         (5+2)+5+(5+2)+(10+4)+(5+2+10)+(10+4)        = 64
VYKOUPIL     1V,2V,3V,4V,5+            (5+2)+(5+2)+(5+2)+(10+4)+(5+10)             = 50
VYMAZAL      1V,3V,4V,5+V              (5+2)+(5+2)+(10+4)+(5+2+10)                 = 45
WEHMHONER    1V,3V                     (5+2)+(5+2)                                 = 14
ZALESAK      1V,3V,4V,5+,6V            (5+2)+(5+2)+(10+4)+(5+10)+(10+4)            = 57