(a,b) strom - veta 3.18

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: (a,b) strom - veta 3.18

Re: (a,b) strom - veta 3.18

od deusex » 29. 1. 2014 17:34

(k+1)a <= kb me osvitilo dopoledne pred zkouskou, neni to nejpresneji, myslenka je ale podle me nasludejici:

Pro jednotlivy intervaly poctu listu indukci dokazujes, ze pro hodnoty n mezi nima umis sestrojit strom. Tady rikas, (k+1) a je tady leva mez intervalu v k+1 -té hladině a kb je pravá mez k-té hladiny. Tzn. tam musí existovat alespoň jednoprvkový překryv mezi intervalama.

Graficky:

Kód: Vybrat vše

----------] k*b
        [------ (k+1)a

Re: (a,b) strom - veta 3.18

od Him » 13. 2. 2012 21:30

Ja mam knihu doma, takze sis trochu pridelal praci ;)
btw to co nie je v skriptach sa na skusku netreba ucit?! no to mi ani nehovor
Nu, ja na prednasky nechodil, ale minule roky kniha nebyla a vzdy to stacilo, podle me to stezovat nebude, kdyz uspesnost zase tak velika neni.

Jinak opravdu nevim, co tim mel Koubek na mysli, muzes se ho zitra zeptat ;-)

Re: (a,b) strom - veta 3.18

od blabla » 13. 2. 2012 21:22

btw to co nie je v skriptach sa na skusku netreba ucit?! no to mi ani nehovor :D

a ano, presne to, co vravis ty by som ocakaval, ze bude chciet dokazat, teda:
2*a^(h-1) <= b^(h-1)

ale to ako mi ma pomoct "k>= 2 je (k+1)a <= kb" pri dokazani tohto vztahu je ten bod, ktory mi unika :) koubek v tom dokaze oznacuje "k" ako pocet listov, tak neviemako nam indukcia skrz listy pomoze.. no ale ja mam pocit ze mi unika len nejaky elementarny fakt. do prilohy som dal odfotenu vetu aj s dokazom:
dokaz.jpg

Re: (a,b) strom - veta 3.18

od Him » 13. 2. 2012 21:07

Vzhledem k tomu, ze ten dukaz neni ve skriptech, tak jsem se ho neucil. Nicmene koukal jsem na to a o co se snazi je jasne, jde o to dokazat indukcni krok. Zjednodusene ti na kazdem patre rika, ze mas pocet listu mezi dvema zavorami. A asi se snazi dokazat, ze se nestane:

leva-zavora-na-patre-x ... prava-zavora-na-patre-x < leva-zavora-na-patre-(x+1) ... prava-zavora-na-patre-(x+1)

proto to (k+1)a.

Jinak si to vysvetlit neumim, ale klidne se ohrad, pokud rikam blbost ;)

Re: (a,b) strom - veta 3.18

od blabla » 13. 2. 2012 20:27

vdaka, zrejme to tak bude. aj tak som ale asi debil, lebo dosiel som v tom dokaze po cast:
Protoze pro k>= 2 je (k+1)a <= kb, dostavame indukci, ze pro kazde kladne cele cislo n existuje (a,b) strom presne s n listy.
a absolutne nechapem co vlastne ta nerovnost vyjadruje, neviem si to povedat vlastnymi slovami. tym padom ani nechapem ako sme na zaklade toho vobec nieco dokazali :?

Re: (a,b) strom - veta 3.18

od Him » 13. 2. 2012 07:31

Kdyz pracujes [delas operace Insert, Delete, Member,...] s (a,b)-stromem, tak si chces vybrat konkretni hodnoty a a b podle sve preference. A Koubkova veta ti rika, ze pro tato a a b muzes reprezentovat libovolnou mnozinu S o velikosti |S|=n.

To je daleko silnejsi tvrzeni nez ze existuje nejaky (a,b)-strom, ktery ma n listu, s tim by se nedalo pracovat, protoze po insertu/delete bys mohlo dojit k tomu, ze je potreba predelat (a,b)-strom na jiny (a,b)-strom.

Takhle jsem to pochopil ja.

(a,b) strom - veta 3.18

od blabla » 12. 2. 2012 23:21

v koubkovej knihe na strane 191 sa nachadza veta 3.18, ktora znie:
mejme prirozena cisla a a b takova, ze a >=2, b >= 2a + 1. Pak pro kazde kladne cislo n existuje (a,b) strom, ktery ma presne n listu....
Veta este pokracuje dalej, no mna zaujima iba tato cast. V knihe je dokazu tohto tvrdenia venovany pomerne velky priestor. Mne to ale pride uplne zbytocne dokazovanie, teda ak to dobre chapem... Nestacilo by pre konkretne n zaviest strom (2,n) ?? Ved ten moze mat urcite n listov a tym by bolo tvrdenie dokazane...

Nieco mi unika, alebo preco je tam k tomu taky zbytocne zlozity dokaz? Co si o tom myslite?

Nahoru