(a,b) strom - veta 3.18

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

(a,b) strom - veta 3.18

Příspěvek od blabla »

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?
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: (a,b) strom - veta 3.18

Příspěvek od Him »

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.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: (a,b) strom - veta 3.18

Příspěvek od blabla »

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 :?
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: (a,b) strom - veta 3.18

Příspěvek od Him »

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 ;)
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: (a,b) strom - veta 3.18

Příspěvek od blabla »

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
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: (a,b) strom - veta 3.18

Příspěvek od Him »

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 ;-)
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
deusex

Re: (a,b) strom - veta 3.18

Příspěvek od deusex »

(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
Odpovědět

Zpět na „TIN066 Datové struktury I“