در مورد شوال ۷ و ۱۳ و ۱۴ میشه نظر بدین؟
(۱۸ اسفند ۱۳۹۲ ۰۱:۱۶ ق.ظ)fallah_o68 نوشته شده توسط:(17 اسفند ۱۳۹۲ ۱۱:۴۷ ب.ظ)mrmasoud نوشته شده توسط: به صورت سوال دقت کنید:
عنصر با اندیس ۱۰، نه عدد ۱۰!
اگر Heap رو با ارایه پیاده سازی کنیم طبق صورت مساله، عنصر با index 10، لزوما عدد ۱۰ نیست! اصلا برامون هم مهم نیست چه عددی هست!
وظیفه ما اینه
عنصر با اندیس ۱۰۰ (که هر چی میخواد باشه! باشه!) رو میذاریم جای عنصر با اندیس ۱۰/ (از این به بعد بهش میگم X)
عنصر ۲۰ و ۲۱ (بچه هاش) رو با هم مقایسه می کنیم، یکی از این عناصر بزرگتر از دیگری هستش، حالا عنصر کوچکتر رو با X جابه جا میکنیم.---> تا اینجا یک مقایسه
حالا بسته به اینکه با اندیس ۲۰ یا ۲۱ جابه جا شده، یا عناصر (۴۰ و ۴۱) یا (۴۲ و ۴۳) رو با هم مقایسه میکنیم!
مثل روش بالا با یه مقایسه این عنصر میره سر جاش! --> تا اینجا دو مقایسه
و در مرحله سوم هم یکی از جفت های زیر رو باید مقایسه کنیم (۸۰ و ۸۱) یا (۸۲ و ۸۳) یا (۸۳ و ۸۴) یا (۸۴ و ۸۵).
---> سه مقایسه.
تمت.
(البته خدا رو چه دیدید، شاید سنجش گزینه ۱! رو اعلام کنه)
سلام و تشکر بابت استدلال و توضیحتان
بله بنده قبول دارم که اشتباه کردم و عنصر با اندیس ۱۰ را باید در نظر گرفت. اما میخام بگم که من در روز کنکور میخاستم این سوال را پاسخ ندهم چون به نظرم تعداد مقایسه ها باید زوج باشد و هیچکدام از گزینه ها زوج نیست. مثلا در جمله زیر مربوط به استدلال جنابعالی:
عنصر ۲۰ و ۲۱ (بچه هاش) رو با هم مقایسه می کنیم، یکی از این عناصر بزرگتر از دیگری هستش، حالا عنصر کوچکتر رو با X جابه جا میکنیم.---> تا اینجا یک مقایسه
وقتی عنصر ۲۰ و ۲۱ باهم مقایسه میشوند، یکی از عناصر کوچکتر است. شما طبق روال min-heapify حق ندارید عنصر کوچکتر را با عنصر جایگزین شده در اندیس ۱۰ (X) بدون انجام مقایسه تعویض کنید. از کجا میدانید که این عنصر قطعا کوچکتر بوده است. بنابراین نیاز به مقایسه بین عنصر کوچکتر با عنصر جایگزین شده در اندیس ۱۰ (X) هم باید انجام شود ---> بنابراین تا اینجا ۲ مقایسه (مطابق متد max-heapify کتاب clrs هربار ۲ مقایسه بین عناصر انجام میشود لطفا به شبه کد آن رجوع کنید و اگر حرف مرا قبول ندارید توجیه کنید)
در کل ۳ بار عملیات انجام شده و هربار ۲ مقایسه لازم است یعنی در کل ۶ مقایسه لازم است که در هیچ گزینه ای وجود ندارد!!!
شما یا سایر دوستان جواب یا مثال نقض یا اثباتی برای سوالات ۱۴، ۱۵ و ۱۸ سراغ دارید چون هنوز جواب قطعی و محکمی برای این سوالات را کسی نگفته
سلام خدمت تمامی دوستان
در مورد سوال ۱۴ در بهترین حالت و استفاده از هیپ فیبوناچی زمان الگوریتم دایکسترا برابر e+vlogvاست حال اگر بخوایهم برای تمام راس ها حساب کنیم برابر ev+v 2 logv حال در صورت سوال گفته که گراف همبند است لذا گراف می تواند یک گراف کامل باشد و در وصورتی که گراف کامل باشد داریم E=v 2 لذا زمان الگوریتم دایکسترا برابر v3+v 2 logv می شود که بیشتر از زمان v3 برای الگوریتم فلوید هست پس گزینه درست ۲ می باشد
(۱۸ اسفند ۱۳۹۲ ۰۷:۰۳ ب.ظ)kasadegh نوشته شده توسط: سلام خدمت تمامی دوستان
در مورد سوال ۱۴ در بهترین حالت و استفاده از هیپ فیبوناچی زمان الگوریتم دایکسترا برابر e+vlogvاست حال اگر بخوایهم برای تمام راس ها حساب کنیم برابر ev+v 2 logv حال در صورت سوال گفته که گراف همبند است لذا گراف می تواند یک گراف کامل باشد و در وصورتی که گراف کامل باشد داریم E=v 2 لذا زمان الگوریتم دایکسترا برابر v3+v 2 logv می شود که بیشتر از زمان v3 برای الگوریتم فلوید هست پس گزینه درست ۲ می باشد
سلام
سوال ۱۴ منم گزینه ۲ زدم. منتها تو صورت سوال گفته گراف مسطح. تا اونجا که من اطلاع دارم حداکثر تعداد یالهای گراف مسطح ۳v-6 هست. بنابراین هزینه الگوریتم دایکسترا v2 logv میشه که کمتره. با این حال اگه کسی اطلاع داره که حداکثر تعداد یالهای گراف مسطح چقدر است، لطفا خبر دهد؟
سوال ۱۵ هم که ظاهرا گزینه ۴ صحیحه. کسی مثالی برای رد ۳ گزینه دیگر دارد؟
سوال ۱۸ ظاهرا هیچ موردی غلط نیست (گزینه اول جواب است) و مثال نقض تا الان پیدا نکردم. اگر کسی از دوستان مثال نقضی برای هریک از موارد دارد لطفا بگوید
در مورد سوال ۵ که در چند نظر قبلی بنده توجیه دقیق کردم که جواب ۶ میشود و در هیچکدام از گزینه ها وجود ندارد، لطفا با استدلال پاسخ بنده را تایید یا رد کنید؟
(۱۸ اسفند ۱۳۹۲ ۱۰:۰۰ ب.ظ)fallah_o68 نوشته شده توسط: [quote='kasadegh' pid='261198' dateline='1394375609']
سلام خدمت تمامی دوستان
در مورد سوال ۱۴ در بهترین حالت و استفاده از هیپ فیبوناچی زمان الگوریتم دایکسترا برابر e+vlogvاست حال اگر بخوایهم برای تمام راس ها حساب کنیم برابر ev+v 2 logv حال در صورت سوال گفته که گراف همبند است لذا گراف می تواند یک گراف کامل باشد و در وصورتی که گراف کامل باشد داریم E=v 2 لذا زمان الگوریتم دایکسترا برابر v3+v 2 logv می شود که بیشتر از زمان v3 برای الگوریتم فلوید هست پس گزینه درست ۲ می باشد
سلام
سوال ۱۴ منم گزینه ۲ زدم. منتها تو صورت سوال گفته گراف مسطح. تا اونجا که من اطلاع دارم حداکثر تعداد یالهای گراف مسطح ۳v-6 هست. بنابراین هزینه الگوریتم دایکسترا v2 logv میشه که کمتره. با این حال اگه کسی اطلاع داره که حداکثر تعداد یالهای گراف مسطح چقدر است، لطفا خبر دهد؟
در مورد گراف مسطح حق با شماست، دو ستانی که میگن میتونه کامل باشه، آیا گراف کامل میتونه مسطح باشه؟
شما در مورد سوال ۷ نظری ندارین، بنطر من گزینه هیچکدارم صحیح است، چون ما الگوریتمی مبتنی بر مقایسه نداریم که کمتر از nlogn باشه.اگه لطفن نظرتونو بگین
سوال ۱۴ به نظر من گزینه ۳ هست
دوستان دکترا ، میشه لطف کنید در مورد سوالات ساختمان داده و طراحی الگوریتم کارشناسی ارشد ۹۳ ایتی نظر بدید با توجه به کلید اعلام شده سنجش خیلی لطف میکنید
دوستان دکترا میشه ی لطف کنید پاسخ تشریحی ساختمان داده و طراحی الگوریتم کارشناسی ارشد کنکور ایتی ۹۳ را برای بنده بنویسید ممنونتون میشم و لطف کنید کلید سنجش رو هم بررسی کنید
(۱۹ اسفند ۱۳۹۲ ۰۳:۳۵ ب.ظ)hamidsho نوشته شده توسط: دوستان دکترا ، میشه لطف کنید در مورد سوالات ساختمان داده و طراحی الگوریتم کارشناسی ارشد ۹۳ ایتی نظر بدید با توجه به کلید اعلام شده سنجش خیلی لطف میکنید
دوستان دکترا میشه ی لطف کنید پاسخ تشریحی ساختمان داده و طراحی الگوریتم کارشناسی ارشد کنکور ایتی ۹۳ را برای بنده بنویسید ممنونتون میشم و لطف کنید کلید سنجش رو هم بررسی کنید
دوست من سنجش کجا کلید داده ؟ لینکش رو به ما هم بده . "کلید اولیه سوالات درروز پنجشنبه مورخ ۲۲/۱۲/۹۲"
دوست من منظورم سوالای ارشد بود