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

تست ۵۱ نرم افزار ۸۷

ارسال:
۲۶ آبان ۱۳۹۰, ۰۱:۱۰ ق.ظ (آخرین ویرایش در این ارسال: ۲۶ آبان ۱۳۹۰ ۰۱:۱۲ ق.ظ، توسط Masoud05.)
تست ۵۱ نرم افزار ۸۷
این سوال قبلا یه بار بررسی شده اما از اونجایی که تست خوبی هست اون ارسال رو حذف میکنم تا سوالات تکراری نباشه( فقط ارسال خودم رو پاک میکنم و نه مال هیچکس دیگه!) و در ضمن یه بار با کمک هم این سوال قشنگ رو بررسی کنیم‌:



واللَّه خَیْرٌ وَأَبْقَى
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۲۶ آبان ۱۳۹۰, ۰۷:۱۲ ب.ظ (آخرین ویرایش در این ارسال: ۰۲ اردیبهشت ۱۳۹۱ ۰۲:۰۵ ب.ظ، توسط Masoud05.)
RE: تست ۵۱ نرم افزار ۸۷
خب کسی نظری نداره ؟! - جواب زیر همون جواب قبلی خودمه که دوباره گزاشتمش‌، اگه کسی راه بهتری بلده یا نکته ای میخواهد اضافه کنه‌، مطلبش رو همینجا بزاره.

از آنجایی که آرایه‌ها مرتب هستند پس یافتن میانه هر یک از آرایه‌ها مستقل از تعداد عناصر آرایه در زمان ثابت قابل یافتن است .
برای حل این مسئله تکنیک های زیادی وجود دارد اما با توجه به اینکه:

۱ )اگر مسائل را تقسیم کنیم و هر یک را جدا حل نماییم به جواب میرسیم
۲) حل زیر مسائل بهم وابسته نیست و فقط نتایج را با هم مقایسه میکنیم.

می توان نتیجه گرفت رهیافت تقسیم و غلبه برای حل این مسئله مناسب است.
اما تقسیم و غلبه چگونه این مسئله را حل می کند‌:

راه حل )میانه‌ها را به هم مقایسه کن‌، ۳ حالت رخ می دهد:

۱- میانه‌ها با هم برابرند ----> جواب کل همان میانه آرایه هاست - که البته چون اعداد از هم مجزا هستند این مورد برای این مسئله رخ نمی دهد.
۲- میانه آرایه ۱ از میانه آرایه ۲ بزرگتر است ----> نتیجه میگیریم که جواب در نیمه اول آرایه ۱ و یا نیمه دوم آرایه ۲ است چراکه در آرایه ۱ همانطور که گفته شد میانه این آرایه بزرگتر از مقدار مطلوب است پس باید به دنبال عناصر کوچکتراز میانه آرایه۱ که همان نیمه اول میشود گشت . همینطور هم اثبات میشود که باید دنبال عناصر بزرگتر از میانه در آرایه ۲ گشت که میشود نیمه دوم
۳- معکوس حالت ۲

در واقع با هر مرحله فراخوانی مجدد الگوریتم‌، هر آرایه نصف میشود پس در بدترین حالت باید به جایی برسیم که فقط هر زیر آرایه فقط ۱ عنصر دارد . این دنباله سبب ایجاد پیچیدگی زمانی لگاریتمی می شود:

[tex]T(2n)=T(n/2) T(n/2) O(1)=2T(n/2) O(1) = O(Log n)[/tex]

