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

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

ارسال:
  

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 نیاز داریم
لطفا بگویید کجا را اشتباه می کنم


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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال درباره طراحی سایت و جدول ahantell ۰ ۱۰۰ ۰۲ مرداد ۱۳۹۹ ۱۰:۴۳ ق.ظ
آخرین ارسال: ahantell
Video دانلود رایگان نکته و تست احتمال و آمار مهندسی Farzamm ۰ ۲۶۷ ۱۸ خرداد ۱۳۹۹ ۰۱:۲۹ ب.ظ
آخرین ارسال: Farzamm
  طراحی سایت شرکتی ideasoft98 ۰ ۱۰ ۲۶ اسفند ۱۳۹۸ ۰۲:۵۶ ب.ظ
آخرین ارسال: ideasoft98
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۴۸۰ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t
  تاثیر بودجه در انتخاب شرکت طراحی سایت wone ۱ ۲۰ ۲۳ آبان ۱۳۹۸ ۰۱:۱۴ ب.ظ
آخرین ارسال: xiaomi
  ضرب ماتریس ها roller1829 ۰ ۳۴۶ ۱۹ مهر ۱۳۹۸ ۰۲:۴۸ ب.ظ
آخرین ارسال: roller1829
Exclamation زمان برگزاری کنکور ارشد ۹۸ به تعویق افتاد elect ۲ ۶۹۲ ۱۳ مهر ۱۳۹۸ ۰۵:۲۴ ب.ظ
آخرین ارسال: saharfarhang
  طراحی یک سیستم نورانی هوشمند marvelous ۸ ۸۸۴ ۲۸ مرداد ۱۳۹۸ ۰۳:۵۰ ق.ظ
آخرین ارسال: marvelous
Star ایده طراحی یک وب سایت stabesh ۱ ۶۳۷ ۱۹ مرداد ۱۳۹۸ ۱۱:۱۳ ب.ظ
آخرین ارسال: attarud
  طراحی و چاپ کاتالوگ - اصول مهم و کاربردی طراحی بنر aframehr ۰ ۳۹۳ ۲۵ تیر ۱۳۹۸ ۱۲:۵۳ ق.ظ
آخرین ارسال: aframehr

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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