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ý: 8:00 - 9:30
Cvičení: úterý: 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

Úkoly

úkol 1: experimentálně porovnejte výšku násl. stromů
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 9.10.
forma odevzdání: předvést na cvičení

úkol 2:
Najděte bijekci mezi interpretacemi Catalanových
čísel (handshakes nebo triangulae polygonu vs.
některá z dalších interpretací z přednášky).

body: 5+2
včasné odevzdání: do 9.10.
forma odevzdání: dokument na e-mail

ú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 9.10.
forma odevzdání: předvést na cvičení


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: 5+2
včasné odevzdání: do 23.10.
forma odevzdání: předvést na cvičení

ukol 5:

Experimentálně vyhodnoťte počty operací při vkládání do
AVL stromu. Sestavte AVL strom (postupným vkládáním) o
2000 uzlech (náhodné pořadí). Pro každý externí uzel
zjistěte
A) zda by nastala rotace (a která), kdyby tam byl vložen
   nový klíč. (bez rotace, jednoduchá, dvojitá)
B) délka cesty (1, 2, 3, 4, 5, >5)  od tohoto externího uzlu
   k nejbližšímu předkovi s nenulovým vyvažovacím faktorem.
Určete frekvence ve kterých nastávají současně jevy v A,B.
(Pro více detailů, viz 
http://phoenix.inf.upol.cz/~konecnja/vyuka/2017W/ALS1/L4.pdf
slajdy 30-32)

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


ukol 6:
Explicitně vyjádřete vztah mezi Fibonacciho stromem
a interpretací Fibonacciho řady jako velikost populace
králíků v čase (přesněji rodokmenovým stromem těch králíků).

body: 5+2
včasné odevzdání: do 21.11.
forma odevzdání: dokument na e-mail

ukol 7:
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.

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

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


8] Naprogramujte demonstraci R-stromu 2d s kvadratickým splitem.

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

9] Experimentálně porovnejte tři algoritmy stavby statických
R-stromů, které jsme probrali na přednášce: vytvořte R-stromy
ze zhruba 2000 dat (zkuste různé hodnoty fill factoru)
a porovnejte rychlost vyhledávání.

body: (5-10)+2
včasné odevzdání: do 4.12.
forma odevzdání: osobně předvést 


10] Naprogramujte demonstraci m-stromu 2d

body: 10+4
včasné odevzdání: do 4.12.
forma odevzdání: osobně předvést

Zkouška

ústní formou.

Požadavky na zápočet

domácí úkoly.

                                1.	2.	3.	4.	5.      6.      7.       8
1.  BEZNOSKA Tomáš              5+2             5+2     5+2     5+2            10+2     10+4         Z
2.  CSÁKÁNYIOVÁ Ema                     5+2                             5+2
3.  CUDELCU Valentin Emil               5+2
4.  ČERNOHOUS Matyáš            5+2     5+2     5+2     5+2     5+2     5+2
5.  DOHNAL David		5                       5+2     5+2     5+2    10+2     10+4         Z
6.  DUFKOVÁ Andrea		
7.  FOLTÝN Miroslav		5+2	5+2	5+2     5+2     5+2     5+2    10+2                  Z
8.  HAAS Antonín		
9.  HRŮZA David			5+2	5+2             5+2             5+2    10+2     10           Z
10. JURAČKA Jakub		5+2	5+2     5+2     5+2     5+2     5      10+2                  Z
11. JURÁSKOVÁ Kateřina		5+2	5+2             5+2     5+2
12. LADEMBERGER Denis			
13. LUBOJACKÁ Jana		5+2	5+2     5+2	5+2     5+2     5+2    10                    Z
14. MACHÁLEK Libor		5+2	5+2	5+2     5+2     5+2     5+2
15. MAJZLÍKOVÁ Gabriela		5+2	5+2     5       5+2     5+2     5      10+2                  Z
16. MOLČÍK Jan			5+2     5+2
17. OPÁLKA Michal		
18. ŘEZNÍČEK Adam		5+2	5+2     5+2     5+2     5+2     5      10+2                  Z
19. ŠIMKOVÁ Lucie		5+2	5+2	5	5+2     5              10       10           Z
20. VALIGURA Petr		5+2	5+2	5+2     5+2     5+2     5+2             10+4         Z
21. VRAŠTIAK Kristián		5+2	5+2	5+2     5+2     5+2     5+2    10+2                  Z