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

[f_b]

سلام و کنکور ۱۳۹۴ به اتمام رسید تو این تاپیک سوالات تحلیل می کنیم.
اما انتقاد من از ساختمان داده ۹۴ این بود که سطح سوالات خیلی استانداردتر شده و بر اساس درک و دید DS باید سوالات پاسخ داد و این خیلی خوبه و اما نمیدونم چرا امسال تعداد سوالات از گراف بود فکر کنم دکتر قدسی امسال روی گراف مانور داده بود.
منتظر نقد و بررسی دوستان هستیم.

[aadmida]

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

[arta.66]

برش کمینه همون ترکیب n از ۲ میشد؟؟
اون سرشکن هیپ چی؟؟ من حسم میگفت حذف ۱ میشه ولی آخرش جفتشم log زدم
اون سوال قد میشد ln
ماتریس اونی که همه رو جمع کرده بود
رابطه بازگشتی همون n رادیکال n
رابطه بازگشتی درخت متوازن خاص میشد t(n)=Tn-1+Tn-2
هافمن میشد ۱۲
دوران میشد n-1 که ۶ تا گره بود میشد ۵ دوران
یه سوالم بود در مورد قطر اینا: اونم میشد شعاع بزرگتر مساوی ۱/۲ قطر
باقی سوالا اصلا یادم نیست
ولی من کلا ۱۸ تا ساختمان زدم
البته شکیا رم زدم:) سیستم عامل معلوم نبود کار کی بود:) من با خوندن جزوه پدرام تونستم ۱ تست بزنم:) ۳ تا تست دیگم با تحلیل خودم بود:)
پایگاهم مطمئنا کار دکتر روحانی نبود( ادبیات فارسی رو زیر سوال برده بود طراح) اونم فکر کنم ۵ تا زدم

[sharareh_moradi]

هافمن ۲۵ میشد!
اون سوال که گزینه ها هافمن-بلمن فورد-دایجسترا- شار بود، کدوم میشد؟

[arta.66]

هافمن اگه سری فیبوناچی بود حرفتون درست بود ولی این سری دقیقا میشد ۱۲
اون سوال ام که میگین فکر کنم سوال یک بود که من نزدم:) کلا ۲ تا نزدم یکیش اون بود یکیش اونی که گفته ان پی تمام هارو بگین

[Masoud05]

هیپ من زدم: درج ۱ ؛ خذف لگاریتم.

[arta.66]

من به هیپ اینجوری نگاه کردم
گفتم فرض کن مثلا n/2 درج کنی... بعد اون بیای یکی در میون حذف کنی که میشه هر کدوم n/4 با این تفسیر هر دو میشن log حتی اگه جای عنصرم بدونیم فرقی نمیکنه چون هیپ باید اصلاح بشه... حالا شاید کلی بشه سناریو داد من بدترینو میگم بعد درج یه کسری از n من میخوام هر با ریشه رو حذف کنم که اصلاح هیپ میخواد....بازم مطمئن نیستم..

---

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

فکر کنم من اشتباه کردم سوتی بد دادم:) اگه سری تکرار به ترتیب ۱و۲و۴و۸ و... بوده باشه همون ۲۵ میشه:)) سر جلسه من کجا بودم نمیدونم:) البته وقتی مراقب باد بالاسرت جواباتو ببره واسه یکی دیگه تمرکز بیشتر ازین نمیشه:)) کلا کشور باحالی داریم:)

[montazer]

سلام و خسته نیاشید. اینو من هم موافقم، در ۶۰۰ گفته چون فراونی بعدی جمع قبلی هاست. اون هزینه سرشکن حذف و جمع رو من زدم جمعlogn و حذف ۱! اول فکر کردم هردوش logn اما بعد طبق هزینه سرشکن اینو زدم...
برای رابطه بازگشتی nرادیکالn logn زدم، اینم فکر کنم تو ۶۰۰ بود

امیدوارم همه موفق باشیم

(۱۵ اسفند ۱۳۹۳ ۰۴:۲۴ ب.ظ)sharareh_moradi نوشته شده توسط:  هافمن ۲۵ میشد!
اون سوال که گزینه ها هافمن-بلمن فورد-دایجسترا- شار بود، کدوم میشد؟

[Masoud05]

ساخت هیپ با n عنصر از مرتبه n هست. پس بطور سرشکن هزینه درج ۱ میشه!
هافمن رو ۲۵ زدم
اون که گفته ۱ لینک جهتدار اضافه میکنیم (سوال ۳یا ۴) : زدم ۲ تا درسته چون ۱ لینک که اضافه میکنیم قطعا تعداد اجزار همبند زیاد نمیشه اما با ذکر مثالی میشه نشون داد که گراف میتونه اصلا تغییر نکنه و یا اینکه چندین زیر گراف همبند ( و نه حداکثر ۱) از گراف همیند کاهش پیدا کنه.
زمان اجرای اون الگوریتم ادغام هم مثل اذغامی معمولی بود
اون سوال که رابطه بازگشتی داده بودن هم میشد [tex]n\sqrt{n}\log n[/tex]
سوال ۱ بلد نبودم ولی زدم دایکسترا.

[arta.66]

(۱۵ اسفند ۱۳۹۳ ۰۵:۵۲ ب.ظ)Masoud05 نوشته شده توسط:  ساخت هیپ با n عنصر از مرتبه n هست. پس بطور سرشکن هزینه درج ۱ میشه!

