Přednáška z Datových struktur I (NTIN066)

úterý od 9:00 v S5, ZS 25/26

„Ranní ptáče dál doskáče.“

Stránka přednášky Pavla Veselého z Datových struktur I, kde budeme probírat pokročilé techniky pro návrh a analýzu datových struktur a některé jejich praktické aspekty (např. chování ke keším procesoru). Představu o přednášce si můžete udělat z loňské přednášky Jirky Finka.

Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po přednášce. Také budu rád, když se během cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi emailem nebo před/po přednášce. Někdy mě můžete též najít v kanceláři S326 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře naproti učebně S3), ale je lepší se ozvat předem.

Pokud nemůžete přijít (nemoc, izolace, ...), pusťte si stream (pokusím se zprovoznit), podívejte se na záznam (podaří-li se ho pořídit) nebo si nastudujte příslušnou část skript (viz odkazy na sekce níže).

Cvičení povedou: Jirka Fink, Petr Chmel, Pavel Veselý. (Poznámka: o naplnění kapacity víme. Jelikož do S7 se už víc lidí nevejde, zapisujte se prosím do fronty na cvičení v S1.)

Podmínky zápočtu a pravidla. Zkouška bude ústní s písemnou přípravou z teorie z přednášky, bližší informace budou v prosinci.

Co jsme dělali / plán

U každého tématu jsou odkazy do skript. Na záznamech je hlavně tabule, slajdy najdete níže (objeví se vždy před přednáškou).

30. 9.	Úvodní informace o předmětu. Amortizace: nafukovací pole (analýza agregací) a binární počítadlo (tři důkazy: agregací, penízkovou metodou a potenciálem). Zavedení amortizované složitosti pomocí potenciálů. Dynamické pole, tedy implementace zásobníku polem (nedokončeno, jen naznačen potenciál, zbytek na cvičení). Slajdy a záznam (bohužel se ne vždy pořadilo správně natočit kameru, někdy je tedy tabule se zpožděním). Hlavní zdroje: [P 9.1-9.3] a [L 1.1-1.3].
7. 10.	Zaskočil Petr Chmel: Amortizace a stromové datové struktury pro uspořádané množiny: Líně vyvažované stromy (BB[alfa]) a samovyvažovací (Splay stromy), konkrétně operace Splay a analýza jeji amortizované ceny. Slajdy (skončili jsme na slajdu 23), záznam se objeví. Vizualizace splay stromů. Tahák na splay stromy od Ondry Mičky. Hlavní zdroje: [P 9.4-9.5] a [L 1.4, 2.1], též [ST]
14. 10.	Plán: dokončení Splay stromů (operace pomocí Splaye a pokročilé vlastnosti). (a,b)-stromy: operace a amortizovaná analýza.

Literatura, zdroje, odkazy, videa, ...

• [L] Martin Mareš: Lecture notes on data structures. Skripta pokrývající naprostou většinu přednášky.
• [P] Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, CZ.NIC. Hodí se mít druhé vydání, ale kniha je dostupná online. Kniha nepokrývá celou přednášku, ale naopak obsahuje spoustu základních DS, na kterých budeme stavět.
• Stránka loňské přednášky Jirky Finka včetně prezentací
• Stránka předloňské přednášky Martina Mareše včetně videozáznamů
• Přednáška Michala Kouckého z roku 2021 (poznámky a videa)
• [CO] Erik Demaine: Cache-Oblivious Algorithms and Data Structures
• [E] Erik Demaine: přednáška Advanced Data Structures z MIT
• [G] Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry – Algorithms and Applications. ISBN 978-3-540-77973-5.
• [H] Handbook of Data Structures and Applications (dostupné online ze sítě MFF)
• [M] Kurt Mehlhorn: Data Structures and Algorithms (digitální verze knihy)
• [ST] Sleator, Tarjan: Self-Adjusting Binary Search Trees, Journal of the ACM, 1985
• [ST2] Sleator, Tarjan: Amortized Efficiency of List Update and Paging Rules, Communicatons of the ACM, 1985
• [T] Mikkel Thorup: Lecture Notes on Linear Probing with 5-Independent Hashing
• [T2] Mikkel Thorup: High Speed Hashing for Integers and Strings
• Navazující předměty: Datové struktury 2 (v LS), Vybrané kapitoly z datových struktur (M. Mareš, bude se umouvat), Implementation of Algorithms and Data Structures (J. Fink), Proudové algoritmy pro velká data (P. Veselý, bude se umouvat)
• Animovaný výklad algoritmů v Algovision od prof. Luďka Kučery

