# Zk. 27.6. Hric

<{ForumPost(poster="Void", timestamp=2006-06-27 12:57:54)}>
Tak dnesni pisemka se mi nezdala tezka co se tyce nutnych znalosti, posudte sami:  
  
1) a) popis odebirani prvku z AVL stromu  
    b) popis pridavani prvku do B stromu  
  
2) a) dokazte nebo vyvratte: f(n) = o(h(n)) & g(n) = o(h(n)) =>   
                                                                   f(n) + g(n) = o(h(n))  
    b) dokazte: suma_{i=0}^{log n} i * n/(2^i) je pro n ve   
        tvaru 2^k rovna O(n)  
  
3) a) Mate dve setridene posloupnosti cisel, kazdou delky n. Pomoci   
        metody divide et impera vynalezt algoritmus, ktery rekurzivne   
        najde spolecny median. Behem jednoho kroku vyloucit kolem pulky   
        cisel.  
    b) Sestavit rekurentni vzorecek pro slozitost algoritmu z a). Pomoci MT   
        nebo subs asymptoticky odhadnout jeho slozitost.  
  
Tak ted uz jen ustni, tak doufam, ze dostanu spodni odhad trideni nebo neco takovyho :)
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2006-06-27 14:23:16)}>
hm snazim se vymyslet tu sumu s logaritmem a nejde mi to :cry: ...  
mohl by to nekdo nastinit... prosim  :wink:  
domnival jsem se ze rada suma i={1..n} i/2^i roste stejne rychle jako n  
pak by ovsem ta rada musela byt O(n log n),kde jsem se zmylil? :cry:
<{/ForumPost}>

<{ForumPost(poster="Void", timestamp=2006-06-28 11:01:56)}>

 > Jakobicek wrote:hm snazim se vymyslet tu sumu s logaritmem a nejde mi to :cry: ...  
 > mohl by to nekdo nastinit... prosim  :wink:  
 > domnival jsem se ze rada suma i={1..n} i/2^i roste stejne rychle jako n  
 > pak by ovsem ta rada musela byt O(n log n),kde jsem se zmylil? :cry:

Ja teda u ustniho zjistil, ze pisemku jsem mel prakticky bez chyby a k ty sume tam bylo tohle: suma i={1..n} i/2^i absolutne konverguje podle podilovyho kriteria, to znamena, ze castecny soucty konvergujou k nejakymu cislu, takze existuje nejaky vetsi cislo, ktery je vetsi nez ta suma, at ma kolik chce clenu. Takze je to n*suma <= n* const = O(N).
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2006-06-28 19:52:22)}>
uf.... ja jsem lama :oops: uz je mi to jasne... spletl jsem si to s jinou podobnou radou...  8)
<{/ForumPost}>