☰

Datové struktury I

sudý kalendářní týden, čtvrtek 17:20, místnost S8

přednáší Martin Mareš

Zápis cvičení

5. 10.

Příklady na stromy, viz: pdf.

19. 10.

Splayování na levé cestě -- klasické vs. dvoj- rotace, optimální strom pro dané pravděpodobnostní rozložení, Static Finger Theorem a nakousnut Working Set Theorem: pdf.

2. 11.

Rozbor prvních domácích úkolů a upozornění na nejčastější problémy v nich.

16.11

Paralelní (a,b)-stromy, převod červenočerných na (2,4)-stromy a opačně, tvorba označené cesty ve Fibonacciho haldách, zopakování amortizace u Fibonacciho hald, dolní odhad omega(odmocnina z n) pro případ neoznačování vrcholů jimž byl odtržen list.

20. 11. (konzultace)

V pondělí 20.11. 17:20 plánujeme konzultovat potenciály v amortizaci. Pokud se chcete přidat přijďte v danou hodinu na půdu (páte patro Malostranské budovy, zvoňte na doktorandi KAM.)

30. 11.

Cache oblivious algoritmy - slévání polí, binární vyhledávání, quicksort, Z-order matice, indexování, analýza počtu výpadků při rekurzivním násobení.

14. 12.

Hešovací funkce: skalární součin s aditivním členem je 2-nezávislý, tableace je 3-nezávislám tabelace není 4-nezávsilá, je-li systém k-nezávislý je i (k-1) nezávislý, 2 nezávislý je také c-univerzální

4. 1.

Rozbor třetího a čtvrtého domacího úkolu, kukaččí hešování na místě. Dokončení příkladů na hešovací funkce.

K příkladům ze cvičení

Další zdroje informací:

Splay stromy:
naskenované poznámky od Martina Mareše,
Průvodce labyrintem algoritmů,
samozřejmě původní článek od Sleatora a Tarjana,
lekce 5 od E. Demaine.

Příklady -- Splay stromy:
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.
Příklady -- Fibonacciho haldy:
Posloupnost operací tvořící označenou cestu: I -1, I -2, I -3, E, I -3, I -4, I -5, E, I -5, I -6, I -7, E, I -7, I -8, I -9, E, opakuj pro i=0,...,k (D -6-4i na -10-4i, I -11-4i, I -12-4i, I -13-4i, E). Tato posloupnost, kde I je Insert, E je ExtractMin a D je DecreaseKey, vytvoří neoznačený hřeben (cesta, na které je na každém vrcholu přivěšen jeden list. Odtržením těchto listů dostaneme požadovanou označenou cestu
Dolní odhad při neoznačování vrcholů lze nalézt v článku Replacing Mark Bits with Randomness in Fibonacci Heaps (Jerry Li, John Peebles)

Podmínky zápočtu

Za domácí úkoly viz stránky přednášky

Užitečné odkazy
Stránky přednášky: MJ s dalšími odkazy.
Stránky přednášky z minulých let k nalezení na: Michal Koucký a Jirka Fink (minulý rok + současná anglická paralelka).
Zajímavý pokus o interaktivní učení: http://tutor.fi.muni.cz/. Po přihlášení zde jsou dostupné interaktivní příklady na lineární zobrazení v rovině (a také afinní zobrazení). Obsahuje celou řadu dalších typů úloh. Přihlášením podporujete výzkum učení!
Jestli se chcete naučit psát hezky matematiku, zkuste se podívat na LaTeX. Pro kreslení obrázků se bude hodit například program ipe. LaTeX můžete psát i online například na sharelatex. V případě zájmu vytvořím nějaký ukázkový soubor.

Veronika Slívová