(۲۷ بهمن ۱۳۹۱ ۱۱:۳۵ ب.ظ)farid_express نوشته شده توسط:  

نقل قول: سلام، تحلیل یو خ مفید بود برام - ممنون، فقط من تحلیل خودمو مینویسم یه نگا بنداز اشکالشو بگیر
منمیگم باید جایگشت های مختلف آرایه رو در نظر بگیریم به طوری که از بهترین حالت برای رفتن به سطر ۴ و آپدیت min تا بدترین حالتش اتفاق بیفته، بهترین حالت زمانیه ک Min تو خونه اول باشه و ۰ آپدیت داریم همینطور میتونیم جایگشتی رو در نظر بگیریم ک min تو خونه دوم باشه که ۱ دونه آپدیت داریم ... تا n-1 آپدیت، حالا از یه طرف دیگه ما کلا !n جایگشت برای آرایه داریم یعنی با احتمال [tex]\frac{1}{n!}[/tex] جایگشت داریم برای انتخاب آرایه، بعدشم فرض کن min تو خونه اول باشه یعنی ۰ آپدیت برای همچین حالتی !(n-1) داریم همینطور اگه تو خونه دوم باشه باز !(n-1) و ... حالا اگه از امید ریاضی استفاده کنیم با تابع چگالی احتمال [tex]\frac{1}{n!}[/tex] داریم:
[tex]\frac{1}{n!}\sum_{i=0}^{n-1}i(n-1)!=\frac{1}{n}\sum_{i=0}^{n-1}i=\frac{n(n-1)}{2n}=\frac{n-1}{2}=\Theta (n)[/tex]

سلام
من به تحلیل شما زیاد وارد نمیشم() ولی اشکالاتی که وجود داره رو اشاره میکنم بهشون
۱-اگه min عنصر اول باشه سطر چهارم ۱ بار اجرا میشه نه ۰ بار(چون min در ابتدا بینهایت هستش!)
۲-شما میگی اگه تو یه جایگشت خاص min تو مکان i باشه حتما i یا i-1 (مهم نیس حالا!) بار باید آپدیت شه ولی اینطوری نیس.
مثلا اگه بگیری [tex]2 , 3, 4, 5, ... n-1, 1[/tex] که min خونه آخره در واقع فقط ۲ بار آپدیت انجام میشه.
در واقع اگه بخواییم از این روش تحلیل استفاده کنیم کار خیلی سخت میشه. واسه اینکه به حرف من برسی برای n=4 که ۲۴ تا جایگشت داریم یه بار امتحان کن. تو ۶ جایگشت ۱ تعویض، تو ۱۱ جایگشت ۲ تعویض، تو ۶ جایگشت ۳ تعویض و فقط وقتی آرایه مرتب نزولی باشه ۴ بار تعویض انجام میشه-یعنی به این راحتی نمیشه شمارش انجام داد(بر اساس تحلیل شما)
واسه همین نمیگم تحلیلت نادرسته ولی اگه دقیقترش کنی شاید به زمان لگاریتمی نزدیک بشی!

بازم شاید من تحلیل شما رو خوب متوجه نشده باشم. اگه اینطوریه لطفا روشنم کنید.

(۰۵ اسفند ۱۳۹۱ ۰۱:۴۹ ق.ظ) MajidManesht2012 نوشته شده توسط:  منمیگم باید جایگشت های مختلف آرایه رو در نظر بگیریم به طوری که از بهترین حالت برای رفتن به سطر ۴ و آپدیت min تا بدترین حالتش اتفاق بیفته، بهترین حالت زمانیه ک Min تو خونه اول باشه و ۰ آپدیت داریم همینطور میتونیم جایگشتی رو در نظر بگیریم ک min تو خونه دوم باشه که ۱ دونه آپدیت داریم ... تا n-1 آپدیت، حالا از یه طرف دیگه ما کلا !n جایگشت برای آرایه داریم یعنی با احتمال جایگشت داریم برای انتخاب آرایه، بعدشم فرض کن min تو خونه اول باشه یعنی ۰ آپدیت برای همچین حالتی !(n-1) داریم همینطور اگه تو خونه دوم باشه باز !(n-1) و ...

