Zápis cvičení
11. 1.
Diskuse -- výsledky domácích úkolů.
21. 12.
Hashování:
skalární součin s aditivním členem je 2-nezávislý;
tabelace je 3-nezávislá;
tabelace není 4-nezávislá;
je-li systém k-nezávislý, je také (k-1)-nezávislý;
je-li systém 2-nezávislý, je také c-univerzální.
7. 12.
Komentáře k řešení Splay stromů, komentáře k tomu, co mělo být
vidět u Fibonacciho hald (k tomu ještě více příště).
Cache oblivious algoritmy: poznámky k úkolu transpozice matice,
merge dvou setřízených polí, binsearch, násobení matic jako motivace
pro Z-order (tam uděláno jak se adresuje, zmíněny některé vlastnosti a
použití).
Zmínka o debuggerech a možnostech debugování.
-
Nástroj
dot
pro kreslení grafů. Je to asi nejsnazší možnost kreslení
orientovaných grafů, kterou znám. Může se hodit pro ladění
datových struktur s pointery (například stromy, spojové
seznamy...). Další možnosti snadného kreslení jsou například TikZ
(příjemné kreslení v LaTeXu), který toho umí opravdu mnoho navíc:
čtivý tutoriál (cca 800 stran, ale vám bude stačit jen pár desítek).
-
Pokud nechcete vykreslovat datové struktury sami přímo v programu
můžete používat libovolný debugger. Doporučuji se podívat na DDD
(Data Display Debugger), jehož vzhled je sice poněkud zastaralý,
ale pořád má spoustu krásných vlastnosti (které nevím, nakolik
jsou unikátní). Například umí zobrazovat datové struktury
podobně, jako byste to dělali pomocí již zmíněného dot nebo
vykreslovat grafy z polí atd. Více obrázků na stránkách
ddd
nebo v
dokumentaci.
-
Poslední často přehlížený debugger, který má zajímavé vlastnosti
je starý známý gdb. Jako reklamu doporučuji talk z CppCon
Give me 15 minutes & I'll change your view of GDB.
9. 11.
Poznámky k řešením prvního úkolu.
Fibonacciho halda, která vytvoří jen cestu.
Posloupnost operací, pokud označujeme kořen: I1, I2, I3, DMAX, I3, I4, I5, DMAX, opakuj pro k = 1, 2, 3, ...: (Increase 2k+1 na 2k+3, I 2k+4, I 2k+5, DMAX).
Pokud neoznačujete kořen, snadnou úpravu si rozmyslete sami (nápověda: nechte increase až nakonec).
Na cvičení jsme si nerozmysleli, jestli se má označovat i kořen.
Ve skutečnosti je to jedno, na přednášce kořen nikdy neměl být označený a tím pádem je algoritmus v scanu poznámek nekonzistentní (funguje, ale neshoduje se s předpokladem).
Mimochodem označený kořen nám nevadí, mohli bychom ho zkusit odtrhnout od ničeho a tím mu značku smazat.
Ale nesmíme zapomenout odznačovat, když odtrhneme!
Příští pondělí budeme pravděpodobně konzultovat s kolegou potenciály v amortizaci.
Pokud se chcete přidat přijďte 20.11. v 17:20 na půdu (páté patro Malostranské budovy, zvoňte na doktorandi KAM).
26. 10.
Static finger theorem a working set theorem.
Nestihli jsme konstrukci optimálního vyhledávacího stromu, když máme dané pravděpodobnosti vyhledávání.
Zkuste si to vymyslet a případně se kouknout do kraťoučkého článku od
Knutha.
12. 10.
Příklady 1, 2, 3, hint na 4, 5, 6, komentáře ke zněním 12, 13 z následujícího
pdf.
Navíc byla intuitivní interpretace Shannonovy entropie.
Další zdroje informací:
Příklady:
- Příklad 4 -- stránka KSP,
- Příklad 5 -- strana 181 z Průvodce labyrintem algoritmů,
- Příklad 6 hint -- kořen odpovídá pivotu u quicksortu a levý podstrom rekurzení vlevo..., hloubka prvku odpovídá počtu jeho porovnání s pivoty a hloubka stromu odpovídá hloubce rekurze,
- Příklad 7 -- vyzkoušejte jednoduché a Splay-stromové rotace na cestu,
- Příklad 8 -- dynamické programování (jde zrychlit jednoduchou myšlenkou),
- Příklad 10 hint -- mohou si mé vyvažovací informace pamatovat mí potomci? (obdobně se dá udělat strom s dvěma pointery ve vrcholu, u kterého lze zjistit pointer na otce, levého syna i pravého syna),
- Příklad 11 -- Shannonova entropie viz předmět Michala Kouckého Základy přenosu a zpracování informace začátek aktualizovaných poznámek k přednášce (v sekci Literatura),
- Příklad 12, 13 -- poznámky k přednášce Martina Mareše.
- ostatní příklady přibudou, až budou odcvičeny i na ostatních paralelkách.