زمان کنونی: ۲۶ مهر ۱۳۹۶, ۰۲:۳۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)
ارسال:
  

rad.bahar پرسیده:

تست طراحی الگوریتم مهندسی ۸۹ (زمان مصرفی در ضرب ماتریس ها)

ماتریس های Ak ماتریسی به شکل ۲ به توان k در ۲ به توان k است و v برداری ستونی به طول
n = 2^k است برای ضرب Ak.V زمان مصرفی چقدر است
جواب:nlogn
راه حلی که استفاده کردم اینه
اگر از روش تقسیم و غلبه استفاده کنیم ماتریس Ak باید ۴ تکه و ماتریس V دو تکه شوند در صرب این ۴ تکه در ۲ تکه ۴ ارایه ۲ به توان k-1 در ۲ به توان k-1 ایجاد می شود ۲ تا از ارایه‌ها با هم و ۲ تا دیگرشان با هم جمع می شوند که از مرتبه طول v یعنی n است
پس رابطه بازگشتی برابر t(n) =4t(n/2) + n است ولی جواب حاصل از مرتبه n^2 است
ایا راهی هست که از مرتبه nlogn باشد؟

لطفا جواب بدید
مشاهده‌ی وب‌سایت کاربر

۲
ارسال:
  

homa پاسخ داده:

RE: مهندسی ۸۹

(۰۵ بهمن ۱۳۹۰ ۰۱:۱۸ ق.ظ)rad.bahar نوشته شده توسط:  ماتریس های Ak ماتریسی به شکل ۲ به توان k در ۲ به توان k است و v برداری ستونی به طول
n = 2^k است برای ضرب Ak.V زمان مصرفی چقدر است
جواب:nlogn
راه حلی که استفاده کردم اینه
اگر از روش تقسیم و غلبه استفاده کنیم ماتریس Ak باید ۴ تکه و ماتریس V دو تکه شوند در صرب این ۴ تکه در ۲ تکه ۴ ارایه ۲ به توان k-1 در ۲ به توان k-1 ایجاد می شود ۲ تا از ارایه‌ها با هم و ۲ تا دیگرشان با هم جمع می شوند که از مرتبه طول v یعنی n است
پس رابطه بازگشتی برابر t(n) =4t(n/2) + n است ولی جواب حاصل از مرتبه n^2 است
ایا راهی هست که از مرتبه nlogn باشد؟

لطفا جواب بدید

اینجا تمام ماتریس‌ها با هم برابر ند چون همه رو با متغیر A مشخص کرده و اندیس کنارشون فقط اندازه‌ی اونها رو نشون میده و همین طور گفته:
[tex]A_{0}=[1][/tex]
و در مورد:
[tex]A_{1}=\begin{bmatrix} 1 &1 \\ 1& 1 \end{bmatrix}[/tex]
[tex]A_{1}=\begin{bmatrix} 1 &1 &1 &1 \\ 1 & 1 & 1 & 1\\ 1& 1 & 1 &1 \\ 1 & 1 & 1& 1 \end{bmatrix}[/tex]

تو مسائلی که بخایم مرتبه زمانی بدست بیاریم معمولا باید بهترین راه حل رو انتخاب کنیم:
حالا با توجه به شکلی که گذاشته بودی ومنم اینجا پیوست کردم:
A1 با A2 تو ماتریس برابر ند پس من میتونم فاکتور گیری رو انجام بدم که میشه:

[tex]A_{1}(V_{1} V_{2})[/tex] یا [tex]A_{2}(V_{1} V_{2})[/tex]

اینجا من یک ضرب دارم و یک جمع
زمان جمع به n/2 نیاز داره و ضرب هم میشه:

[tex]T(\frac{n}{2})[/tex]

برای قسمت پایین هم همینه پس کلا داریم:
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) (\frac{n}{2} \frac{n}{2})=2T(\frac{n}{2}) n[/tex]


