Datové struktury I

Základní přednáška o konstrukci efektivních datových struktur.

Vzhledem k náročnosti tohoto předmětu byly vytvořeny dva nové doplňkové předměty, které by měly poskytnout více času k diskuzi teoretických i praktických otázek souvisejících s datovými strukturami.

  1. V předcházejících letech řada studentů trávila hodně času hledáním chyb při ladění vlastních programů potřebných ke splnění domácích úkolů. Proto jsme založili předmět Implementace datových struktur (NTIN106), jehož cílem je seznámit studenty s pokročilými technikami efektivní implementace datových struktur a algoritmů.
  2. Analýza datových struktur doplňuje cvičení z Datových struktur I (NTIN066) o hlubší partie týkající se teoretické analýzy chování 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 4.10.
  • Úvod
  • Amortizovaná složitost: inkrementace binárního čítače, dynamické pole
  • BB[α]-strom

2. přednáška dne 11.10.
  • Splay strom: rotace a amortizovaná složitost, operace Insert a Delete, další zajímavé vlastnosti
  • (a,b)-stromy: základní operace (vyhledávání, vkládání, mazání), paralelní přístup, A-sort

3. přednáška dne 18.10.
  • Červeno-černé stromy, ekvivalence s (2,4)-stromy
  • Cache-oblivious algoritmy: motivace, cache-oblivious analýza (čtení paměti, binární halda, binární vyhledávání, mergesort)
  • Transpozice matic: Trivialní a blokový algoritmus

4. přednáška dne 25.10.
  • Transpozice matic: Rekurzivní cache-oblivious algoritmus
  • Rozložení van Emde Boas
  • Věta Sleator-Tarjan srovnávající LRU a OPT strategie výměny stránek

5. přednáška dne 1.11.
  • Haldy: regulární, binomiální a Fibonacciho

6. přednáška dne 8.11.
  • Fibonacciho halda: důkaz složitosti
  • Intervalové dotazy v jedné dimenzi
  • Kd-stromy

7. přednáška dne 15.11.
  • Range tree: Konstrukce, intervalové dotazy

dne 22.11. přednáška odpadá

8. přednáška dne 29.11.
  • Range tree: Dynamizace pomocí BB[α]-stromů
  • Fractional cascading
  • Range tree: zrychlení intervalových dotazů pomocí Fractional cascading
  • Obecnější verze Fractional cascading

9. přednáška dne 6.12.
  • Hašování: Výběr hašovací funkce

10. přednáška dne 13.12.
  • Hašování: Výběr hašovací funkce, separované řetězce

11. přednáška dne 20.12.
  • Hašování: Separované řetězce, lineární přidávání

12. přednáška dne 3.1.
  • Kombinace lineárního hašování a systému multiply-shift
  • Kukaččí hašování

13. přednáška dne 10.1.
  • Bloom filtry
  • Závěr

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
Hashing with separate chaining110
Hashing 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 110 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ů.

Podle GDPR nesmí soubory odevzdané ke splnění domácích úkolů obsahovat jméno ani jiné osobní údaje.

Přečtěte si též podrobná pravidla k řešení úkolům.

Abyste měli představu, jak má řešení zhruba vypadat, můžete se podívat na vzorové zadání, řešení a zdrojové kódy, které připravili vyučující (Veronika Slívová a Karel Král). Můžete si tento příklad zkusit implementovat, ale žádné body za něj nezískáte. Dále si můžete přečíst povídání založené na našich zkušenostech z předchozích let.

Zadání domácích úkolů

ZadáníTermín odevzdáníPředtermín
1Splay stromy4.11.28.10.
2Cache-oblivious algoritmy25.11.18.11.
3Haldy16.12.9.12.
4Range tree6.1.30.12.
5Hešování27.1.20.1.

Ke zkoušce se můžete přihlásit, i když ještě nemáte dost bodů na zápočet, ale zbývající úkoly musíte odevzdat minimálně týden před zkouškou, aby vaši cvičící měli dost času na jejich opravení. Pokud nebudete mít dost bodů na zápočet, tak nebudete ke zkoušce připuštěni.

Stránka k odevzdávání domácích úkolů.

Stránky cvičících

Obsah pátečních cvičení

  • 5.10.: Úvodní povídání o domácích úkolech; dynamické programování pro hledání staticky optimálního stromu; minimální hloubka listů v BB[α]-stromech.
  • 12.10.: Úvodní povídání o domácích úkolech; dynamické programování pro hledání staticky optimálního stromu.
  • 19.10.: Modifikace dynamického pole tak, aby umělo přidávat i mazat prvky ze začátku i konce; amortizovaný počet modifikovaných vrcholů při posloupnosti operací Insert a Delete ve (2,4)-stromech.
  • 26.10.: Modifikace dynamického pole tak, aby umělo přidávat i mazat prvky ze začátku i konce; amortizovaný počet modifikovaných vrcholů při posloupnosti operací Insert a Delete ve (2,4)-stromech; top-down operace Insert a Delete v červeno-černých stromech.
  • 2.11.: Cache-oblivious analýze: k-cestný mergesort, hledání mediánu, násobení dlouhých čísel a matic
  • 9.11.: 1. domácí úkol: Splay stromy
  • 16.11.: 1. domácí úkol: Splay stromy
  • 23.11.: Range trees
  • 30.11.: 2. domácí úkol: Cache
  • 7.12.: 2. domácí úkol: Cache
  • 14.12.: Range trees nebo Hešování podle zájmu studentů
  • 21.12.: 3. domácí úkol: Fibonacciho halda
  • 4.1.: 3. domácí úkol: Fibonacciho halda

Navíc všechna cvičení začínají diskuzí nad zadáním úkolů.

Další odkazy