Matematické Fórum

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
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 28. 08. 2017 22:56

kocourOggy
Příspěvky: 28
Pozice: student
Reputace:   
 

Trable s indukcí podruhé - ekvivalence definic binomiálních stromů

1.definice: Binomiální strom T řádu k (značíme Tk) je zakořeněný strom, pro který platí následující:
    a) strom T0 (řádu 0) obsahuje pouze kořen
    b) strom Tk pro k > 0 má kořen, který má právě k synů, přičemž tito synové jsou zároveň kořeny binomiálních stromů po řadě T0, T1 až Tk−1.

2.definice: Zakořeněné stromy Bk jsou definovány takto:   
    a) pro k = 0 B0 obsahuje pouze kořen
    b) pro k > 0 se Bk skládá ze stromu Bk−1, pod jehož kořenem je napojený další strom Bk−1.

Hezky rozdílnost definic znázorňuje obrázek:
http://forum.matematika.cz/upload3/img/2017-08/53464_binomialTree.png


Dokažte ekvivalenci definic... (důkazy jsou uvedeny přímo ve studijních materiálech, ale jednotlivým krokům zcela nerozumím)

Důkaz Tk => Bk. Matematickou indukcí podle k.
    Pro k = 0 tvrzení zjevně platí (jasný... Tk i Bk jsou dle svých definic pouze kořeny)
    Pod kořenem stromu Tk jsou dle 1. definice zavěšeny stromy T0, . . . , Tk−1 (jasný... jen jsem přečetl definici)
    Odtržením posledního podstromu S = Tk−1 od Tk však dostáváme strom Tk−1 (jasný... stále se stačí striktně držet 1.definice, že když mám strom Tk, kterému chybí jeho Tk-1 syn, tak jsem vlastně dostal strom o řád menší... tedy Tk-1)
    Použitím indukčního předpokladu tedy dostáváme z Tk binomiální strom řádu k−1, tedy Bk−1. Opětovným připojením S zpět dostáváme přesně strom Bk (ztrácím se... z jakého indukčního předpokladu)

Z jakého indukčního předpokladu? Indukční předpoklad je, že pro nějaké k>0 platí, že stromy Tk a Bk jsou stejné že? (lépe řečeno izomorfní) A nyní bych měl přijít na to, že když to platí pro nějaké k, tak to platí i pro k+1, ne? Jenže kde přesně leží to odvození pro k+1? Chápu, že to asi není těžký důkaz, ale já tam tu indukci prostě nevidím :/


Důkaz Bk => Tk. Matematickou indukcí podle k.
    Naopak, uvážíme-li strom Bk, z indukce vyplývá, že Bk−1 je binomiální strom T řádu k−1, (opět.. z jaké indukce to vyplývá?)
    pod jehož kořen jsou dle definice napojeny binomiální stromy řádů T0, . . . , Tk−2.     (jak něco takového můžu tvrdit, když mám vycházet jen z 2.definice)
    Pod kořen Bk jsou tudíž napojeny binomiální stromy řádů T0, . . . , Tk−1, tedy strom Bk je binomiální strom řádu k.

Offline

  • (téma jako vyřešené označil(a) kocourOggy)

#2 29. 08. 2017 01:03 — Editoval kocourOggy (29. 08. 2017 02:12)

kocourOggy
Příspěvky: 28
Pozice: student
Reputace:   
 

Re: Trable s indukcí podruhé - ekvivalence definic binomiálních stromů

↑ kocourOggy:
Hm... zkusil jsem se ještě zamyslet a takhle mi to smysl dává.

Důkaz Tk => Bk. Matematickou indukcí podle k.
nechť k = 0... tvrzení platí triviálně jelikož B0 je stejně jako T0 pouze jeden vrchol.
   
nechť tvrzení platí pro k = n-1 (kde n > 0). Tedy náš IP (indukční předpoklad) je, že Bn-1 je izomorfní s Tn-1.
Tn-1 := strom má n-2 synů, které jsou popořadě stromy s řádem 0, 1, 2,..., n-2
Bn-1 := strom se skládá ze stromu Bn-2 pod jehož kořenem je napojený další strom Bn-2
Zdůrazněme, že Bn-1 je ekvivalentní definice k Tn-1 (jak jsme na to přišli? Prostě je to náš IP)

nechť k = n...
Tn := strom má n-1 synů, které jsou popořadě stromy s řádem 0, 1, 2,..., n-2, n-1 (definice, ze které vycházíme)
Strom Tn můžeme sestavit ze stromu Tn-1 z IP (strom Tn obsahuje podstromy jako strom Tn-1, ale má k tomu ještě navíc (n-1)-ního syna reprezentující strom s řádem n-1)
To nápadně připomíná 2.definici pro Bk, protože tato myšlenka nám říká, že Tn lze sestavit ze stromu Tn-1 k jehož kořeni je připojen další strom Tn-1. Místo Tn-1 bychom chtěli však strom Tn sestavit ze stromů Bn. S tím nám pomůže IP, jelikož IP říká, že Bn-1 je izomorfní s Tn-1 (tj. lze je zaměnit), můžeme říci, že strom Tn lze sestavit ze stromu Bn-1 k jehož kořeni je připojen další strom Bn-1. Definice Tk tudíž můžu zaměnit s Bk, kde k>0! Proč? Protože indukcí jsme dokázali, že každý Tk binomiální strom zvládnu sestavit dle 2.definice z Bk. Dokázali jsme, že Tk a Bk jsou stejná pro k=0. Ukázali jsme, že když uvažujeme izomorfismus Tk a Bk pro nějaké k (k = n-1), tak jsou grafy shodné i pro k+1 (k = n).

Důkaz pro Bk => Tk se vede obdobně...

Offline

 

#3 29. 08. 2017 01:22 — Editoval kocourOggy (29. 08. 2017 01:24)

kocourOggy
Příspěvky: 28
Pozice: student
Reputace:   
 

Re: Trable s indukcí podruhé - ekvivalence definic binomiálních stromů

↑ kocourOggy:
Přijde mi, že v těch studijních materiálech by to mohlo být lépe napsané. Sice to je asi trochu subjektivní pohled (vím, že si potřebuju věci trochu víc zdůvodňovat než je třeba), ale aspoň by tam mohlo být napsané co si volím za indukční předpoklad, i když to už je spíš poznámka pro profesory, co ty studijní materiály tvoří a nejspíš i mimo téma otázky.

Jinak nedokázali byste prosím doporučit nějaký studijní materiál o matematické indukci? Na střední jsme dělali takové klasické úlohy s dokazováním pro součtové vzorce a já vlastně až teď na vysoké zjišťuji, že jsem matematickou indukci nechápal úplně dobře a mám dojem, že jsem na ni narazil tolikrát, že by stálo za to se na ni podívat trochu lépe. Už jen slabý princip matematické indukce mi dělá potíže, natož silný princip, nebo strukturální indukce.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson