Datové struktury 1
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
ZS 2014/2015
TIN066 - 2/0 Zk
Čas konání: Po 12:20-14:00.
Místo konání: S5, 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
Literatura:
- Aktualizované poznámky k přednášce. (Kompaktní verze.)
- 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.
Domácí úkoly
- Do 23.10. 2014.
- Do 13.11. 2014.
- Do 8.12. 2014.
- Do 4.1. 2015.
- Dva dny před zkouškou
Zkouška
Termíny zkoušek jsou vypsané v SISu, kde se i na zkoušky zapisuje. Když se přihlásíte na některý termín,
tak jej využijte nebo se včas omluvte či odhlašte. Propadlým termínem ztracíte svůj pokus,
navíc případně propadlý termín mohl využít některý z vašich spolužáků.
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í
V letním semestru je volně navazující přednáška Datové struktury II.
Často kladené otázky
Q: Chtěl bych odevzdat řešení do CodExu v C++11, ale CodEx C++11 neumí. Co s tím?
Bohužel, CodEx v součacné době z technických důvodů nepodporuje C++11. Řešení do CodExu je tak
nutné odevzdat ve starší formě C++.
Q: Jsem student kombinovaného studia, jaké jsou povinnosti pro získání zápočtu a zkoušky z této přednášky?
Účast na mých přednáškách není povinná, i když ji samozřejmě doporučuji. V průběhu semestru plánuji zveřejňovat na svých webových stránkách svoji přípravu, ze které půjde vyčíst,
co se zhruba probralo. Tato informace však nemusí být nutně úplná. Zkoušet se bude z probrané látky. Zápočet není,
domácí úkoly jsou dobrovolné. Nicméně pokud vyrešíte všech pět úkolů, můžete si tím vylepšit známku až o jeden stupeň,
pokud budete schopen(na) při zkoušce svá řešení rozebrat. Tím především prokážete to, že jste je skutečně vypracoval(a) sám(a).
(Jinak ale pokud probranou látku budete umět třeba na jedničku, jedničku dostanete i bez domácích úkolů.)