Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
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
Offline
a) První krok: Dokazuji pro . je uzel, obsahuje vrcholů, tvrzení pro tedy platí.
Indukční krok: Předpokládáme, že tvrzení platí pro . obsahuje všechny vrcholy dvou stromů (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 . Tím jsem tvrzení dokázal pro . 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.
Offline
↑ 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 :((((
Offline
Indukční krok: Předpokládáme, že pro tvrzení platí, tedy strom má výšku . Když budeme sestrojovat strom , sestavujeme ho ze dvou , jejichž výška je dle indukčního předpokladu . Strom sestavujeme tak, že na kořen prvního stromu napojíme jako levého potomka kořen druhého stromu . Výška toho druhého stromu je dle předpokladu . Napojení kořenů zvětší výšku výsledného stromu o jedna. Proto bude výška stromu rovna .
Offline
Stránky: 1