Zdroje k úkolům:

• Úkoly se odevzdávají v recodexu
• Zadání úkolů a šablony zdrojových kódů jsou v repozitáři na GitLabu
• Vzorové řešení experimentálního úkolu (pro nafukovací pole)
• Nápověda k programovacím jazykům: C++ tutorial, C++ reference, Python doc

Další videa:

• YouTube kanál Bena Langmeada – pokročilé datové struktury pro řetězce (sufixová pole, BWT a FM index)

Další knihy v angličtině:

• Dasgupta, Papadimitriou, Vazirani: Algorithms
• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd Edition), Mc Graw Hill 2001 (pozor na to, že používají jinou definice červeno-černých stromů a jsou tam i další rozdíly oproti definicím běžně používaným na MFF)

Podmínky zápočtu a pravidla

Zápočet bude za zisk alespoň 75 bodů z úkolů v recodexu. Zadáme alespoň sedm implementačních úkolů po 10 bodech a alespoň tři experimentální po 15 bodech, tedy půjde získat alespoň 115 bodů (a nějaké bonusové navíc). Na každý úkol budou alespoň dva týdny (ke konci semestru více).

Implementační úkoly:

• Dostanete částečnou implementaci datové struktury.
• Máte za úkol implementovat chybějící části. Původní části můžete upravovat.
• Úkol je testován automaticky, testovací data jsou veřejná.
• Cvičící si prohlédne váš program a případně koriguje bodové ohodnocení.
• Lze řešit v C++ a (obvykle) také v Pythonu.

Experimentální úkoly

• Cílem je změřit chování zadané implementace struktury.
• Odevzdáváte zprávu s naměřenými hodnotami a diskusí (jako PDF).

Všeobecná pravidla

• O úkolech můžete diskutovat s ostatními, ale nesdílejte s nimi své programy ani zprávy (ukázat je přednášejícímu nebo cvičícímu samozřejmě můžete).
• Nesdílejte vzorová řešení úkolů s lidmi mimo vaši skupinu.
• Termíny jsou pevné.
• Před termínem můžete své řešení odevzdávat vícekrát, platí maximum získaných bodů.
• Program musí projít všemi testy.
• Kvalita vašich programů a zpráv se promítá do hodnocení.
• Musíte rozumět všemu, co odevzdáte. Cvičící nebo přednášející může vyžadovat osobní vysvětlení odevzdaného kódu nebo řešení experimentálního úkolu, aby udělil body.
• V programovacích úkolech nepoužívejte netriviální kód, který jste nenapsali sami. To zahrnuje cizí implementace datových struktur a jiné než zřejmé knihovní funkce. Triviální rostoucí pole (std::vector v C++ nebo list.append() v Pythonu) je ještě v pořádku, ale cokoliv složitějšího už ne. Pokud si nejste jistí, poraďte se s cvičícím.
• Text v experimentálních úkolech pište sami.
• Všechny matematické věty, které použijete ve svých zprávách, je potřeba precizně formulovat a citovat jejich zdroj. Pokud věta zazněla na přednášce, stačí citovat přednášku.
• Pokud jste se kdekoliv inspirovali, citujte všechny zdroje. Chybějící citace jsou (nejen zde) považovány za významný prohřešek proti akademické etice.
• Pokud se rozhodnete použít jinou verzi datové struktury, než zazněla na přednášce, čeká se od vás důkaz, že také má požadované vlastnosti.