Datové struktury I

V zimním semestru 2017/2018 přednáším Datové struktury I [NTIN066].

Přednášky se konají ve středu od 14:00 v S3. Anglickou verzi přednáší Jirka Fink ve středu od 9:00 v S4.

datum co jsme dělali zdroje
4. 10. Úvod: rozhraní datových struktur, statičnost/dynamičnost, výpočetní model. Různé způsoby amortizované analýzy: agregace, účtování, penízky, potenciál. Nafukovací pole (se zvětšováním a zmenšováním), binární počítadla, líně vyvažovaná varianta BB[α] stromů. [P01] [L9.1-9.4]
11. 10. Splay stromy: Operace Splay a její amortizovaná analýza. Implementace operací Find, Insert a Delete pomocí Splay. Rozšíření analýzy o váhy. [P02] [L9.5] [ST]
18. 10. Splay stromy: Statická optimalita (věta), dynamická optimalita (hypotéza). (a,b)-stromy: definice, logaritmická hloubka, Find, Insert a Delete, volba parametrů. [P03] [ST] [L8.3]
25. 10. (a,b)-stromy: Amortizované chování (a,2a-1) a (a,2a)-stromů. Třídicí algoritmus A-sort. Haldy: rozhraní hald, d-regulární haldy, použití v Dijkstrově algoritmu. [P03] [P04] [L8.3, 4.2, 6.2]
1. 11. Haldy: Binomiální, líné binomiální, Fibonacciho. [P04] [L18]
8. 11. Přednáška se nekoná: Děkanský sportovní den
15. 11. Cache-oblivious algoritmy: Příklady rychlosti přístupu do paměti, zjednodušený popis hardwarové keše, množinová asociativita a aliasing. Teoretické modely: I/O, cache-aware, cache-oblivious. Scanování pole. Třídění: Mergesort, vícecestný Mergesort, zmínka o Funnelsortu a dolním odhadu. [P05] [CO]
22. 11. Cache-oblivious algoritmy: Transpozice matice. Statické množiny – binární vyhledávání, (a,b)-stromy, van Emde-Boasovo uložení binárních stromů. [P05] [CO] [ST2]
29. 11. Plán: Cache-oblivious algoritmy: model kontra realita, Sleatorova-Tarjanova věta o kompetitivitě LRU. Hešování: c-univerzální a k-nezávislé systémy funkcí.

Cvičení

Cvičení se konají jednou za 2 týdny, zapište se na jedno z nich v SISu. Můžete si vybrat i cvičení v angličtině k české přednášce.

V průběhu semestru budou zadány čtyři domácí úkoly po 100 bodech. K udělení zápočtu musíte získat minimálně 320 bodů. Vzhledem k náročnosti přípravy úkolů nebudou zadány žádné dodatečné úkoly ani náhradní možnosti získání zápočtů.

Přečtěte si podrobná pravidla domácích úkolů.

Stránky cvičících:

Domácí úkoly

úkol termín
Splay stromy 2017-10-29
Fibonacciho haldy 2017-11-19
Transpozice matice 2017-12-10

Odevzdávejte pomocí klikátka.

Materiály

Stránku spravuje Martin Mareš