این تاپیک اختصاص داره به مسائل متفرقه در زمینه طراحی الگوریتم
سئوال اول:
تمرین ۲-۲ فصل اول کتاب clrs (اخر کتاب)
جواب نامعادله: ۸n^2 < 64nlogn
مسئله دوم:
حداق مقدار n به نحوی که در نامعادله زیر صدق کند ؟ ۱۰۰n^2 < 2 ^ n
من که هر چی تبدیل زدم نشد در نهایت تونستم با تبدیلات سری تبدیش کنم که باز هم میخوره به...(وای مخم سووت کشید)
برا سوال اول فک کنم اینطوری بشهa
۸(n^2) < 64 nlogn
(۲^۳)(n^2) < (2^6) nlogn
(۲n)^5 < (2^6) nlogn
---> 5 log 2n < 6 log 2n logn
سوال اول: اگر n کوچکتر یا مساوی ۴۳ باشه اونوقت مقدار ۸n^2 کوچکتر از ۶۴nlogn خواهد بود
سوال دوم: فکر می کنم کوچکترین n ای که در رابطه [tex]100n^{2}<2^{n}[/tex] صدق می کنه ۱۵ هستش
(۰۸ مرداد ۱۳۹۰ ۰۵:۲۱ ب.ظ)mfXpert نوشته شده توسط: سوال اول: اگر n کوچکتر یا مساوی ۴۳ باشه اونوقت مقدار ۸n^2 کوچکتر از ۶۴nlogn خواهد بود
سوال دوم: فکر می کنم کوچکترین n ای که در رابطه [tex]100n^{2}<2^{n}[/tex] صدق می کنه ۱۵ هستش
ممکنه بگید ۴۳ و ۱۵ رو چه طور بدست آوردید؟
(۰۸ مرداد ۱۳۹۰ ۰۶:۰۰ ب.ظ)ehsan_nekooee نوشته شده توسط:خیلی ساده.با استفاده از یه ماشین حساب(08 مرداد ۱۳۹۰ ۰۵:۲۱ ب.ظ)mfXpert نوشته شده توسط: سوال اول: اگر n کوچکتر یا مساوی ۴۳ باشه اونوقت مقدار ۸n^2 کوچکتر از ۶۴nlogn خواهد بود
سوال دوم: فکر می کنم کوچکترین n ای که در رابطه [tex]100n^{2}<2^{n}[/tex] صدق می کنه ۱۵ هستش
ممکنه بگید ۴۳ و ۱۵ رو چه طور بدست آوردید؟
(۰۸ مرداد ۱۳۹۰ ۰۲:۰۸ ب.ظ)ehsan_nekooee نوشته شده توسط: برا سوال اول فک کنم اینطوری بشهa
۸(n^2) < 64 nlogn
(۲^۳)(n^2) < (2^6) nlogn
(۲n)^5 < (2^6) nlogn
---> 5 log 2n < 6 log 2n logn
من هنگ کردم اخه هر جور حساب مینکم
۳^۲(۲^n) برابر با ۵^(۲n)
نمیشه
البته من تا یادمه تو بحث توانها می بایست پایه توانها یکی میبودن البته تو ریاضیات مدرن نمیدونم شاید اونجا بشه از این کارا کرد
در هر حال ببیند در این جور مسائل باید مقدار عددی n را بدست بیاورید و صرفا تبدیلاتی که شما استفاده کردین نتیجه بخش نیست .
(۰۸ مرداد ۱۳۹۰ ۰۷:۵۰ ب.ظ)mfXpert نوشته شده توسط:(08 مرداد ۱۳۹۰ ۰۶:۰۰ ب.ظ)ehsan_nekooee نوشته شده توسط:خیلی ساده.با استفاده از یه ماشین حساب(08 مرداد ۱۳۹۰ ۰۵:۲۱ ب.ظ)mfXpert نوشته شده توسط: سوال اول: اگر n کوچکتر یا مساوی ۴۳ باشه اونوقت مقدار ۸n^2 کوچکتر از ۶۴nlogn خواهد بود
سوال دوم: فکر می کنم کوچکترین n ای که در رابطه [tex]100n^{2}<2^{n}[/tex] صدق می کنه ۱۵ هستش
ممکنه بگید ۴۳ و ۱۵ رو چه طور بدست آوردید؟
خیلی خوبه ولی مسئله اینجاست که شما سر جلسه امکان حمل ماشین حساب رو ندارید
الته چورتکه رو نمیدونم انشالله که مشکلی نداشته باشه
ولی راه حل ریاضی ارائه بدید وگرنه با عدد گذاری میشه عدد مورد نظر رو به دست اورد ببیندید در این مسائل از انجا که جملات از یک جس نمیباشند لذا با مشکل روربرو هستیم (لگاریتمی با چند جمله ایی ویا نمایی با چند جمله ایی) لذا باید در صدد تبدیل جملات به یک فرم استاندارد کنیم مثلا همگی رو تبدیل به چند جمله ایی کنیم.
خب با تبدیلات سری میشه تابع نمایی رو تبدیل به چند جمله ایی کرد اما من از این بیشتر نتونستم کاری پیش ببرم یعنی میخورم به محاسبات عددی .
دوست عزیز بعید میدونم چنین سوالی اونم تو کنکور بدن و به شما بگن مقدار n رو به دست بیارید.هدف کلی تمرین ۲-۲ از فصل اول این بوده که بگه اگر مقدار n(یا همون ورودی های شما) کوچکتر یا مساوی یه مقدار خاص باشه بهتره که به جای مرتب سازی ادغامی از مرتب سازی درجی استفاده بشه.
یکی از دوستان خواسته بود تا جواب تمرین ۳-۳ رو قرار بدم.من ترتیب زیر رو به دست آوردم(تضمین نمی کنم که صددرصد درست باشه)
[tex]1=n^{\frac{1}{lgn}}< lnln(n)< \sqrt{lgn}< ln(n)< \sqrt{2}^{lg(n)}<2^{lg(n)}=n<lg(n!)<(lgn)^{2}<n.lg(n)<n^{2}=4^{lg(n)}<n^{3}<(\frac{3}{2})^{n}<2^{n}<n.2^{n}<e^{n}<(lgn)!<n!<(n 1)!<n^{lglg(n)}=lg(n)^{lg(n)}<2^{2^{n}}<2^{2^{n 1}}[/tex]
چهار تا تابع که [tex]log^{*}[/tex] دارن و تابع [tex]2^{\sqrt{2lg(n)}}[/tex] رو در جواب بالا نیاوردم چون ترتیب قرارگیریشون در لیست بالا رو نتونستم به دست بیارم
داریم:
[tex]8n^{2}< 64n log n[/tex]
با ساده کردن ۸ با ۶۴ و دو n طرفین داریم:
[tex]n< 8 log n[/tex]
و همچنین:
[tex]\frac{n}{8}< log n[/tex]
و
[tex]2^{\frac{n}{8}}< n[/tex]
حال با محاسبه مقدار n تقریبا بین ۲ تا ۴۳ می شود.