Datové struktury 1

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

ZS 2015/2016

TIN066 - 2/1 Zk/Z

Čas konání: St 9:00-10:30.
Místo konání: S3, Malá Strana.

Základní přednáška o konstrukci efektivních datových struktur pro magisterské studium informatiky. Vyhledávací stromy, haldy, hašování. Analýza nejhoršího, amortizovaného a očekávaného chování datových struktur. Samoupravující se datové struktury. Chování a analýza datových struktur na systémech s paměťovou hierarchií.

Plán přednášky

• Stromy
  • (a,b)-stromy
  • MFR-strategie pro seznamy, Splay stromy
  • přehled ostatních řešení: AVL stromy, červeno-černé stromy, BB-α stromy
• Haldy
  • regulární halda
  • binomiální halda – amortizovaná a nejhorší časová složitost
  • Fibonacciho halda
• Techniky pro paměťovou hierarchii
  • I/O model, cache-oblivious analýza, LRU-strategie pro on-line paging
  • příklady: transpozice a násobení matic, van Emde Boas rozložení vyhledávacích stromů
• Hašování
  • řešení kolizí, analýza pro uniformě rozdělená data
  • výběr hašovací funkce: univerzální hašování a dobré hašovací funkce
  • kukačkové hašování
• Vícerozměrné datové struktury
  • KD stromy
  • Range trees

Literatura:

• Poznámky k přednášce 2014.
• A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011.
• T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2009
• 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
  
  
• 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.

Cvičení

Domácí úkoly

1. Do 27.10. 2015. (English)
2. Do 17.11. 2015. (English)
3. Do 1.12. 2015. (English)
4. Do 22.12. 2015. (English)
5. Do 19.1. 2016. (English)

Zkouška

Zkouší se z probrané látky. Příklad zkušebních otázek je zde. Zkouška je ústní. Po zadání otázek budete mít čas na přípravu. Studijní materiály (skripta, učebnice a zápisky z přednášek) ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny. Společenský oblek není nutný, ale přiměřené oblečení je doporučeno.

Pokračování