Matematické Fórum

tmoe · 07. 05. 2010 12:13

Zdravím, opět mám velké problémy s dokazováním idukcí a tak prosím o pomoc. Zkouška by pak byla pro mě jednodušší.

Víme, že binomiální halda je les binomiálních stromů. Označme B_k binomiální
strom řádu k (tj. jedná se o uzel, jehož potomci jsou všechny B_{k-1}, ...,
B_0) Tj. B_0 je samotný uzel a B_i vznikne ze dvou stromů B_{i-1} tak, že ten
první napojíme jako levého potomka kořenového uzlu toho druhého stromu.

Dokažte:
a) že B_k obsahuje právě 2^k vrcholů.
b) B_k má výšku právě k

Moc díky za přesný formální zápis, v tomhle strašně plavu

tmoe · 08. 05. 2010 21:41

↑ tmoe: opravdu mi tady nikdo neporadi?

Pavel Brožek · 08. 05. 2010 22:02

a) První krok: Dokazuji pro $k=0$ . $B_0$ je uzel, obsahuje $1=2^0$ vrcholů, tvrzení pro $k=0$ tedy platí.
Indukční krok: Předpokládáme, že tvrzení platí pro $k$ . $B_{k+1}$ obsahuje všechny vrcholy dvou stromů $B_{k}$ (které nemají žádné vrcholy společné) a žádný jiný, počet jeho uzlů tedy bude součtem počtu uzlů těch dvou stromů, tedy $2^k+2^k=2\cdot2^k=2^{k+1}$ . Tím jsem tvrzení dokázal pro $k+1$ . Důkaz matematickou indukcí je tak dokončen.

b) Nezkusíš to teď ty? Pak to někdo určitě zkontroluje, připíše připomínky.

tmoe · 10. 05. 2010 20:49

↑ BrozekP:ok takze zkusim to b) Indukcni baze: dokazuji pro k=0. B_0 je samotny uzel, jeho vyska je tedy 0 = k. Tvrzeni pro k = 0 tedy plati.

Indukcni predpoklad: predpokladame, ze tvrzeni plati pro k. B_k+1 ma vysku stromu B_k + 1. aaaaaaa a uz sem se v tom ztratil a neumim s tim hnout :((((

Pavel Brožek · 10. 05. 2010 21:09

Indukční krok: Předpokládáme, že pro $k$ tvrzení platí, tedy strom $B_k$ má výšku $k$ . Když budeme sestrojovat strom $B_{k+1}$ , sestavujeme ho ze dvou $B_k$ , jejichž výška je dle indukčního předpokladu $k$ . Strom $B_{k+1}$ sestavujeme tak, že na kořen prvního stromu $B_k$ napojíme jako levého potomka kořen druhého stromu $B_k$ . Výška toho druhého stromu je dle předpokladu $k$ . Napojení kořenů zvětší výšku výsledného stromu o jedna. Proto bude výška stromu $B_{k+1}$ rovna $k+1$ .

tmoe · 10. 05. 2010 21:11

↑ BrozekP:diky moc, jsem ti zavazan

Matematické Fórum

#1 07. 05. 2010 12:13

matematicka indukce

#2 08. 05. 2010 21:41

Re: matematicka indukce

#3 08. 05. 2010 22:02

Re: matematicka indukce

#4 10. 05. 2010 20:49

Re: matematicka indukce

#5 10. 05. 2010 21:09

Re: matematicka indukce

#6 10. 05. 2010 21:11

Re: matematicka indukce

Zápatí