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
Zk. 27.6. Hric
- 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
Aurë Entuluva!!
- Void
- Matfyz(ák|ačka) level II
- Příspěvky: 54
- Registrován: 17. 1. 2006 16:21
- Typ studia: Informatika Mgr.
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).Jakobicek píše:hm snazim se vymyslet tu sumu s logaritmem a nejde mi to ...
mohl by to nekdo nastinit... prosim
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?
Aurë Entuluva!!