سوال از اثبات (فصل اول کتاب پوران) - نسخهی قابل چاپ |
سوال از اثبات (فصل اول کتاب پوران) - azad_ahmadi - 03 آذر ۱۳۹۱ ۱۲:۱۵ ق.ظ
سلام به همه دوستان مانشتی. قبلا می تونستم این سوال رو حل کنم. اما امشب کلی اعصابمو ریخت به هم. ممنون می شم کمک کنید. { اون رادیکال ها برای همه عبارت زیرش هست. ۲ به توان اون عبارت = n به توان اون عبارت. } |
RE: سوال از اثبات (فصل اول کتاب پوران) - nasi1391 - 03 آذر ۱۳۹۱ ۰۱:۰۱ ق.ظ
(۰۳ آذر ۱۳۹۱ ۱۲:۱۵ ق.ظ)azad_ahmadi نوشته شده توسط: سلام به همه دوستان مانشتی. سلام میخواهی اینو ثابت کنی ؟ [tex]2^{\sqrt{2lgn}}=n^{\sqrt{\frac{2}{lgn}}}[/tex] خوب کاری نداره ! اگه دو طرف رو به توان : [tex]\sqrt{2lgn}[/tex] برسونی ! چی میشه ؟ این میشه : [tex](2^{\sqrt{2lgn}})^{\sqrt{2lgn}}=(n^{\sqrt{\frac{2}{lgn}}})^{\sqrt{2lgn}}[/tex] خوب حالا توان قدیم در توان جدید ضرب میکنیم و میشود : [tex]2^{2lgn}=n^{\sqrt{4}=2}[/tex] و میدانیم که : [tex]2^{2lgn}=4^{lgn}=n^{lg4}=n^2[/tex] ثابت شد |
سوال از اثبات (فصل اول کتاب پوران) - azad_ahmadi - 03 آذر ۱۳۹۱ ۰۲:۵۲ ق.ظ
ممنون بابت جواب. اثبات رو از کجا پیدا کردی؟ اون علامت تعجبی که جلوی "برسونی" نوشتی، فکر کنم برای خودت هم سواله که چرا؟ (چرا رادیکال ۲lgn )؟ |
RE: سوال از اثبات (فصل اول کتاب پوران) - nasi1391 - 03 آذر ۱۳۹۱ ۱۱:۰۵ ق.ظ
(۰۳ آذر ۱۳۹۱ ۰۲:۵۲ ق.ظ)azad_ahmadi نوشته شده توسط: ممنون بابت جواب. سلام مجدد نه منظور خاصی نداشتم ، عادت دارم که علامت تعجب میزارم. یکم فکر کردم به جواب رسیدم از جایی نیاوردم. این نکته رو برای یادگاری میگم : گزاره : اگر : [tex]f(n)\in O(g(n))[/tex] آنگاه : [tex]2^{f(n)}\notin O(2^{g(n)} )[/tex] غلط است چه اوی کوچیک باشه و چه اوی بزرگ. اثبات اوی بزرگ ساده هست. ([tex]f(n)=2n ,g(n)=n[/tex] اما اثبات اوی کوچیک : اگر فرض کنیم : [tex]f(n)=\frac{1}{n^2} ,g(n)=\frac{1}{n}[/tex] در این صورت میتوان گفت که : [tex]f(n)\in o(g(n))[/tex] (اثبات از طریق حد : [tex]\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}=\lim_{n\rightarrow \infty } \frac{\frac{1}{n^2}}{\frac{1}{n}}=\lim_{n\rightarrow \infty } \frac{n}{n^2}=\lim_{n\rightarrow \infty } \frac{1}{n}=0\Rightarrow f(n)\in o(g(n))[/tex] حال اگر داشته باشیم : [tex]2^{f(n)}\in o(2^{g(n)})=2^\frac{1}{n^2} \notin o(2^\frac{1}{n})[/tex] زیرا : [tex]2^{f(n)}\in o(2^{g(n)})=2^\frac{1}{n^2} \in \theta (2^\frac{1}{n})[/tex] (از حد استفاده کنید.) |
سوال از اثبات (فصل اول کتاب پوران) - azad_ahmadi - 03 آذر ۱۳۹۱ ۰۴:۰۶ ب.ظ
کتاب پوران صفحه ۱۱، اون دو عبارتی که من نوشتم رو مساوی دونسته، و هردوی اونا رو کوچیکتر از n نوشته. n >2^R2lgn = n^R2/lgn ، پس به عبارتی چون شما n^2 رو بدست اوردین، پاسخ شما اشتباهه. اون اثبات با توجه به خواص لگاریتم حل می شه، اما تو یه قسمتیش نمی دونم باید چکار کنم. |
RE: سوال از اثبات (فصل اول کتاب پوران) - nasi1391 - 03 آذر ۱۳۹۱ ۰۸:۲۱ ب.ظ
(۰۳ آذر ۱۳۹۱ ۰۴:۰۶ ب.ظ)azad_ahmadi نوشته شده توسط: کتاب پوران صفحه ۱۱، اون دو عبارتی که من نوشتم رو مساوی دونسته، و هردوی اونا رو کوچیکتر از n نوشته. سلام مجدد ! جسارته ولی چه ربطی داره ؟ مثلآ شما میخواهی ثابت کنی که : [tex]\sqrt{n}=n^{\frac{1}{2}}[/tex] بعد دو طرف رو به توان دو برسونی : [tex](\sqrt{n})^2=(n^{\frac{1}{2}})^2[/tex] و در نهایت برسی به این جمله که : [tex]n=n[/tex] که بدیهی است. (و اثبات کامل است.) بعد از همه این ماجرا ها یکی بیاد و بگه غلطه ! و دلیلشم این باشه که [tex]\sqrt{n}\neq n[/tex] !!! شما جای من ، آیا دیوانه نمیشدی ؟ (به حق چیزای ندیده ونشنیده ! ) |