Okomentova Koubkova skripta

[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é!

[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]

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]

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]

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

[Donarus]

WOW, to vubec nevypada zle .. tak ja ti je rovnou otestuju ..