(۲۴ بهمن ۱۳۹۱ ۰۴:۰۶ ب.ظ)farid_express نوشته شده توسط:  واسه اینکه به حرف من برسی برای n=4 که ۲۴ تا جایگشت داریم یه بار امتحان کن. تو ۶ جایگشت ۱ تعویض، تو ۱۱ جایگشت ۲ تعویض، تو ۶ جایگشت ۳ تعویض و فقط وقتی آرایه مرتب نزولی باشه ۴ بار تعویض انجام میشه

(۲۷ بهمن ۱۳۹۱ ۰۹:۵۸ ب.ظ)MajidManesht2012 نوشته شده توسط:  سلام، تحلیل یو خ مفید بود برام - ممنون، فقط من تحلیل خودمو مینویسم یه نگا بنداز اشکالشو بگیر
منمیگم باید جایگشت های مختلف آرایه رو در نظر بگیریم به طوری که از بهترین حالت برای رفتن به سطر ۴ و آپدیت min تا بدترین حالتش اتفاق بیفته، بهترین حالت زمانیه ک Min تو خونه اول باشه و ۰ آپدیت داریم همینطور میتونیم جایگشتی رو در نظر بگیریم ک min تو خونه دوم باشه که ۱ دونه آپدیت داریم ... تا n-1 آپدیت، حالا از یه طرف دیگه ما کلا !n جایگشت برای آرایه داریم یعنی با احتمال [tex]\frac{1}{n!}[/tex] جایگشت داریم برای انتخاب آرایه، بعدشم فرض کن min تو خونه اول باشه یعنی ۰ آپدیت برای همچین حالتی !(n-1) داریم همینطور اگه تو خونه دوم باشه باز !(n-1) و ... حالا اگه از امید ریاضی استفاده کنیم با تابع چگالی احتمال [tex]\frac{1}{n!}[/tex] داریم:
[tex]\frac{1}{n!}\sum_{i=0}^{n-1}i(n-1)!=\frac{1}{n}\sum_{i=0}^{n-1}i=\frac{n(n-1)}{2n}=\frac{n-1}{2}=\Theta (n)[/tex]

(۲۷ بهمن ۱۳۹۱ ۰۱:۴۶ ب.ظ)۶۶الی نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۱۱:۲۰ ق.ظ)vahidfrr نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط:  سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.

---

در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.

در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد

سوال ۴۹ اولی نادرست چون وقتی گفته چند باد عنصر کوچکتر یا بزرگتر پس logn نمی شه چون چند بار succ یا pere باید صدا زده شه
ولی دومی درست بود

---

(۲۲ بهمن ۱۳۹۱ ۰۲:۳۷ ب.ظ)ADELZX نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۲:۳۵ ب.ظ)mfXpert نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۲:۲۴ ب.ظ)ADELZX نوشته شده توسط:  توی صورت سوال o کوچیک گذاشته .
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟

چه نتیجه‌ای از این حرف شما باید گرفت؟

خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟

در کمتر logn میشه چون heapify زمانش کمتر از logn

(۲۵ بهمن ۱۳۹۱ ۱۱:۰۹ ب.ظ)mehdi3254 نوشته شده توسط:  سوال ۴۸ یکم مشکوکه و فقط نظر طراح میتونه قبول بشه!!!!(متاسفانه)
البته به نظر من nk میشه چون بقیه گزینه ها یه جورایی هم ارز هستند! البته نه هم ارز ریاضی هم ارز از لحاظ مرتبه زمانی!

(۳۰ بهمن ۱۳۹۱ ۱۰:۳۱ ب.ظ)fsi2013 نوشته شده توسط:  سوال ۵۲ مگه منفی بی نهایت رو توی مین نذاشته؟؟؟؟!!!!
پس چطوری شرط until درست میشه؟

