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.