(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ů.

(a,b) strom - veta 3.18

Příspěvekod 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?
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ěvekod 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.
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 ;)
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ěvekod 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 :?
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ěvekod 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 ;)
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 ;)
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ěvekod 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
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ěvekod 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 ;-)
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 ;)
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ěvekod 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
deusex
 


Zpět na TIN066 Datové struktury I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron