تعداد فراخوانی های بازگشتی الگوریتم استراسن

[ali643]

سئوال 50 کنکور it 86
اگر در ضرب استراسن مساله کوچک ضرب ماتریسهای 2*2 باشد با چند فراخوانی بازگشتی الگوریتم استراسن عمل ضرب دو ماتریس 8*8 انجام می پذیرد؟

الف)343
ب) 57
ج)49
د)7

جواب 57 هست

.

چطوری به این جواب رسیده ؟


مرسی

[empoly]

سلام دوست عزیز :
1- اگر لطف کنید و عنوان سوال را که به اشتباه رب استراسن شده است را اصلاح کنید خیلی خوبه. اگر یه طورهایی عنوان را بیاورید که معلوم بشه که سوال مربوط به رابطه ی بازگشتی و تست هست و... که بهتره البته تو این مورد من نباید دخالت کنم چون که هر چی نباشه این جا مدیر داره.
2- اگر لطف کنید و پاسخ نامه ی ( کلید) آزمون فن آوری اطلاعات سال قبل را به من هم بدهید ممنون می شم البته اگر خودتان دارید ( در حال حاضر در سایت سازمان سنجش موجود نیست)
3- در مورد سوال هم من فکر کنم 49 جواب باشه چون که می شه برای الگوریتم استراسن گفت تعداد ضرب ها و یا به عیارتی تعداد فراخوانی ها تابع از رابطه ی زیر به دست می آید :
T(n) =7 T(n/2)
البته خوب اگه شما می گید 57 و از روی کلید نگاه کردید حتما حکمتی در کار است!!!!

[whitehat]

مسئله جالبی است، من فکر کنم این مسئله با استفاده از مفهوم ماتریس استراسن استفاده میشه. الگوریتم استراسن این نکته را بیان می کند که ضرب دو ماتریس 2 در 2 به جای 8 مرحله در هفت مرحله انجام میشه.
برای انجام عمل ضرب یک ماتریس 8 در 8 باید 64 مرحله انجام شود ولی اگر بخواهیم آنرا با استراسن انجام دهیم در واقع 7 مرحله کمتر از 64 مرحله انجام میشه، که برابر 57 است.

در مورد سوال هم من فکر کنم 49 جواب باشه چون که می شه برای الگوریتم استراسن گفت تعداد ضرب ها و یا به عیارتی تعداد فراخوانی ها تابع از رابطه ی زیر به دست می آید :
T(n) =7 T(n/2)

بهتره بگید تعداد ضرب ها ! جواب شما صحیح نیست چون در الگوریتم استراسن T(1)=1 است

تعداد جمع های ماتریس استراسن هم از رابطه زیر بدست می آید:

T(n)=7T(n/2)+18(n/2)^2

پ.ن:روی جواب که گذاشتم فکر کنید چون ممکنه درست نباشه!
موفق باشید

[empoly]

من نمی فهمم چرا می گید 7 تا کمتر نیاز داره .

اگه می شه بیشتر توضیح بدهید.

در مورد تعداد ضزب ها و همچنین جمع ها هم حق با شماست و منظور از نوشتن اون رابطه بازگشتی دقیقا تعداد فراخوانی ها بود نه تعداد ضرب ها و یا جمع ها و یا مجموع آنها.

کلید را کسی نداره ( اگر دارید آپلود کنید ما هم استفاده کنیم لطفا)

[msn_vb]

این دقیقا سئوال اختیاری پایان ترم طراحی الگوریتم که همین 1 ماه پیش امتحان دادم بود
و جواب خیلی ساده ای داره
شما کافیه که فقط یک درخت بکشید
در مرحله اول که یک فراخوانی 8*8 در main دارید
مرحله بعدی هفت تا فراخوانی با اندازه n/2 دارید ( با توجه به الگوریتم و مرتبه زمانی )
یعنی 7 تا 4*4
مرحله بعد 7 تا 2*2
و چون threshold شما 2*2 است , بقیه ضرب ها را به روش معمولی ضرب میکنیم
حالا اگه شما درخت رو نگاه کنین میبینین که 1+7+(2^7) فراخوانی ( با احتصاب فراخوانی در main ) دارید

[empoly]

با تشکز از شما
حق با شماست.
در مورد کلید هم می تونید به این آدرس مراجعه کنید.

[pesar irooni]

رابطه بازگشتی تعداد فراخوانی ها برای استراسن برابراست با:

T(n) = 7T(n/2)+1

T(2) = 1;

چون در هر بار فراخوانی 7 بار فراخوانی برای مسائل کوچکتر داریم و یکی هم که خود مساله اصلی است که فراخوانی شده:

T(8) = 7 * T(4) + 1 = 7 * (7 * T(2) + 1) + 1 = 7 * (7 * 1 + 1) + 1 = 57

تعداد ضربها وقتی که مساله کوچک ضرب ماتریسهای 2*2 باشد داریم

T(n) = 7T(n/2);

T(2) = 8;

عدد 8 از اینجا بدست اومده که ضرب دو ماتریس 2*2 از مرتبه n^3 میباشد و نیاز به 3^2=8 ضرب دارد

T(64) = 7*T(32) = 7*7*T(16) = 7*7*7T(8) = 7*7*7*7T(4) = 7*7*7*7*7*T(2) = 7*7*7*7*7*8 = 134456