Matematické Fórum

mr.rubik

Zdravím všechny přítomné,

za domácí úkol jsem dostal vyřešit rekurentní rovnici (diskrétní matematika). Byl bych vděčný za pomoc.

Funkce t(n), rekurentně:

$t(n) = at(\lfloor\frac{n}{3}\rfloor) + n^{k}$

Úkolem je pomocí mistrovské metody nalézt těsnou asymptotickou mez t(n) $t(n) = \Theta(?)$ pro všechny hodnoty parametrů.

parametry zde

$0 < a <= 1$

$k \in \mathbb{N}$

V mistrovské metodě jsou tři možnosti (v rychlosti je tu připomenu)

a) pokud $f(n) = O (n^{log_{b}a-\varepsilon }), \varepsilon > 0$ pak $t(n) = \Theta (n^{log_{b}a })$

b) pokud $f(n) = \Theta (n^{log_{b}a })$ pak $t(n) = \Theta (n^{log_{b}a }\log_{}n)$

c) pokud $f(n) = \Omega (n^{log_{b}a+\varepsilon })$ ... pak $t(n) = \Theta (f(n))$

Já jsem začal řešit a) takto:

$f(n) = O(n^{\log_{n}a-\varepsilon })$

$\varepsilon > 0, p = a - \varepsilon$ - p jsem si určil sám pro sebe pro přehlednost

a protože v logaritmu nesmí být p <= 0, tak jsem řešil jen pro p > 0 a tedy:

$z = \log_{3}p$ z jsem si taky určil sám

z musí být menší než nula, protože b je z intervalu (0,1), to z toho plyne (doufám :) )

dále tedy:

$n^{k} \le c\cdot n^{z}$

Došel jsem až sem a teď nevím, jak určit konkrétní hodnoty parametrů tak, aby to platilo. Respektive udělal jsem několik pokusů, ale opravdu nevím. Dost jsem se ve složitostech ztrácel.

Další části mistrovské metody budou - předpokládám - analogické. Prosil bych tedy o kontrolu dosavadního postupu a o radu, co dál.

EDIT: jedná se sice o diskrétní matematiku, ale ne na VŠB, tak jsem téma umístil sem, doufám, že je to tak správně

Díky, MrRubik

mr.rubik · 28. 11. 2011 13:20

To tady opravdu nikdo nezvládá mistrovskou metodu, nebo jsem to téma vytvořil nějak špatně? Mimochodem... co před mým tématem znamená ta tečka?

jelena · 28. 11. 2011 22:26

↑ mr.rubik:

Zdravím, bude to čistě Moderatorská osvěta (mistrovskou metodu jsem sice teď přečetla z materiálů, ale diskrétní matematika je zapovězena, mé mistrovství končí u trojčlenky), tak jen:

tečka značí, že jsi do tématu přispíval, téma jsi vytvořil správně, v sekci DIM VŠB se objevují také úlohy z jiných škol, snad nebude námitka, pokud přesunu a budeš více viditelný, případně vážený Moderátor pan Petr Kovář přesune jinam (děkuji).

Je to asi všechno, co mohu udělat - pokud se podíváš na stav odpovězených témat v sekci VŠ, řekla bych, že je období odevzdávání nějakých práci (alespoň v mém okolí to tak je). Ať se podaří.

mr.rubik · 28. 11. 2011 22:30

Super, zatím děkuji za odpověď.

FailED · 28. 11. 2011 22:55 — Editoval FailED (28. 11. 2011 23:01)

↑ mr.rubik:

Zdravím,

ten překlad zní opravdu hrozně :)

Dost jsem se ve složitostech ztrácel.

Bez toho to opravdu nepůjde.

$n^k \in O(n^{\log_{b}a-\varepsilon }) \Leftrightarrow \exists c>0 \,\forall n\, cn^k\le n^{\log_{b}a-\varepsilon }$

Protože pro n>0 je n^k>0, můžeme to převést na $n^k \in O(n^{\log_{b}a-\varepsilon })\Leftrightarrow \lim\frac{n^{\log_{b}a-\varepsilon }}{n^k}>0$ , z toho už k vyjádříš ne?

