Předmět Datové struktury I (NTIN066)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN066 - Datové struktury I, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Naučit základní datové struktury a algoritmy včetně teoretické analýzy jejich chování
Sylabus
Základní přednáška o konstrukci efektivních datových struktur. 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í.Haldy Regulární halda binomiální halda - amortizovaná a nejhorší časová složitost Fibonacciho haldaStromy (a,b)-stromy MFR-strategie pro seznamy, Splay stromy přehled ostatních řešení: AVL stromy, červeno-černé stromy, BB-α stromyTechniky 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ů cache-aware technikyHaš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 FKS perfektní hašování nebo kukačkové hašováníVícerozměrné datové struktury KD stromy Range trees
Literatura
Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011T. H. Cormen, C.E. Leiserso, R. L. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2009K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005
Garant
doc. Mgr. Michal Koucký, Ph.D.