Datové struktury 1
ZS 2021/2022
NTIN066 - 2/2 Zk/Z
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
Od teď ke přednáška opět prezenčně.
Čas konání: Čt 14:00-15:30.
Místo konání: S5, Malá Strana. Zoom: https://cesnet.zoom.us/j/4042155019
Základní přednáška o konstrukci efektivních datových struktur. Vyhledávací stromy, hešování, struktury pro práci s řetězci. Analýza nejhoršího, amortizovaného a očekávaného chování datových struktur. Samoupravující se datové struktury. Chování datových struktur na systémech s paměťovou hierarchií. Přednáška volně navazuje na přednášky Algoritmizace, Algoritmy a datové struktury 1 a Algoritmy a datové struktury 2 z bakalářského studia.
Plán přednášky
- 30.9. - Úvod, modely výpočtu, příklady.
- 7.10. - Amortizovaná složitost, potenciálová metoda. Líně vyvažované stromy. (Poznámky)
- 14.10 - Splay stromy, amortizovaná analýza, statická optimalita. (Poznámky)
- 21.10. - Splay stromy - odhad složitosti s užitím pracovní množiny. (a,b)-stromy: definice, operace, výběr parametrů, varianty. (Poznámky)
- 28.10. - statní svátek.
- 4.11. - Paměťová hierarchie: hardwarové keše, model vnější paměti, cache-aware a cache-oblivious algoritmy. (Poznámky)
- 11.11. - Cache-aware a cache-oblivious algoritmy: van Emde Boasovo rozložení stromů. Model versus realita: kompetitivní poměr LRU. Úvod do hešování
- 18.11. - Hešování: hešování se separovanými řetězci, s lineárním přidáváním, kukačkové hešování, ledovcové hešování, Bins and Balls. (Poznámky)
- 25.11. - Hešování: Výběr hešovací fuknce: k-nezávislé systémy, tabulační hešování. (Poznámky)
- 2.12. - Hešovací systémy. Video
- 9.12. - Bloomovy filtry: 1-pásmové, více-pásmové, počítací filtry, (Poznámky). Suffixová pole (Poznámky). Video (Naneštestí to video je beze zvuku. Pokud by někdo nějakou náhodou měl audio nahrávku k tomu videu, jak by mohl, že, tak bych ji uvítal.)
- 16. 12. - Konstrukce suffixového pole (zdvojováním). Geometrické datové struktury: intervalové dotazy, k-d stromy, intervalové stromy.
- 6. 1. - Paralelní datové struktury: zamykání, bez-zámkové datové struktury.
Literatura:
- M. Mareš: Lecture notes on data structures, 2019.
- M. Mareš, T. Valla: Průvodce labyrintem algoritmů, CZ.NIC, 2017.
- M. Koucký: Poznámky k přednášce 2014-2015.
- M. Koucký: Poznámky k sufixovým polím z přednášky DS 2 - 2014.
- A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011.
- E. D. Demaine: Cache-Oblivious Algorithms and Data Structures, 2002.
- M. Thorup: High Speed Hashing for Integers and Strings. ArXiv 1504.06804, 2015.
- 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.
- R. Pagh: Cuckoo Hashing for Undergraduates. Lecture note, 2006.
- M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.
Cvičení
Cvičení jsou dvouhodinová. Zápočet se udílí za získání požadovaného počtu bodů za domácí úkoly řešené během semestru, detaily vysvětlí jednotliví cvičící.
Termíny cvičení:
První cvičení se konají v týdnu od 4. října.
Zkouška
Ke splnění předmětu je nutné získat zápočet a složit zkoušku. Zápočet se udílí za získání požadovaného počtu bodů za domácí úkoly řešené během semestru. Vzhledem k povaze domácích úkolů nejsou náhradní termíny zápočtu přípustné. Více viz cvičení.
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ů. Před zkouškou byste měli již mít hotový zápočet, ale na většinu termínů se lze zapsat i bez něj.
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, kterou by měl letos přednášet M. Mareš, dále seminář Implementace algoritmů a datových struktur
J. Finka a také Seminář z algoritmů a datových struktur vedený M. Marešem.