که برابر هست با: nlogn


فایل‌(های) پیوست شده

ارسال:
  

rad.bahar پاسخ داده:

RE: مهندسی ۸۹

(۰۹ بهمن ۱۳۹۰ ۱۱:۵۶ ب.ظ)homa نوشته شده توسط:  
(05 بهمن ۱۳۹۰ ۰۱:۱۸ ق.ظ)rad.bahar نوشته شده توسط:  

اینجا تمام ماتریس‌ها با هم برابر ند چون همه رو با متغیر A مشخص کرده و اندیس کنارشون فقط اندازه‌ی اونها رو نشون میده و همین طور گفته:
[tex]A_{0}=[1][/tex]
و در مورد:
[tex]A_{1}=\begin{bmatrix} 1 &1 \\ 1& 1 \end{bmatrix}[/tex]
[tex]A_{1}=\begin{bmatrix} 1 &1 &1 &1 \\ 1 & 1 & 1 & 1\\ 1& 1 & 1 &1 \\ 1 & 1 & 1& 1 \end{bmatrix}[/tex]

تو مسائلی که بخایم مرتبه زمانی بدست بیاریم معمولا باید بهترین راه حل رو انتخاب کنیم:
حالا با توجه به شکلی که گذاشته بودی ومنم اینجا پیوست کردم:
A1 با A2 تو ماتریس برابر ند پس من میتونم فاکتور گیری رو انجام بدم که میشه:

[tex]A_{1}(V_{1} V_{2})[/tex] یا [tex]A_{2}(V_{1} V_{2})[/tex]

اینجا من یک ضرب دارم و یک جمع
زمان جمع به n/2 نیاز داره و ضرب هم میشه:

[tex]T(\frac{n}{2})[/tex]

برای قسمت پایین هم همینه پس کلا داریم:
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) (\frac{n}{2} \frac{n}{2})=2T(\frac{n}{2}) n[/tex]


که برابر هست با: nlogn

