Datové struktury I
Základní přednáška o konstrukci efektivních datových struktur.Přednáška
Slajdy z přednášek (kompaktní verze) jsou průběžně upravovány.Obsah jednotlivých přednášek
- 1. přednáška dne 6.10.
-
- Úvod
- Amortizovaná složitost: inkrementace binárního čítače, dynamické pole, BB[α]-strom
- Splay tree: rotace a amortizovaná složitost
- 2. přednáška dne 13.10.
-
- Splay tree: operace Insert a Delete
- (a,b)-stromy: základní operace (vyhledávání, vkládání, mazání), paralelní přístup, A-sort, ekvivalence s červeno-černými stromy
- Regulární halda
- 3. přednáška dne 20.10.
-
- Binomiální halda
- Fibonacciho halda
- Cache-oblivious algoritmy: motivace
- 4. přednáška dne 27.10.
-
- Cache-oblivious algoritmy: cache-oblivious analýza (čtení paměti, binární halda, binární vyhladávání, mergesort)
- Transpozice matic
- Rozložení van Emde Boas
- Sleator & Tarjan
- 5. přednáška dne 3.11.
-
- Sleator & Tarjan: Důkaz
- Universální hešování: definice, základní vlastnosti, Multiply-mod-prime, tabulkové hešování
- 6. přednáška dne 10.11.
-
- Universální hešování: tabulkové hešování, další hešovací systémy
- Perfektní hešování
- Hešování se separovanými řetězci: složitost operace Find
- Dne 17.11. se přednáška nekoná (státní svátek)
-
- 7. přednáška dne 24.11.
-
- Hešování se separovanými řetězci: délka nejdelšího řetězec, amortizovaná složitost
- Lineární přidávání: analýza složitosti
- 8. přednáška dne 1.12.
-
- Kombinace lineárního přidávání s hešovacím systémem multiply-shift
- Kukaččí hešování: operace a složitost
- 9. přednáška dne 8.12.
-
- k-d stromy
- Intervalové stromy
- 10. přednáška dne 15.12.
-
- Intervalové stromy: dynamizace a zrychlení pomocí kaskádování
- 11. přednáška dne 22.12.
-
- R-stromy
- 12. přednáška dne 5.1.
-
- Deamortizace dynamického pole
- Dynamizace datových struktur
- Obecné kaskádování
- 13. přednáška dne 12.1.
-
- Bloom filtry
- Čítačové filtry
- Bloomier filtry
Literatura
- A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011.
- T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Third edition, MIT Press, 2009. On-line
- K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984
- D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005, Accessible on-line from faculty IP addresses.
- D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. J. ACM 32 (3): 652–686, 1985.
- E. Demaine: Cache-Oblivious Algorithms and Data Structures. 2002.
- R. Pagh: Cuckoo Hashing for Undergraduates. Lecture note, 2006.
- M. Thorup: High Speed Hashing for Integers and Strings. lecture notes, 2014.
- M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.
- D.E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998
- M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, Springer, 3 rd edition, 2008. The second edition is on-line.
- Erik Demaine: přednáška Advanced Data Structures z MIT
- A. Broder, M. Mitzenmacher: Network applications of bloom filters: A survey. Internet mathematics, 2004, 1.4: 485-509. On-line
- B. Chazelle, J. Kilian, R. Rubinfeld, A. Tal: The Bloomier filter: an efficient data structure for static support lookup tables. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF), pp. 30-39 On-line
- M. Mareš: přednaška Datové struktury II
- B. Chazelle, L. J. Guibas: Fractional cascading: I. A data structuring technique. Algorithmica, 1 (1): 133-162. On-line
- B. Chazelle, L. J. Guibas: Fractional cascading: II. Applications. Algorithmica, 1 (1): 133-162. On-line
Czech | English | |
---|---|---|
(a,b)-tree: definition, insert, delete | 1 | 3 |
(a,b)-tree: join, split, amortized, parallel | 1 | |
A-sort | 1 | |
Red-black tree | 1 | 2,3 |
Splay tree | 3,4,5 | |
Complete d-ary heap | 1 | 2 |
Binomial heap | 1 | 2,4 |
Lazy binomial heap | 1 | |
Fibonacci heap | 1 | 2,4 |
Cache-oblivious algorithms | 6,4,5 | |
Hashisg with separate chaining | 1 | 10 |
Hashisg with linear probing | 1 | 10 |
Cuckoo hashing | 7 | |
Universal hashing | 8 | |
Range trees | 4,11 | |
R-trees | 4 | |
Dynamization | 15 | |
Fractional cascading | 16,17 | |
Bloom filters | 13,14 |
Cvičení
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ě 350 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 též podrobná pravidla k řešení úkolům.
Zadání domácích úkolů
- Externí třídění (termín odevzdání 30.10.) English
- Splay tree (13.11.) English
- Fibonacciho halda (27.11.) English
- Transpozice matic (11.12.) English
- Hešování (1.1.) English
Výsledky domácích úkolů studentů chodících na moje cvičení. Otázky k hodnocení a bodování pokládejte na cvičení.
Další odkazy
- Anglická přednáška
- Loňská česká a anglická přednáška.