Zk. 27.6. Hric

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

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:

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 nsuma <= n const = O(N).

uf.... ja jsem lama :oops: uz je mi to jasne... spletl jsem si to s jinou podobnou radou... 8)