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]
29. 11. 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í. 1-univerzální systémy odvozené ze skalárního součinu a z lineárních funkcí. Očekávaná délka řetězce pro c-univerzální systém. [P05] [ST2] [P06] [L11.3, 11.5]
6. 12. Přehled systémů hešovacích funkcí: skalární součin, lineární zobrazení, multiply-shift, polynomy, tabelace. Základní vlastnosti hešování s řetězci a hešování s lineárním přidáváním (bez důkazů). Kukaččí hešování. [P07] [E10]
13. 12. Perfektní hešování FKS (Fredman, Komlós, Szemerédi). Analýza hešování s lineárním přidáváním. [P07] [P08] [FKS] [KS] [T]
20. 12. Důkazy některých vět o systémech hešovacích funkcí. Bloomovy filtry: základní konstrukce, snižování pravděpodobnosti chyby paralelní kompozicí. Zmínka o počítacích filtrech a aproximacích slovníků (bloomier filtry). [P06] [P09] [T2]
3. 1. Náprava lemmatu z minulé přednášky. Vícerozměrné datové struktury: intervalové dotazy na binárních stromech, k-d stromy. [P10] [M7.2.1]
10. 1. Vícerozměrné datové struktury: intervalové stromy (range trees), jejich dynamizace částečnou rekonstrukcí a zrychlení pomocí kaskádování. Něco navíc (nezkouší se): Obecnější princip zlomkového kaskádování. Okénkové dotazy pro intervaly a úsečky v rovině, 1D interval trees, 1D a 2D segment trees. [P10] [G]

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 bude zadáno pět domácích úkolů 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
Hešování 2017-12-31
Bonus: (a,b)-stromy 2018-02-18

Odevzdávejte pomocí klikátka.

Zkoušky

Předtermín se koná 11. ledna od 10:40 v S322. Přihlašujte se prosím v SISu.

Další termíny jsou vypsány během zkouškového, opět prosím o přihlašování v SISu. Pokud vám žádný termín nevyhovuje, ozvěte se, vyzkouším vás jindy.

Podívejte se na podrobné požadavky ke zkoušce. (See also exam questions in English.)

Pozor, ke zkoušce je třeba mít zápočet (kromě předtermínů). Cvičící slíbili všechny domácí úkoly opravit do prvního řádného termínu.

Materiály

Stránku spravuje Martin Mareš