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ů.

Okomentova Koubkova skripta

Příspěvekod Him » 13. 2. 2012 15:25

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) 506 krát
KoubekVaclav_Hasovani_original.pdf
Hashovani
(2.12 MiB) 411 krát
KoubekVaclav_Haldy_updated.pdf
Haldy
(1.66 MiB) 393 krát
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 ;)
Him
Supermatfyz(ák|ačka)
 
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Okomentova Koubkova skripta

Příspěvekod blabla » 14. 2. 2012 00:28

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 :)
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ěvekod peci1 » 23. 5. 2013 17:04

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ěvekod peci1 » 23. 5. 2013 17:14

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?
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ěvekod cunav5am » 16. 1. 2014 20:17

: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).
cunav5am
Matfyz(ák|ačka) level I
 
Příspěvky: 16
Registrován: 4. 6. 2007 08:37
Typ studia: Informatika Mgr.
Login do SIS: cunav5am

Re: Okomentova Koubkova skripta

Příspěvekod Donarus » 19. 1. 2014 00:47

WOW, to vubec nevypada zle .. tak ja ti je rovnou otestuju .. :)
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
 
Příspěvky: 194
Registrován: 30. 9. 2007 11:40
Typ studia: Informatika Mgr.
Login do SIS: palut7am


Zpět na TIN066 Datové struktury I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků

cron