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: středa: 9:45 - 11:15
Cvičení: středa: 11:30 - 13:00
Obsah přednášek
- 23-09-2020: Analýza binárních vyhledávacích stromů; cvičení: Catalanova čísla; (použité výukové materiály: pdf)
- 30-09-2020: Analýza hašovacích tabulek; dokonalé hašování, cvičení: pokračování přednášky; (použité výukové materiály: pdf)
- 07-10-2020: Opět Catalanova čísla; konstrukce optimálních vyhledávacích stromů; (použité výukové materiály: pdf)
- 14-10-2020:
R-stromy (nahrazující studijní materiály: pdf; demonstrace R-stromů:
linearní split,
kvadratický split,
bruteforce split.)
- 21-10-2020:
R* a R+-stromy (nahrazující studijní materiály: pdf; demonstrace
R+-stromů a
R*-stromů.)
- 04-11-2020:
Hiblertovy R-stromy, linearní split (nahrazující studijní materiály: pdf)
- 11-11-2020:
Statické R-stromy, vyhledávání nejbližších sousedů v R-stromech (nahrazující studijní materiály: pdf,
pdf)
- 18-11-2020: Metrické stromy (nahrazující studijní materiály: pdf)
- 25-11-2020: Další metrické stromy (m-stromy) (nahrazující studijní materiály: pdf)
- 02-12-2020, 09-12-2020:
Pagerank, analýza AVL stromů (nahrazující studijní materiály: pdf,pdf)
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 1-85233-977-.
-
Skiena S. S. The Algorithms Design Manual. Springer, New York, 1998. ISBN 0-387-94860-0.
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 zveřejňovat v průběhu semestru.
Požadavky na zápočet
Vypracování domácích úkolů; 60 bodů
Domácí úkoly
- Úkol 1: (5+2 body): Otestovat vliv mazání na vyváženost
binárního vyhledávacího stromu. Zadání na slajdech pdf. Pozor, v posledním bodě má být 100x, nikoli 200x
- Úkol 2: (5+2 body): Dokonalé hašování a jeho porovnání s vyhledáváním v setřízeném poli.
Zadání na slajdech pdf
- Úkol 3: (7 bodů; nejsou body za včasné odevzdání):
Naprogramujte konstrukci optimálního binárního vyhledávacího stromu
vzhledem k vahám v souboru.
Experimentálně porovnejte
s vyhledáváním v setřízeném poli. Při experimentu vyhledávejte prvky
s ohledem na zadané váhy.
- Úkol 4: (10 (+5) bodů; nejsou body za včasné odevzdání):
Naprogramujte algoritmus vkládání (lib. slit) do R-stromů s grafickou reprezentací.
5 bodů je navíc pokud uděláte i algoritmus mazání.
- Úkol 5: 5 bodů; Naprogramujte proceduru, která vrací H-hodnotu (viz pdf)
- Úkol 6: 10 bodů;
Proveďte experimentální srovnání dvou algoritmů vyhledávání nejbližších sousedů z pdf (porovnávejte rychlost).
- Úkol 7: 10 bodů;
Proveďte experimentální srovnání Hilberovových a STR statických R-stromů
(metriku nechámvám na vás: rychlost vyhledávání, množství překryvů, počet
navštívených uzlů při náhodném vyhledávání, počet uzlů...)
- Úkol 8: 5 bodů;
Naimplementujte algoritmus pagerank s implicitní maticí Q (jako je to v na posledním slajdu v pdf
).
Aplikujte na matici, která se v těch slajdech používá v průběžném příkladu.
Body
-1- -2- -3- -4- -5- -6- -7- -8-
HAJDA Michal
HARCEKOVÁ Lucia 5+2 5+2 7 15 5 10
HRUBÁ Gabriela 5+2 5+2 7 10 5 10
CHALUPA Michael 5+2 5+2
IBRAHIM Karim
MARTINÁT Dominik 5+2 7 15 5 10 10
NOVÁKOVÁ ANDRÝSKOVÁ Denisa 5+2 5+2 7 15
ŠPAČKOVÁ Anna 5 5 7 15 5 10
TOMEK Stanislav
ZEMEK Alexandr 5+2 5+2 7 10 5 10 10