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

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

ارسال:
  

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


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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  [دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی هاتف ۳۳ ۴۰,۷۹۳ ۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ
آخرین ارسال: solmaz58
  درخواست تصحیح (تعویق) زمان کنکور ارشد ۱۴۰۱ s.gg ۱ ۱۴ ۲۳ بهمن ۱۴۰۱ ۰۷:۴۳ ب.ظ
آخرین ارسال: HamidReza1
Video دانلود رایگان نکته و تست شبکه های کامپیوتری Farzamm ۱۱ ۱۷,۶۰۶ ۰۷ بهمن ۱۴۰۰ ۰۱:۰۳ ب.ظ
آخرین ارسال: M.rahimi20
  تعویق زمان کنکور ارشد sima84 ۰ ۱,۴۷۳ ۱۸ اردیبهشت ۱۴۰۰ ۰۱:۰۵ ب.ظ
آخرین ارسال: sima84
  فیلم های مهندسی نرم افزار خلیلی فر osouly ۰ ۱,۹۰۲ ۰۶ اردیبهشت ۱۴۰۰ ۰۴:۴۴ ب.ظ
آخرین ارسال: osouly
  طراحی ui/ux kimiya1234 ۲ ۲,۰۰۹ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۲ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  طراحی یک سیستم عامل (از صفر) sina4everafter ۱۲ ۱۵,۶۲۵ ۰۶ بهمن ۱۳۹۹ ۱۲:۵۳ ب.ظ
آخرین ارسال: nahalmomen2007@yahoo.com
  طراحی سایت ریسپانسیو wikidemy1 ۰ ۱,۶۰۲ ۱۳ دى ۱۳۹۹ ۰۴:۰۱ ب.ظ
آخرین ارسال: wikidemy1
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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