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

  1. A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011.
  2. T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Third edition, MIT Press, 2009. On-line
  3. K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984
  4. 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.
  5. D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. J. ACM 32 (3): 652–686, 1985.
  6. E. Demaine: Cache-Oblivious Algorithms and Data Structures. 2002.
  7. R. Pagh: Cuckoo Hashing for Undergraduates. Lecture note, 2006.
  8. M. Thorup: High Speed Hashing for Integers and Strings. lecture notes, 2014.
  9. M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.
  10. D.E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998
  11. 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.
  12. Erik Demaine: přednáška Advanced Data Structures z MIT
  13. A. Broder, M. Mitzenmacher: Network applications of bloom filters: A survey. Internet mathematics, 2004, 1.4: 485-509. On-line
  14. 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
  15. M. Mareš: přednaška Datové struktury II
  16. B. Chazelle, L. J. Guibas: Fractional cascading: I. A data structuring technique. Algorithmica, 1 (1): 133-162. On-line
  17. B. Chazelle, L. J. Guibas: Fractional cascading: II. Applications. Algorithmica, 1 (1): 133-162. On-line
CzechEnglish
(a,b)-tree: definition, insert, delete13
(a,b)-tree: join, split, amortized, parallel1
A-sort1
Red-black tree12,3
Splay tree3,4,5
Complete d-ary heap12
Binomial heap12,4
Lazy binomial heap1
Fibonacci heap12,4
Cache-oblivious algorithms6,4,5
Hashisg with separate chaining110
Hashisg with linear probing110
Cuckoo hashing7
Universal hashing8
Range trees4,11
R-trees4
Dynamization15
Fractional cascading16,17
Bloom filters13,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ů

  1. Externí třídění (termín odevzdání 30.10.) English
  2. Splay tree (13.11.) English
  3. Fibonacciho halda (27.11.) English
  4. Transpozice matic (11.12.) English
  5. Hešování (1.1.) English
Stránka k odevzdávání domácích úkolů.

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