توجه داشته باشید که تعداد کل عناصر ۲n هست و زمان (O(1 جهت تقسیم و یک مقایسه ساده است و ما به دنبال (T(2n هستیم.

یعنی گزینه ۱ صحیح است.

واللَّه خَیْرٌ وَأَبْقَى
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: parimehraban , mfXpert , ayfer.a11 , firouzi.s , HRZ
ارسال:
۱۷ بهمن ۱۳۹۰, ۱۲:۲۶ ق.ظ
تست ۵۱ نرم افزار ۸۷
در مورد جواب اخر این سوال که نهایتا به لگاریتم میرسیم یه خورده توضیح بدین با تغییر متغیر به رادیکال ۲nمیرسیم و میدونیم رشد رادیکال بیشتر لگاریتم هست!
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۷ بهمن ۱۳۹۰, ۱۱:۲۳ ب.ظ (آخرین ویرایش در این ارسال: ۱۷ بهمن ۱۳۹۰ ۱۱:۲۸ ب.ظ، توسط Masoud05.)
RE: تست ۵۱ نرم افزار ۸۷
فرض کنید ‌: m =2n پس n/2= m/4 با توجه به ‌:

[tex]T(2n)=T(n/2) T(n/2) O(1)= 2T(n/2) O(1)=O(Log n)[/tex]

در نتیجه خواهیم داشت‌:


[tex]T(m)=T(m/4) T(m/4) O(1) = 2T(m/4) O(1) = O(Log m) = O(Log n)[/tex]

واللَّه خَیْرٌ وَأَبْقَى
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: HRZ
ارسال:
۱۸ بهمن ۱۳۹۰, ۱۱:۳۵ ق.ظ
تست ۵۱ نرم افزار ۸۷
بله اونو متوجه بودم اما در همین جا که m متغیر ما است جه طور
۲T(m/4)+O(1)0=O(Logm)

اگر از قضیه اصلی استفاده کنیم که میشه لگاریتم ام
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۹ بهمن ۱۳۹۰, ۱۱:۵۵ ب.ظ
RE: تست ۵۱ نرم افزار ۸۷
(۱۸ بهمن ۱۳۹۰ ۱۱:۳۵ ق.ظ)atharrashno نوشته شده توسط:  بله اونو متوجه بودم اما در همین جا که m متغیر ما است جه طور
۲T(m/4)+O(1)0=O(Logm)

اگر از قضیه اصلی استفاده کنیم که میشه لگاریتم ام
خب کافیه m رو به n تبدیل کنی تا جواب مورد نظر بدست بیاد!

واللَّه خَیْرٌ وَأَبْقَى
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۲۰ بهمن ۱۳۹۰, ۱۱:۱۴ ق.ظ
RE: تست ۵۱ نرم افزار ۸۷
[تصویر:  65884_1_1379095382.bmp]

where is my wro
ng?
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۲۰ بهمن ۱۳۹۰, ۰۱:۰۱ ب.ظ
RE: تست ۵۱ نرم افزار ۸۷
فکر کنم اگه این طوری بگیم بهتره:

[tex]t(2n)=t(2n/2) 1\Rightarrow t(2n)=t(n) 1\Rightarrow t(m)=t(m/2) 1\Rightarrow t(m)=o(logm)\Rightarrow t(n)=o(logn)[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۲۰ بهمن ۱۳۹۰, ۰۱:۰۸ ب.ظ
RE: تست ۵۱ نرم افزار ۸۷
(۲۰ بهمن ۱۳۹۰ ۰۱:۰۱ ب.ظ)saeedeh123 نوشته شده توسط:  فکر کنم اگه این طوری بگیم بهتره:

[tex]t(2n)=t(2n/2) 1\Rightarrow t(2n)=t(n) 1\Rightarrow t(m)=t(m/2) 1\Rightarrow t(m)=o(logm)\Rightarrow t(n)=o(logn)[/tex]
روش صحیحیش هم همینه . منم بالا در اولین ارسال همین رو نوشتم اما با تغییر متغیر هم میشه حلش کرد . تنها ابهامی که هست اینه که تعداد داده‌ها ۲n هست و همین باعث میشه این رابطه کمی گنگ به نظر بیاد در حالی که مسئله ساده ای هست .

واللَّه خَیْرٌ وَأَبْقَى
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۰
۲۱ بهمن ۱۳۹۰, ۰۸:۵۵ ب.ظ
RE: تست ۵۱ نرم افزار ۸۷
دوستان من بلا خره این طوری این قضیه را برا خودم هضم کردم:
تعداد عناصر بعد از هر مقایسه
[tex]2n-\frac{n}{2}-\frac{n}{2}=n[/tex]

پس [tex]T(2n)=T(n) O(1)[/tex]
حالا m=n
[tex]T(m)=T(\frac{m}{2}) O(1)[/tex]
,
اشتباه من این بود که اصولا نوشتن این جمله اشتباه است:
[tex]T(2n)=T(\frac{n}{2}) T(\frac{n}{2}) O(1)[/tex]
چراکه [tex]T(2n)[/tex] ارایه ای است نامرتب اما [tex]T(\frac{n}{2})[/tex] در مورد [tex]n[/tex] صحبت میکند که عناصر ان مرتب است
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۱
۲۱ بهمن ۱۳۹۰, ۱۱:۱۴ ب.ظ
RE: تست ۵۱ نرم افزار ۸۷
(۲۱ بهمن ۱۳۹۰ ۰۸:۵۵ ب.ظ)atharrashno نوشته شده توسط:  اشتباه من این بود که اصولا نوشتن این جمله اشتباه است:
[tex]T(2n)=T(\frac{n}{2}) T(\frac{n}{2}) O(1)[/tex]

چرا این غلطه ؟ بنظرم که درسته!

واللَّه خَیْرٌ وَأَبْقَى
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۲
۲۳ بهمن ۱۳۹۰, ۱۲:۲۶ ق.ظ
تست ۵۱ نرم افزار ۸۷
این جمله غلطه چون:
۱ شما با این رابطه ای که از معادله بازگشتی بالا بدست میاد نمیتونید به لگاریتم برسید
۲ دلیل اصلی این قصه اینه که t(n/2نمونه کوچک شده ای از t(2nنیست شما میانه را در t(n/2 با درجه یک بدست می اورید چون از خاصیت مرتب بودن اعضا در n عنصر استفاده کرده‌اید اما در t(2nاثبات میشود که پیدا کردن میانه از درجه logn است
مساله ما به دو زیر مساله تقسم نمیشود اما اعضای ما در هرمقایسه نصف میشود

۳ با ادرس مقسمی حل کامل این الگوریتم درصحفه۷۵ کتاب design and analysis of parallel algorithm manual solutionموجود است چون تمامی لینک‌ها برای من ف‌ی ل ت ر بود به پاسخ دست پیدا نکردم اگر شما دارید دانلود کنید و تصویر پاسخ را برای ما به اشتراک بگزارید
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۳
۲۳ بهمن ۱۳۹۰, ۰۲:۰۶ ق.ظ
RE: تست ۵۱ نرم افزار ۸۷
بچه‌ها روش حل من چطوره؟
ضمنا این سوال هوشه نه نرم افزار، درسته؟
[tex]t(2n)=t(\frac{n}{2}) t(\frac{n}{2}) O(1)[/tex]
با تغییر متغیر m=2n داریم:
[tex]t(m)=t(\frac{m}{4}) t(\frac{m}{4}) O(1)[/tex]
که برابر است با:
[tex]t(m)=2t(\frac{m}{4}) O(1)[/tex]
و داریم:
[tex]g(m)=m^{log_{4}^{2}}=m^{\frac{1}{log_{2}^{4}}}=\sqrt{m}[/tex]
حالا بجای m مقدار ۲n رو قرار می دهیم و داریم:
[tex]\sqrt{m}=\sqrt{2n}\in O(\sqrt{n})[/tex]

کجا دارم اشتباه می کنم؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال: #۱۴
۲۳ بهمن ۱۳۹۰, ۰۱:۴۷ ب.ظ (آخرین ویرایش در این ارسال: ۲۳ بهمن ۱۳۹۰ ۰۱:۵۷ ب.ظ، توسط Aurora.)
RE: تست ۵۱ نرم افزار ۸۷
(۲۳ بهمن ۱۳۹۰ ۱۲:۲۶ ق.ظ)atharrashno نوشته شده توسط:  این جمله غلطه چون:
۱ شما با این رابطه ای که از معادله بازگشتی بالا بدست میاد نمیتونید به لگاریتم برسید
۲ دلیل اصلی این قصه اینه که t(n/2نمونه کوچک شده ای از t(2nنیست شما میانه را در t(n/2 با درجه یک بدست می اورید چون از خاصیت مرتب بودن اعضا در n عنصر استفاده کرده‌اید اما در t(2nاثبات میشود که پیدا کردن میانه از درجه logn است
مساله ما به دو زیر مساله تقسم نمیشود اما اعضای ما در هرمقایسه نصف میشود

۳ با ادرس مقسمی حل کامل این الگوریتم درصحفه۷۵ کتاب design and analysis of parallel algorithm manual solutionموجود است چون تمامی لینک‌ها برای من ف‌ی ل ت ر بود به پاسخ دست پیدا نکردم اگر شما دارید دانلود کنید و تصویر پاسخ را برای ما به اشتراک بگزارید
من این کتابو پیدا کردم نمی دونم همون کتابی که شما نوشتید هست یانه ولی صفحه ۷۴ و ۷۵ درباره همین سوال توضیح داده.

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

(۲۳ بهمن ۱۳۹۰ ۰۲:۰۶ ق.ظ)پشتکار نوشته شده توسط:  بچه‌ها روش حل من چطوره؟
ضمنا این سوال هوشه نه نرم افزار، درسته؟
[tex]t(2n)=t(\frac{n}{2}) t(\frac{n}{2}) O(1)[/tex]
با تغییر متغیر m=2n داریم:
[tex]t(m)=t(\frac{m}{4}) t(\frac{m}{4}) O(1)[/tex]
که برابر است با:
[tex]t(m)=2t(\frac{m}{4}) O(1)[/tex]
و داریم:
[tex]g(m)=m^{log_{4}^{2}}=m^{\frac{1}{log_{2}^{4}}}=\sqrt{m}[/tex]
حالا بجای m مقدار ۲n رو قرار می دهیم و داریم:
[tex]\sqrt{m}=\sqrt{2n}\in O(\sqrt{n})[/tex]

کجا دارم اشتباه می کنم؟
شما با توجه به رابطه اولی که نوشتید یعنی[tex]t(2n)=t(\frac{n}{2}) t(\frac{n}{2}) O(1)[/tex] ادامه جواب را درست حل کردید ولی
احتمالا چون دوتا رابطه باید باهم حل بشند یعنی اینکه به هم وابسته هستند باید به صورت
[tex]t(2n)=t(n) O(1)[/tex] نه اینکه هر کدام را جدا بنویسیم.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Masoud05 , پشتکار , HRZ
ارسال: #۱۵
۲۳ بهمن ۱۳۹۰, ۰۵:۲۶ ب.ظ
RE: تست ۵۱ نرم افزار ۸۷
لینک
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  علوم کامپیوتر شریف یا نرم افزار تهران؟ ۴L1R3Z4 ۴۴ ۲۷,۹۴۰ ۰۶ شهریور ۱۴۰۲ ۰۸:۱۲ ب.ظ
آخرین ارسال: moeinbahari
  جزوه خلاصه نکات مهم فصول ابتدایی درس مهندسی نرم افزار Happiness.72 ۱ ۳,۴۸۷ ۱۳ خرداد ۱۴۰۱ ۰۶:۲۸ ب.ظ
آخرین ارسال: M o h m m @ d
  مهندسی نرم افزار rh1995 ۰ ۱,۳۱۴ ۱۰ بهمن ۱۴۰۰ ۰۷:۰۹ ب.ظ
آخرین ارسال: rh1995
  مهندسی نرم افزار rh1995 ۰ ۱,۱۱۶ ۱۰ بهمن ۱۴۰۰ ۰۷:۰۸ ب.ظ
آخرین ارسال: rh1995
  آزمون دکتری نرم افزار و الگوریتم ۱۴۰۰ Seyyedab ۴۶ ۱۷,۸۳۳ ۰۹ مهر ۱۴۰۰ ۰۵:۳۷ ب.ظ
آخرین ارسال: Seyyedab
  فیلم های مهندسی نرم افزار خلیلی فر osouly ۰ ۱,۹۰۰ ۰۶ اردیبهشت ۱۴۰۰ ۰۴:۴۴ ب.ظ
آخرین ارسال: osouly
  کارنامه نهایی ازمون دکتری داخل سال ۱۳۹۲-گرایش نرم افزار انرژی مثبت ۶ ۹,۳۳۲ ۱۷ بهمن ۱۳۹۹ ۰۲:۲۷ ق.ظ
آخرین ارسال: hmaryam567
Heart نرم افزار رها بختیاری ۰ ۲,۹۸۸ ۰۵ بهمن ۱۳۹۹ ۰۲:۵۱ ب.ظ
آخرین ارسال: رها بختیاری
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۲۰,۹۵۷ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  آزمون دکتری نرم افزار و الگوریتم ۹۹ Seyyedab ۱۱ ۵,۶۹۳ ۰۲ شهریور ۱۳۹۹ ۱۱:۰۳ ق.ظ
آخرین ارسال: Seyyedab

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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