Zk. 27.6. Hric

Uživatelský avatar
Void
Matfyz(ák|ačka) level II
Příspěvky: 54
Registrován: 17. 1. 2006 16:21
Typ studia: Informatika Mgr.

Zk. 27.6. Hric

Příspěvek od Void »

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 :)
Aurë Entuluva!!
Jakobicek
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Typ studia: Informatika Bc.
Bydliště: Praha... VSE/MATFYZ

Příspěvek od Jakobicek »

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:
Minsk will lead with blade and sword Boo will sort out the details
Uživatelský avatar
Void
Matfyz(ák|ačka) level II
Příspěvky: 54
Registrován: 17. 1. 2006 16:21
Typ studia: Informatika Mgr.

Příspěvek od Void »

Jakobicek píše: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).
Aurë Entuluva!!
Jakobicek
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Typ studia: Informatika Bc.
Bydliště: Praha... VSE/MATFYZ

Příspěvek od Jakobicek »

uf.... ja jsem lama :oops: uz je mi to jasne... spletl jsem si to s jinou podobnou radou... 8)
Minsk will lead with blade and sword Boo will sort out the details
Odpovědět

Zpět na „2005“