Lukáš Ondráček
Katedra teoretické informatiky a matematické logiky
ondracek@ktiml.mff.cuni.cz
Pracovna S207 (Malá Strana, 2. patro)
zpět na seznam předmětů

Cvičení z Datových struktur I, úterý 12:20, ZS 2020/2021

V zimním semestru 2020/2021 vedu cvičení k předmětu NTIN066, Datové struktury I.

Během distanční výuky mě můžete kontaktovat primárně výše zmíněným emailem, předmět prosím uvozujte [DS1].

V čase cvičení pak budeme využívat platformu Zoom, meeting ID pošlu emailem.
Účast na cvičení je nepovinná a půjde především o konzultace k probírané látce a zadaným úlohám.
Náplň cvičení tedy určujete hlavně svými dotazy.
První cvičení se bude konat až po přednášce, tj. v úterý 6. října.

Zápočet je možné získat za řešení domácích úkolů podle pravidel na samostatné stránce;
potřebný počet bodů byl navzdory pravidlům snížen na 60, zadáno bude jen 10 úkolů.
Úkoly budou zadávány prostřednictvím systému ReCodEx vždy se začátkem cvičení,
krátce před zadáním bude k dispozici také kostra řešení v gitovém repozitáři.
První úkol je již zveřejněn a je možné jej řešit do začátku cvičení 20. října;
další úkoly budou zadávány každý týden počínaje 13. říjnem a na jejich řešení budou dva týdny.

Podrobnější informace pošlu se začátkem semestru přihlášeným studentům emailem.


Níže se pokusím aspoň zmínit hlavní věci, na které jsme na cvičeních narazili.

24. 11. 2020

Řešení úkolů matrix_operation a matrix_experiment. Zbavovat se rekurze má smysl hlavně v případě, když to umíme bez explicitního zásobníku (nebo hrozí přetečení). Změna podmínek pro udělení zápočtu (méně úkolů), viz výše.

10. 11. 2020

Řešení úkolu ab_tree.

3. 11. 2020

Shrnutí podstatných částí řešení úkolu splay_experiment. Při vkládání grafů a jiného obsahu do dokumentů by měly být jejich popisky čitelné i v tištěné verzi, klidně můžou mít i stejnou velikost písma jako okolní text.

27. 10. 2020

Dvojrotace u splay stromů lze poskládat z jednoduchých, viz vzorové řešení splay_operation v ReCodExu (samostatná implementace dvojrotací může být i o 100 řádků delší). Voláním operace splay může strom i degradovat -- splay všech vrcholů ve vzestupném pořadí vytvoří cestu. Souvisí to s dotazem, na který jsem na cvičení neodpověděl, příště to můžu ukázat podrobněji. Vizualizaci B-stromů najdete např. zde, na stejném webu jsou podobně zpracovány i jiné datové struktury.

20. 10. 2020

Vzorové řešení prvního úkolu najdete v ReCodExu, další se tam objeví vždy po termínu. Hledání následníka od kořene vede na složitost projití všech prvků O(n log n), hledání od posledního vrcholu na O(n). Rekurze vs. cyklus: Příliš hluboká rekurze způsobuje přetečení zásobníku. Nemáme-li její hloubku dostatečně omezenou, je potřeba namísto rekurze použít cyklus. Např. vyvážený strom s garantovanou logaritmickou hloubkou můžeme procházet rekurzivně, ale strom, který může mít i tvar cesty, ne. Cyklus je taky obecně rychlejší než rekurze. Je proto doporučený aspoň v případě, kdy nezpůsobí jeho použití výrazné zesložitění kódu vůči rekurzi. C++ v některých případech umí rekurzi převést na cyklus (tzv. tail recursion), ale závisí to na spoustě věcí, mj. i na parametrech kompilace. Komentáře v kódu: Je dobré komentovat části, které by mohly být nejasné, ale není nutné komentovat úplně vše. Např. komentář `je-li A nula, nastavíme jej na jedničku` následovaný zmíněnou podmínkou, nepřináší žádnou novou informaci a kód zbytečně prodlužuje. V některých jazycích/projektech je zvykem komentovat třeba i každý parametr sebemenší funkce. Tady nic takového vyžadovat nebudu, komentujte prosím smysluplně. Je-li kód dostatečně přehledný, může se obejít i bez komentářů. Ještě bych doporučil při úpravách kódu upravit i komentáře, kterých se změny týkají; např. vyřešená TODO už nejsou potřeba. Staticky optimální binární vyhledávací strom: Máme daný seznam prvků -- budoucích vrcholů --, jejichž pořadí musíme zachovat, spolu s četnostmi přístupů k nim. Součet součinů hloubky vrcholu a počtu přístupů k němu přes všechny vrcholy, tedy to, kolik toho ve stromě nachodíme, nám udává jeho celkovou cenu a chceme najít strom, který ji minimalizuje. Pro danou souvislou podposloupnost (interval) vstupních prvků najdeme optimální strom vyzkoušením všech možných kořenů, pod něž připojíme optimální stromy příslušných podintervalů nalevo a napravo od něj. Dynamickým programováním sestrojíme optimální stromy všech intervalů od nejmenších. Pro každý začátek a konec intervalu (od nejmenších) vyzkoušíme všechny vrcholy uvnitř jako kořeny. Tím získáme při vhodné reprezentaci dat kubický algoritmus. Zlepšení na kvadratický algoritmus: Pro interval (i, j) se kořen nemůže nacházet před kořenem (i, j-1) ani za kořenem (i+1, j). Testujeme tedy jen tyto vrcholy jako kořeny. Pro všechny intervaly dané délky je jich dohromady O(n).

13. 10. 2020

Coding-style: Na webu je spoustu protiřečících si pravidel. Hlavní je konzistence v rámci projektu, tedy je třeba se přizpůsobit při úpravách cizích kódů. Především doporučuji psát názvy ve stejném jazyce a používat stejně odsazování pomocí mezer/tabulátorů. Každý může mít jinou šířku tabulátoru a při nekonzistentním míchání s mezerami se odsazení může rozbít. (V hodnoceních úkolů na podobné věci upozorním, body nestrhávám.) Jak správně používat splay: Provedeme-li ve stromě k jednotkových operací, které nemají vliv na potenciál (např. hledání prvku), a chceme, aby měly amortizovanou složitost O(log n), musíme provést splay, který reálně provede O(k) operací. Při operaci splay se z potenciálu uvolní tolik jednotek času, kolik potřebuje na všechny rotace, přeškálováním potenciálu pak i libovolný konstantní násobek. Když tedy např. zavoláme splay na prarodiče vyhledaného vrcholu, je to v pořádku a bude nás to i s vyhledáním stát amortizovaně O(log n) + 2 kroky navíc, tedy pořád O(log n). Provádíme-li nějakou změnu ve stromě, je potřeba zajistit, aby se změny potenciálu ve všech předcích nenasčítaly na více než O(log n) (chceme-li dosáhnout této časové složitosti). Drobné změny lze typicky provádět kdekoliv, větší změny jen u kořene. (V konkrétních případech je potřeba si ověřit maximální změnu potenciálu výpočtem.) Příkladem větší operace je spojení dvou stromů (join) A a B, v nichž všechny prvky A jsou menší než prvky B. Připojení A pod nejmenší prvek B může být drahé; připojení A pod kořen B po splayi minima B ovlivní potenciál jen v kořeni B a celkový potenciál (resp. součet potenciálů obou stromů) se změní jen logaritmicky.