ممنون از جوابتان
با این حساب A1 و A2 و A3 و A4 با هم برابرند پس کافبه مثلا A1(V1+V2 را حساب کرد و تنها با همین مقدار نتیجه را به دست اورد
به شمل ضمیمه نگاه کنید
پس یعنی یک ضرب و یک جمع
T(n )= T(n/2)+n
که میشه از مرتبه n
لطفا بگویید کجا را اشتباه می کنم


فایل‌(های) پیوست شده

مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

homa پاسخ داده:

RE: مهندسی ۸۹

(۰۵ بهمن ۱۳۹۰ ۰۱:۱۸ ق.ظ)rad.bahar نوشته شده توسط:  ماتریس های Ak ماتریسی به شکل ۲ به توان k در ۲ به توان k است و v برداری ستونی به طول
n = 2^k است برای ضرب Ak.V زمان مصرفی چقدر است
جواب:nlogn
راه حلی که استفاده کردم اینه
اگر از روش تقسیم و غلبه استفاده کنیم ماتریس Ak باید ۴ تکه و ماتریس V دو تکه شوند در صرب این ۴ تکه در ۲ تکه ۴ ارایه ۲ به توان k-1 در ۲ به توان k-1 ایجاد می شود ۲ تا از ارایه‌ها با هم و ۲ تا دیگرشان با هم جمع می شوند که از مرتبه طول v یعنی n است
پس رابطه بازگشتی برابر t(n) =4t(n/2) + n است ولی جواب حاصل از مرتبه n^2 است
ایا راهی هست که از مرتبه nlogn باشد؟

لطفا جواب بدید
روشت کاملا درسته اما جایی که اشتباه کردی اینه که تمام ۴ مولفه که بدست اوردی رو با هم جمع میکنی در صورتی که جوابی که بدست میاد یک ماتریس ستونی هست با n مولفه یعنی همون ۲ به توان k.
پس فقط کافیه ۲ تا مولفه هایی که از ضرب سطر بالایی ماتریس n*n در ماتریس ستونی بدست اومده با هم جمع کنی.
که میشه:
[tex]T(n)=2T(\frac{n}{2}) O(n)[/tex]
پس همون --->
[tex]O(nlogn)[/tex]

ارسال:
  

rad.bahar پاسخ داده:

RE: مهندسی ۸۹

با تشکر ار جوابتان ولی متوحه نشدم
به نظر من ۲ تا از ۴ مولفه حاصل با هم و ۲ تای دیگر با هم جمع می شوند شکلی ضمبمه کردم تا راه حل را ببینید در اینحا ۴ مولفه A1*V1 , A2*V2 , A3*V1 , A4*V2 داریم که برای به دست اوردن
ماتریس ستونی حاصل از ضرب به ۲ جمع زیر نیاز داریم
A1*V1 + A2*V2 , A3*V1 + A4*V2
نتیحه حاصل اینکه یه ۴ فراخوانی بازگشتی ضرب N/2 در N/2 نیاز داریم
لطفا بگویید کجا را اشتباه می کنم


فایل‌(های) پیوست شده

مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پاسخنامه تشریحی طراحی الگوریتم موسسه ماهان برای درس طراحی الگوریتم کنکور ۹۱ مهندسی MSsoftware ۸ ۶,۱۲۵ ۰۴ بهمن ۱۳۹۱ ۱۲:۰۲ ق.ظ
آخرین ارسال: fa_karoon
  تست ۳۸ طراحی الگوریتم سال ۸۵ پشتکار ۱۰ ۲,۸۴۹ ۲۹ دى ۱۳۹۱ ۰۹:۲۴ ب.ظ
آخرین ارسال: csharpisatechnology
  تست ۴۰ طراحی الگوریتم نرم افزار ۸۶ reyhaneh64 ۲ ۱,۶۰۲ ۲۹ دى ۱۳۹۱ ۰۲:۱۲ ب.ظ
آخرین ارسال: csharpisatechnology
  بررسی سوالات طراحی الگوریتم ۹۱ مهندسی کامپیوتر -گرایش هوش fatima1537 ۸۶ ۳۰,۱۴۵ ۲۰ اسفند ۱۳۹۰ ۰۹:۴۰ ب.ظ
آخرین ارسال: anyone
  تست (مرتبه اجرایی ) طراحی الگوریتم کنکور ۹۱ vijay ۷ ۳,۱۶۸ ۱۵ اسفند ۱۳۹۰ ۰۵:۳۴ ب.ظ
آخرین ارسال: لهمشد
  بررسی سوالات طراحی الگوریتم ۹۱ فناوری اطلاعات uniquegirl ۲۸ ۷,۹۷۵ ۰۶ اسفند ۱۳۹۰ ۱۱:۲۶ ب.ظ
آخرین ارسال: rotbe
  تست (گراف) طراحی الگوریتم آی تی کنکور ۹۱ vijay ۴ ۲,۶۹۴ ۰۱ اسفند ۱۳۹۰ ۰۶:۴۰ ق.ظ
آخرین ارسال: MSZ
  تست مرتبه اجرایی طراحی الگوریتم کنکور ۹۱ vijay ۲ ۲,۴۲۳ ۳۰ بهمن ۱۳۹۰ ۰۱:۵۴ ب.ظ
آخرین ارسال: arixooo
  تست ۳۲ طراحی الگوریتم سال ۹۰ Anahita.R ۳ ۲,۰۶۱ ۲۶ بهمن ۱۳۹۰ ۱۱:۳۶ ق.ظ
آخرین ارسال: atharrashno
  تست (درخت) طراحی الگوریتم آی تی سال ۸۸ netsupport ۲ ۱,۵۰۲ ۲۴ بهمن ۱۳۹۰ ۰۶:۳۳ ب.ظ
آخرین ارسال: homa

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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