اینی که شما میفرمایین واسه وقتیه که عناطر رو داریم و بصورت درجا هیپ میسازیم... در درج های متوالی nlgn هست... درج که مطمئنا lgn هست من روی حذف شک دارم که ۱ میشه یا log که احتما با این سوتی هایی که من دادم اینم میشه همون ۱
رابطه بازگشتی ام سوالش یادم نیست ولی اونجا فکر کنم حس کردم قسمت ناهمگن رشد بیشتری داره

[Masoud05]

(۱۵ اسفند ۱۳۹۳ ۰۶:۰۸ ب.ظ)arta.66 نوشته شده توسط:  

(15 اسفند ۱۳۹۳ ۰۵:۵۲ ب.ظ)Masoud05 نوشته شده توسط:  ساخت هیپ با n عنصر از مرتبه n هست. پس بطور سرشکن هزینه درج ۱ میشه!

اینی که شما میفرمایین واسه وقتیه که عناطر رو داریم و بصورت درجا هیپ میسازیم... در درج های متوالی nlgn هست... درج که مطمئنا lgn هست من روی حذف شک دارم که ۱ میشه یا log که احتما با این سوتی هایی که من دادم اینم میشه همون ۱
رابطه بازگشتی ام سوالش یادم نیست ولی اونجا فکر کنم حس کردم قسمت ناهمگن رشد بیشتری داره

ممکنه. رابطه بازگشتی مطمئنم. از تعمیم قضیه اصلی باید حل میکردید.

[sharareh_moradi]

اون سوال هزینه اجرایی که
n رادیکال n داشت
جواب اون n به توان log3 میشه
اشتباه زدم من

[morelo]

اونی که n رادیکال n داشت، n به توان log3 میشد چون log 3 درمبنای ۲ میشه ۱/۵۸ و از ۱/۵ که توان n رادیکال n هست بیشتره
درخت AVL هم تغییر داده بود تعریفش که میشد f (h) <= f(h-1) + f(h-2)
شعاع هم r بزرگتر مساوی d/2
یک سوال هم بود که ۳n و یافتن x<y که n تا کوچکتر و .... اگه اشتباه نکنم امگای nlogn میشد چون باید مرتب میشد
سوال اول هم شبکه شار
همبند قوی چند گزاره درست : مطمئن نیستم اما دوتا درست/ شاید تغییر نکند و حداکثر یکی زیاد میشود
یکی دیگه بود چند گزاره درست: صفر یعنی گزینه ۱
قد هم : n/2
دوران هم ۵تا

[Masoud05]

(۱۵ اسفند ۱۳۹۳ ۰۷:۰۲ ب.ظ)morelo نوشته شده توسط:  اونی که n رادیکال n داشت، n به توان log3 میشد چون log 3 درمبنای ۲ میشه ۱/۵۸ و از ۱/۵ که توان n رادیکال n هست بیشتره
درخت AVL هم تغییر داده بود تعریفش که میشد f (h) <= f(h-1) + f(h-2)
شعاع هم r بزرگتر مساوی d/2
یک سوال هم بود که ۳n و یافتن x<y که n تا کوچکتر و .... اگه اشتباه نکنم امگای nlogn میشد چون باید مرتب میشد
سوال اول هم شبکه شار
همبند قوی چند گزاره درست : مطمئن نیستم اما دوتا درست/ شاید تغییر نکند و حداکثر یکی زیاد میشود
یکی دیگه بود چند گزاره درست: صفر یعنی گزینه ۱
قد هم : n/2
دوران هم ۵تا

سوال رادیکاله توجه داشته باش اون لگاریتم تو توان عدد ۲ بود نه N!!
سوال ۳n و تقسیک دامنه به ۳ قسمت هم با الگوریتم پارتیشن قابل حل هست و در زمان n حل میشه . (سوال تکراری ارشد هست).
قد رو زدم n/2
همبند قوی هم به احتمال قوی ۲ تاش درست بود.

[morelo]

(۱۵ اسفند ۱۳۹۳ ۰۷:۳۸ ب.ظ)Masoud05 نوشته شده توسط:  

(15 اسفند ۱۳۹۳ ۰۷:۰۲ ب.ظ)morelo نوشته شده توسط:  اونی که n رادیکال n داشت، n به توان log3 میشد چون log 3 درمبنای ۲ میشه ۱/۵۸ و از ۱/۵ که توان n رادیکال n هست بیشتره
درخت AVL هم تغییر داده بود تعریفش که میشد f (h) <= f(h-1) + f(h-2)
شعاع هم r بزرگتر مساوی d/2
یک سوال هم بود که ۳n و یافتن x<y که n تا کوچکتر و .... اگه اشتباه نکنم امگای nlogn میشد چون باید مرتب میشد
سوال اول هم شبکه شار
همبند قوی چند گزاره درست : مطمئن نیستم اما دوتا درست/ شاید تغییر نکند و حداکثر یکی زیاد میشود
یکی دیگه بود چند گزاره درست: صفر یعنی گزینه ۱
قد هم : n/2
دوران هم ۵تا

سوال رادیکاله توجه داشته باش اون لگاریتم تو توان عدد ۲ بود نه N!!
سوال ۳n و تقسیک دامنه به ۳ قسمت هم با الگوریتم پارتیشن قابل حل هست و در زمان n حل میشه . (سوال تکراری ارشد هست).
قد رو زدم n/2
همبند قوی هم به احتمال قوی ۲ تاش درست بود.

۲ به توان لگاریتم ۳ در مبنای ۲ که میشه ۳/ T(n) = 3T(n/2)+n√n
که با قضیه اصلی حل میشه و n به توان log3 در مبنای ۲ میشه
اینم لینکش

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