Datové struktury II

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

LS 2014/2015

TIN067 - 2/0 Zk

Čas konání: St 14:00-15:30.
Místo konání: S4, Malá Strana.

Pokračování základní přednášky o datových strukturách.

Plán přednášky

• Samoupravující se seznamy (MFR strategie)
• Persistentní datové struktury
  • Částečná persistence
  • Úplná persistence
• Vícerozměrné datové struktury
  • KD stromy
  • Range trees
• Vyhledávací stromy
  • Náhodné stromy
  • Treaps
  • Skip-listy, skip-lifty
• Van Emde Boasova struktura, x-fast a x-fast trie
• Union-Find problém.
• Řetězce
  • Suffixové stromy
  • Trie, komprimované trie
  • x - Reprezentace řídkých matic a téměř konstantních vektorů
• Semidynamizace a dynamizace vyhledávacího problému
• x - Distribuované datové struktury
• x - Bloom filter.
• x - Streamy dat.
• x - Třídění v lineárním čase, kvadratické vyhledávání

Literatura:

• Aktualizované poznámky k přednášce. (Kompaktní verze.)
• V. Koubek, A. Koubková: Datové struktury II. Online skripta.
• 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
  
  
• J.R. Driscoll, N. Sarnak, D.D. Sleator, R.E. Tarjan: Making Data Structures Persistent. J. of Comp. and Sys. Sci. 38, 86-124, (1989)
• M. van Kreveld, M. Loffler: Geometric Algorithms. Lectures: Range searching and kd-trees and Range trees. February 24-26, 2015.
• J. Erickson: Algorithms, Etc. Chapter: Treaps and skip lists. January 2015 revision.
• U. Manber, G. Myers. Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327, 1990.
• D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1999.

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.