زمان کنونی: ۰۱ دى ۱۴۰۳, ۰۷:۱۵ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

ارسال:
  

reyhaneh64 پرسیده:

چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

سوال اول و دوم از کتاب پوران فصل ۲(تقسیم و غلبه)
۱) در الگوریتم selection (همان الگوریتم بهینه برای یافتن k امین کوچکترین عنصر در آرایه n تایی به کمک میانه میانه ها)آرایه ورودی به گروه های ۵ تایی تقسیم شدند آیا اگر به گروه های ۷ عنصری تقسیم کنیم زمان همچنان خطی است؟ به گروه های ۳ عنصری چطور؟
پاسخ:
فرض کنیم گروه ها k عنصری باشند تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل
k2(12nk2)n4k
است، پس در بدترین حالت selection به صورت بازگشتی روی حداکثر
n(n4k)=3n4k
عنصر اجرا میشود.
T(n)T(nk)T(3n4k)O(n)

تا این جا رو مشکلی ندارم
سوالم از اینجا به بعده :
برای آنکه این رابطه خطی باشد باید T(n)cn که با جایگذاری ثابت میشود :
k>4

عدد چطور بدست اومده؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
تو رابطه میذارم
اما ۴ بدست نمیاد



۲)نشان دهید اگر n140 حداقل n4 عنصر از n بزرگتر و حداقل n4 عنصر از n کوچکتر است؟


۳) اگر در الگوریتم selection به دسته های ۲k-1 عنصری تقسیم کنیم رابطه T(n) به صورت زیر بدست می آید:
T(n)=θ(n)T(n2k1)T(3k22(2k1))n2k)

T دوم رو متوجه نمیشم.

۴)حداکثر تعداد عناصری که میتوانند در دو طرف میانه میانه ها باشد؟
2(n5)1
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

اینو تو CLRS یافتم یکم شبیش بود:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

اینم یکی دیگه :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

شاید کمکت کنه
فعلا وقت نکردم بیشتر از این
اگه تونستم بیشتر حل می کنم
اگه حلشو یاد گرفتید به منم بگیدBig Grin
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

تا اینجا برات حل کردم :
T(n)T(nk)T(3n4k)Θ(n)cn/kc3cn/4ckan=(43k)cn4k(k1)can=cn(k44kcn(k1)can)cn4k4kcn(k1)can0

امیدوارم قسمت آخر رو دیگه خودت حل کنی به منم یاد بدی
نقل قول این ارسال در یک پاسخ

ارسال:
  

reyhaneh64 پاسخ داده:

RE: چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

(۲۷ آذر ۱۳۹۱ ۰۶:۰۷ ق.ظ)csharpisatechnology نوشته شده توسط:  تا اینجا برات حل کردم :
T(n)T(nk)T(3n4k)Θ(n)cn/kc3cn/4ckan=(43k)cn4k(k1)can=cn(k44kcn(k1)can)cn4k4kcn(k1)can0

برای اینکه این عبارت کمتر مساوی ۰ باشه با فرض a<c که البته اگه در نظر هم نگیریم فرقی نمیکنه باید ضریب cn از ۰ کوچکتر باشه که بدست میاد k>4
که مرتبه خطی میشه

برای k کوچکتر از ۴ گفته بود غیر خطی میشه
چرا؟؟؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

اینم معادل جوابه:
(43k)n4kk1anc
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

در مورد قضیه ی Master(اصلی)،بهترین روش یادگیری رو توی جزوه های دستنویس هادی یوسفی دیدم و سعی کردم خلاصشو فرموله کنم بذارم اینجا
T(n)=AF(n),A=aT(n/b)
ifΘ(A)>Θ(F(n))T(n)=Θ(A)
ifΘ(F(n))>Θ(A)T(n)=Θ(F(n))
[تصویر:  149463_1_1379087161.gif]
Θ(A)=nLogba
البته موارد استثنا هم وجود داره که توی جای مختلف باید از روش های درخت بازگشت و روش های تبدیل متغیر یا روش های دیگه و استقراء و برهان خلف و غیره حلش کنیم.