mr.rubik · 29. 11. 2011 21:38

Jaký překlad máš na mysli?

Jo snad si s tím poradím. Díky za pomoc :)

Dworzaaa · 29. 11. 2011 23:34

Ja to v tom dal este nevidim..slo by to prosim jeste trochu rozvest?

FailED · 30. 11. 2011 00:17

↑ mr.rubik:
master theorem -> mistrovská metoda

↑ Dworzaaa:
Co v čem nevidíš? Ta limita je jen přepsání definice, $a, b, \varepsilon$ jsou konstanty takže vyjde kladně právě když $\log_ba-\varepsilon>k$ .

mr.rubik · 30. 11. 2011 11:38

↑ FailED:

my to tak máme v přednáškách :) já si to nevymyslel, ale uznávám, že ten překlad úplně košér není :)

theCAESAR

No a jelikož neplatí že $log_{3}(a) - \varepsilon < k$ kde a je $0 < a \le 1$ protože ten logaritmus je vždycky záporný a $\varepsilon > 0$ a $k \in \mathbb{N}$ Tzn že neplatí ani $n^{k}=\Theta (n^{log_{3}(a)})$ pak platí třetí možnost a to že $n^{k}=\Omega (n^{log_{3}a + \varepsilon })$ a také platí $a * (n/3)^{k} \le c*n^{k}$

Dworzaaa · 30. 11. 2011 15:46

↑ theCAESAR:
tohle reseni vypada rozumne... projevi se na vysledku nejak ta dolni cela cast v $(\lfloor\frac{n}{3}\rfloor)$ ? Nevim, kde by se to mohlo projevit, ale zase se mi nezda, ze bych ji moh uplne zahodit..

theCAESAR · 30. 11. 2011 15:57

Při řešení mistrovskou metodou se zanedbává, zda je to dolní či horní část. Podle mě je to podobný jako by si k $n^{2}$ připočítával konstantu $c$ stejně ti z toho nikdy nevyjde že $(n^{2}+c) = \Omega (n^{3})$

mr.rubik

Děkuji mnohokrát všem za pomoc. Byl v tom malý chyták: Master theorem platí jen pro a >=1 :) Nějaké body jsem za to ale dostal. Myslím si, že je možné tohle téma uzavřít.

Matematické Fórum

#1 27. 11. 2011 18:24 — Editoval mr.rubik (27. 11. 2011 19:58)

Rekurentní rovnice - mistrovská metoda

#2 28. 11. 2011 13:20

Re: Rekurentní rovnice - mistrovská metoda

#3 28. 11. 2011 22:26

Re: Rekurentní rovnice - mistrovská metoda

#4 28. 11. 2011 22:30

Re: Rekurentní rovnice - mistrovská metoda

#5 28. 11. 2011 22:55 — Editoval FailED (28. 11. 2011 23:01)

Re: Rekurentní rovnice - mistrovská metoda

#6 29. 11. 2011 21:38

Re: Rekurentní rovnice - mistrovská metoda

#7 29. 11. 2011 23:34

Re: Rekurentní rovnice - mistrovská metoda

#8 30. 11. 2011 00:17

Re: Rekurentní rovnice - mistrovská metoda

#9 30. 11. 2011 11:38

Re: Rekurentní rovnice - mistrovská metoda

#10 30. 11. 2011 12:09 Příspěvek uživatele theCAESAR byl skryt uživatelem theCAESAR.

#11 30. 11. 2011 12:24 — Editoval theCAESAR (30. 11. 2011 12:28)

Re: Rekurentní rovnice - mistrovská metoda

#12 30. 11. 2011 15:46

Re: Rekurentní rovnice - mistrovská metoda

#13 30. 11. 2011 15:57

Re: Rekurentní rovnice - mistrovská metoda

#14 10. 12. 2011 13:42 — Editoval mr.rubik (10. 12. 2011 14:09)

Re: Rekurentní rovnice - mistrovská metoda

Zápatí