انجمنصفحه اولجستجوی انجمن

[MajidManesht2012]

(۲۷ بهمن ۱۳۹۱ ۱۱:۳۵ ب.ظ)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 که ۲۴ تا جایگشت داریم یه بار امتحان کن. تو ۶ جایگشت ۱ تعویض، تو ۱۱ جایگشت ۲ تعویض، تو ۶ جایگشت ۳ تعویض و فقط وقتی آرایه مرتب نزولی باشه ۴ بار تعویض انجام میشه-یعنی به این راحتی نمیشه شمارش انجام داد(بر اساس تحلیل شما)
واسه همین نمیگم تحلیلت نادرسته ولی اگه دقیقترش کنی شاید به زمان لگاریتمی نزدیک بشی!

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

آره، به این سادگی ها نمیشه شمرد، نظم و قانونی توش پیدا نکردم- بالاخره ما رو یه کوچولو به Logn نزدیک کردی! ولی روش قانونمند اثباتش بلد نیستم

[oli92]

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

اگه به جای n-1 توی سیگما n-i قرار بدید به مقدار واقعی نزدیک تر می شه.

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

با یکی دو مثال در مقیاس کوچیک نمی شه تشخیص درستی داد.

اگه بخوای درست حسابش کنیم باید تابع بازگشتی زیر رو حل کرد که تعداد مقایسها رو توی کل حالات میده و بعد بر n! تقسیم کنی.
T(n)=n!+sum{(T(i-1) * (n-1)! / (i-1)! } i=1..n

[mizgly]

سوال ۵۲ رو به یک روش دیگه هم میشه حل کرد
فرض کنید عناصر آرایه رو به ترتیب داخل یک BST درج کنیم
در این صورت زمانی دستوری انتساب انجام میشه که یه عنصر در سمت چپ ترین برگ قرار بگیره
پس تعداد دفعات اجرای دستور انتساب طول شاخه سمت چپ درخت BST حاصل از اون جایگشت هست
که می‌دونیم در حالت میانگین ارتفاعش logn هست

بیان دیگر این راه حل:
در ابتدا ما n کاندیدا برای انتساب شدن به min آرایه داریم. بعد از اولین انتساب که در خونه اول رخ میده کاندیداها میشن اونهایی که از خونه اول کوچکتر باشن که تعدادشون از ۰ تا n-1 هست. در حالت میانگین n/2 عناصر کاندیدا میمونن و بعد از دومین انتساب n/4 عناصر و... یعنی:
T(n) = T(n/2) + 1 که logn هست

---

(۲۷ بهمن ۱۳۹۱ ۰۹:۵۸ ب.ظ)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]

اشکال اثبات شما در اینه که وقتی iمین عنصر میشه min این به این معنی نیست که تا اونجا i بار انتساب انجام شده
به عنوان مثال حالتی که در اون n-1 بار انتساب بعد از بار اول رخ بده تعداد جایگشت هایی که این حالت رو دارن فقط یک دونه است ولی شما [tex](n-1)![/tex] بار اونو می شمارید

[freidoony]

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

(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

وقتی عبارت o(logn) میاد یعنی مرتبه زمانی از logn کوچکتر باشه مثلا loglogn یا رادیکال logn نه اینکه تعداد عملیات کمتر باشه
حالا درسته تعداد عملیات heapify از logn کمتره ولی مرتبه زمانیش همون logn و کمتر نیست

[fsi2013]

سوال ۵۲ مگه منفی بی نهایت رو توی مین نذاشته؟؟؟؟!!!!
پس چطوری شرط until درست میشه؟

[iman30v]

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

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

[Farid_Feyzi]

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

اون مثبت بی نهایته. در واقع اشتباه تایپی هست ولی باید خیلی راحت حدس میزدین اینو.

---

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

اگه درخت بازگشت بکشید جواب همون nk میاد. بعید میدونم گزینه ۴ درست باشه.

[fatima1537]

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

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

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

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

[arta.66]

نظرای آقا فرید در مورد سوالای ساختمان درست هستش به جز سوال ۵۲ که بهش شک دارم بقیه درست هستن!! فقط نمی دونم چرا یه حس پلیسی بهم میگه آقا فرید یه ربطی به این سوالا داره!!!! بابا یکم آسونتر طرح میکردی مگه چی می شد؟؟؟

[Farid_Feyzi]

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

آخه منفی بی نهایت باشه که اصلا خط ۴ اجرا نمیشه! کدوم عدد داخل آرایه از منفی بینهایت کوچیک تر هست که با مین جایگزین بشه؟!

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

در مورد رابطه بازگشتی، همونو میگین که حداکثر عمق درخت بازگشت رو خواسته؟(۹۰ مهندسی کامپیوتر؟) خوب اونجا ماکزیموم عمق درخت رو خواسته ولی اینجا هزینه رابطه بازگشتی رو! اینجا باید مجموع سطوح درخت بازگشت رو بدست بیارید.

---

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

نه آرتا من من فقط علاقه خاصی به ساختمان و الگوریتم دارم، واسه همین گفتم سوالایی که تقریبا مطمئنم رو نظرمو در موردشون بگم شاید مفید واقع بشه!

[MajidManesht2012]

(۰۵ اسفند ۱۳۹۱ ۱۰:۲۴ ب.ظ)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 ماکزیمم مرتبه ایه که میتونه داشته با شه و دیگه مهم نیست که بیایم ارتفاع دقیق و محدود در نظر بگیریم.
بازم .....شاید حق با شما باشه.

[Farid_Feyzi]

نقل قول: من حداکثر عمق درخت بی نهایت در نظر میگیرم، قبول دار ی که بینهایت از 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 ماکزیمم مرتبه ایه که میتونه داشته با شه و دیگه مهم نیست که بیایم ارتفاع دقیق و محدود در نظر بگیریم.

کاملا درسته. شک نکنید!