در اینجا F(n ما همون Cn هست
پس A باید از Cn کمتر باشه تا همون ((Teta(F(n رو قبول کنیم
( Teta(f(n))=teta(cn
پس تتای A باید از Cn کمتر باشه.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

ana_12345 پاسخ داده:

RE: چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

(۲۵ آذر ۱۳۹۱ ۰۶:۲۲ ب.ظ)reyhaneh64 نوشته شده توسط:  سوال اول و دوم از کتاب پوران فصل ۲(تقسیم و غلبه)
۱) در الگوریتم selection (همان الگوریتم بهینه برای یافتن k امین کوچکترین عنصر در آرایه n تایی به کمک میانه میانه ها)آرایه ورودی به گروه های ۵ تایی تقسیم شدند آیا اگر به گروه های ۷ عنصری تقسیم کنیم زمان همچنان خطی است؟ به گروه های ۳ عنصری چطور؟
پاسخ:
فرض کنیم گروه ها k عنصری باشند تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل
k2(12nk2)n4k
است، پس در بدترین حالت selection به صورت بازگشتی روی حداکثر
n(n4k)=3n4k
عنصر اجرا میشود.
T(n)T(nk)T(3n4k)O(n)

تا این جا رو مشکلی ندارم
می شه این قسمت رو که متوجه شدید توضیح بدید ؟؟؟ من این فرمول رو نمی فهمم. چرا ضربدر K/2 ??
توی فرمول بالا که برای محاسبه " تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل " نوشتید رو می گم . کلا میشه تحلیل بدست اوردن این فرمول رو بگین ؟؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

reyhaneh64 پاسخ داده:

RE: چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

(۲۵ آذر ۱۳۹۱ ۰۶:۲۲ ب.ظ)reyhaneh64 نوشته شده توسط:  ۳) اگر در الگوریتم selection به دسته های ۲k-1 عنصری تقسیم کنیم رابطه T(n) به صورت زیر بدست می آید:
T(n)=θ(n)T(n2k1)T(3k22(2k1))n2k)

اثبات جواب این سوال:

زمان لازم برای یافتن میانه (n2k1) میانه به صورت بازگشتی:
T(n2k1)


هزینه لازم برای partition کردن دو طرف میانه میانه ها و...
θ(n)

حداقل تعداد عناصر بزرگتر(یا کوچکتر از) میانه میانه ها وقتی به دسته های ۲k-1 عنصری تقسیم میکنیم:

(12n2k12)×(2k1121)=k2n2k12k

(((((((((((((((توجه: تعداد عناصر بزرگتر از میانه میانه ها در هر دسته:
در هر دسته ۲k-1 عنصره :میانه را کم میکنیم بر ۲ تقسیم میکنیم با ۱(میانه دسته) جمع میکنیم
میشه ( \frac{2k-1-1}{2}) \right ))))))))))))))))


بعد از نتیجه عبارت بالا محاسبات را انجام داده :
(nk2(2k1)2k)

برای یافتن حداکثر تعداد عناصر از n عبارت بالا را کم میکنیم:
n(nk2(2k1)2k)=n (4k2k2(2k1))2k=n(3k22(2k1))2k

پس جواب کلی میشه:

T(n)=θ(n)T(n2k1)T(3k22(2k1))n2k)

(۲۷ آذر ۱۳۹۱ ۰۶:۲۶ ب.ظ)reyhaneh64 نوشته شده توسط:  
(27 آذر ۱۳۹۱ ۰۶:۰۷ ق.ظ)csharpisatechnology نوشته شده توسط:  تا اینجا برات حل کردم :
T(n)T(nk)T(3n4k)Θ(n)cn/kc3cn/4ckan=(43k)cn4k(k1)can=cn(k44kcn(k1)can)cn4k4kcn(k1)can0

برای اینکه این عبارت کمتر مساوی ۰ باشه با فرض a<c که البته اگه در نظر هم نگیریم فرقی نمیکنه باید ضریب cn از ۰ کوچکتر باشه که بدست میاد k>4
که مرتبه خطی میشه

برای k کوچکتر از ۴ گفته بود غیر خطی میشه
چرا؟؟؟

برای غیر خطی بودن مرتبه رابطه به ازای k<4 در رابطه بالا که اثبات شد
به جای ۲k-1 میذاریم ۳
به رابطه زیر میرسیم:
۲k-1=3
k=2

T(n)=T(n3)T(23n)θ(n))

که میدانیم با درخت بازگشت حلش میشه:
T(n)=omega(nlogn)
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها

جرا به جای ۲k-1 میذاریم ۳ ؟
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مبحث جستجوهای محلی Elham_tm ۷ ۴,۵۱۱ ۱۷ اسفند ۱۴۰۰ ۰۵:۴۳ ب.ظ
آخرین ارسال: KB2000
  در نوشتن چند جمله انگلیسی نیاز به کمک دارم fa_karoon ۰ ۱,۷۲۹ ۰۳ شهریور ۱۴۰۰ ۰۱:۰۹ ب.ظ
آخرین ارسال: fa_karoon
  مدیریت سیستم چند پردازنده ای متقارن no_ta2000 ۰ ۱,۷۶۰ ۰۹ مهر ۱۳۹۹ ۰۲:۲۱ ب.ظ
آخرین ارسال: no_ta2000
  صفحه چند سطحی Flash1 ۰ ۱,۷۹۸ ۱۰ تیر ۱۳۹۹ ۰۵:۵۸ ب.ظ
آخرین ارسال: Flash1
  کمک برای چند تا سوالات شبکه کامپیوتری Hamedudk ۳ ۶,۴۴۳ ۲۷ آبان ۱۳۹۸ ۱۱:۴۲ ق.ظ
آخرین ارسال: khayyam
  افزایش واگرایی الگوریتم های مبتنی بر جمعیت moslem73421 ۲ ۳,۳۳۷ ۰۵ شهریور ۱۳۹۸ ۱۰:۵۳ ب.ظ
آخرین ارسال: cpt.mazi
  دانلود آموزش تصویری کلاس درس تحلیل و طراحی الگوریتم های پیشرفته دانشگاه فردوسی jazana ۱۳ ۱۴,۳۴۴ ۱۰ خرداد ۱۳۹۸ ۰۵:۴۲ ب.ظ
آخرین ارسال: Valipourh20
  چند راه برای این که پرواز طولانی راحت تری را تجربه کنید - خبرگزاری فارس abolfazlda ۰ ۹ ۲۴ بهمن ۱۳۹۷ ۱۱:۰۵ ق.ظ
آخرین ارسال: abolfazlda
Question تفاوت تعداد مقایسه های مورد نیاز در الگوریتم های متفاوت porseshgar ۰ ۲,۱۷۷ ۱۵ بهمن ۱۳۹۷ ۱۲:۳۳ ب.ظ
آخرین ارسال: porseshgar
  درخواست دانلود چند مقاله از www.civilica.com H.Mohammadi ۱ ۳,۸۰۸ ۱۴ دى ۱۳۹۷ ۰۱:۲۳ ق.ظ
آخرین ارسال: Behnam‌

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close