Okomentova Koubkova skripta

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Okomentova Koubkova skripta

Příspěvek od Him »

Ahoj,

pracoval jsem pomerne dlouho na komentovani Koubkovych skript. Mezitim p. Koubek vydal knihu, ktera obsahuje daleko mene chyb a je asi ctenari i blizsi. Presto skripta jsou kratsi a kniha obsahuje vic nez je potreba na zkousku.

Pozn. k prohlizeni: Komentare jsou pridavany rovnou do PDFka, pouzivam prohlizec PDF XChange Viewer (http://www.tracker-software.com/product ... nge-viewer), ale komentare mi zobrazil i posledni Adobe Acrobat X, tak snad nebudou problemy se zobrazenim (na Windows verim, ze nebudou, na Linuxu nevim a nemam uz silu neco testovat).

Disclaimer: Komentare mohou byt spatne, pripadne zavadejici, obcas lehce infantilni, kdyz jsem na to koukal jak z jara apod. Neplanoval jsem, ze to nekdy nekam umistim, rozhodl jsem se tak proto, ze par lidi, kterym jsem to jiz posilal, tak se zdali, ze jim to pomohlo.

PS: Nahlášení chyb je vítané! A libovolný jiný feedback také!
Přílohy
KoubekVaclav_Stromy.pdf
Stromy
(2.39 MiB) Staženo 976 x
KoubekVaclav_Hasovani_original.pdf
Hashovani
(2.12 MiB) Staženo 837 x
KoubekVaclav_Haldy_updated.pdf
Haldy
(1.66 MiB) Staženo 751 x
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: Okomentova Koubkova skripta

Příspěvek od blabla »

toto mi pride celkom spravne miesto na vznesenie mojej otazky. nie je nahodou zlozitost operacie "merge" pre leftist haldu v knihe zle?

v knihe sa pise:
protoze pocet rekurzivnich volani je roven souctu delek pravych cest v haldach T1, T2 reprezentujicich mnoziny S1, S2, vyzaduje algoritmus MERGE cas O(log(|S1| + |S2|))
mne osobne to ale pride ako uplne protichodne tvrdenie... ved "soucet delek pravych cest" by mal byt skor log(|S1|) + log(|S2|), no nie?? ale mozno znova len nieco prehliadam :)
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Okomentova Koubkova skripta

Příspěvek od peci1 »

blabla píše:toto mi pride celkom spravne miesto na vznesenie mojej otazky. nie je nahodou zlozitost operacie "merge" pre leftist haldu v knihe zle?

v knihe sa pise:
protoze pocet rekurzivnich volani je roven souctu delek pravych cest v haldach T1, T2 reprezentujicich mnoziny S1, S2, vyzaduje algoritmus MERGE cas O(log(|S1| + |S2|))
mne osobne to ale pride ako uplne protichodne tvrdenie... ved "soucet delek pravych cest" by mal byt skor log(|S1|) + log(|S2|), no nie?? ale mozno znova len nieco prehliadam :)
Taky mi to tak prijde! Jenze to je vazne rozdil, ptz. ve druhem pripade by se to taky dalo chapat jako log( |S1| * |S2| ) !
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Okomentova Koubkova skripta

Příspěvek od peci1 »

Dalsi otazka, ktera neni ve skriptech jasne vyresena.

Kdyz mam hashovani s premistovanim/2 ukazateli/srustajici, tak hojne vyuzivam proceduru "vloz na libovolny prazdny radek". V zaveru kapitoly se pise, ze na prazdne radky je nejlepsi mit zasobnik. Ten mi ale zvedne pamet. narocnost o konst. * m. Pritom to nikde neni zminene (jasne, ono se to schova, ale kdyz uz si hrajeme na presne vypocty...)

Nebo mate nekdo jiny napad?
cunav5am
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 4. 6. 2007 09:37
Typ studia: Informatika Mgr.

Re: Okomentova Koubkova skripta

Příspěvek od cunav5am »

:D Asi o tom nikdo zatím neví, až dnes je odkaz z matfyzácké wiki...

Dal jsem dohromady polo-oficiální zápisky v angličtině, určené původně/především pro studenty kteří neumějí česky, ale za to jsou úplné (kromě 2-4 nejdelších důkazů), rozumně vyTeXované a snad s méně chybami a více nadhledem ;-) Stále upravuji a vylepšuji, jakékoliv komentáře uvítám (kontakt je v kořeni odkázaného webu).
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: Okomentova Koubkova skripta

Příspěvek od Donarus »

WOW, to vubec nevypada zle .. tak ja ti je rovnou otestuju .. :)
Odpovědět

Zpět na „TIN066 Datové struktury I“