نقل قول: با استاد هادی یوسفی حل کردیم این سوال رو و گزینه ۴ درست میشه.

(۰۱ اسفند ۱۳۹۱ ۰۶:۵۷ ب.ظ)farid_express نوشته شده توسط:  اون مثبت بی نهایته. در واقع اشتباه تایپی هست ولی باید خیلی راحت حدس میزدین اینو.

(۰۱ اسفند ۱۳۹۱ ۰۶:۵۷ ب.ظ)farid_express نوشته شده توسط:  اگه درخت بازگشت بکشید جواب همون nk میاد. بعید میدونم گزینه ۴ درست باشه.

نقل قول: نمیشه به راحتی حدس زد.به حرف آسونه ولی داوطلبی که سرجلسه است خیلی به سنجش و کادرش اعتماد داره.دیگه سرجلسه واقعا جایی برای در نظر گرفتن احتمالاتی مثل اشتباه تایپی نیست.من روز قبلش کنکور علوم رو هم دادم اونجا هم دو سه سئوال رو حدس زدم.دیگه نمیشه زیادی بر اساس حدس پیش رفت

نقل قول: این که کپی سئوال چند سال پیش آی تی است(فکر کنم سال ۹۰)توی کتب دیگه هم درخت بازگشتش رو کشیدند ولی اونجا گزینه ۱ نشده.! یعنی سنجش با خودش هم تناقض داره؟!

(۰۲ اسفند ۱۳۹۱ ۱۲:۵۱ ق.ظ)arta.66 نوشته شده توسط:  نظرای آقا فرید در مورد سوالای ساختمان درست هستش به جز سوال ۵۲ که بهش شک دارم بقیه درست هستن!! فقط نمی دونم چرا یه حس پلیسی بهم میگه آقا فرید یه ربطی به این سوالا داره!!!! بابا یکم آسونتر طرح میکردی مگه چی می شد؟؟؟

(۰۵ اسفند ۱۳۹۱ ۱۰:۲۴ ب.ظ)ebi87 نوشته شده توسط:  

(23 بهمن ۱۳۹۱ ۰۶:۱۶ ب.ظ)MajidManesht2012 نوشته شده توسط:  حل سوال ۴۸ ساختمان نرم افزار - گزینه ۱ دفترچه B

دوست عزیز این سری را چطوری شما حساب کردین!
میدونیم که حداکثر عمق درخت بازگشتی برابر خواهد بود با [tex]\dpi{150} \log_{2}n \log_{4}k[/tex] و در هر سطح هزینه برابر است با [tex]\dpi{150} \frac{3^i}{4^i}nk[/tex]
که یک سری هارمونیک میشه و باید ازش انتگرال گرفته بشه به صورت زیر:

[tex]\dpi{150} \sum_{i=0}^{\log_{2}n \log_{4}k}{\frac{3^i} {4^i}nk}= nk\sum_{i=0}^{\log_{2}n \log_{4}k}{\frac{3^i} {4^i}}= nk \int_{0}^{\log_{2}n \log_{4}k}{\frac{3^i} {4^i}di}[/tex]
البته این نظر من هست شاید اشتباه کرده باشم
نظر شما چیه دوستان؟

نقل قول: من حداکثر عمق درخت بی نهایت در نظر میگیرم، قبول دار ی که بینهایت از logn+logk بیش تره حالا سری هندسی با قدر نسبت کمتر از یک رو اینجوری حل می کنم:
می دانیم:
[tex]\sum_{0}^{\infty}a^{i}=\frac{1}{1-a} , \left | a \right |<1[/tex]
پس:
[tex](nk)\sum_{0}^{\infty }(3/4)^{i} = \frac{1}{1-\frac{3}{4}}nk=4nk[/tex]
چون ارتفاع درخت رو بینهایت فرض کردم nk ماکزیمم مرتبه ایه که میتونه داشته با شه و دیگه مهم نیست که بیایم ارتفاع دقیق و محدود در نظر بگیریم.