تالار گفتمان مانشت

سلام.

تست ۴۹ از کنکور مهندسی کامپیوتر ۹۲.






پاسخ گزینه ۲ است.

به نظر من گزینه ۳ صحیح است.
به نظر من الف را نمی توان ایجاد کرد. اگر می توان ایجاد نمود لطفا توضیح دهید چگونه است.
به نظر من ب را می توان ایجاد نمود. کافی است یک min heap داشته باشیم. ابتدا آرایه را در مرتبه [tex]O(n)[/tex] به مین هیپ تبدیل می کنیم و درج و حذف، با [tex]O(logn)[/tex] قابل انجام می باشد.



سپاس...

(21 آذر 1392 02:40 ق.ظ)mohammad-a نوشته شده توسط: [ -> ]برای گزینه‌ی الف میشه از یک AVL یا شبیه آن مثل درخت‌های قرمز-سیاه استفاده کرد که حذف و درج در آن از مرتبه‌ی لگاریتمی و برای یافتن هم میشه در آن یک جستجو انجام داد. چون ارتفاع AVL همیشه لگاریتمی است، در نتیجه موارد خواسته شده در الف را می‌توان انجام داد.

در مورد قسمت الف توضیح قانع کننده ای بود و حق با شماست اما در مورد قسمت ب مشکل وجود دارد و باز هم فکر می کنم قابل انجام نباشد چون یافتن یک عنصر مورد نظر نیست بلکه چندین عنصر مد نظر است. پس در زمان logn قابل انجام نخواند بود.




ممکنه در این مورد کمی توضیح دهید.



بسیار تشکر می کنم.

شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه

(21 آذر 1392 01:42 ب.ظ)izadan11 نوشته شده توسط: [ -> ]شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه

تشکر.
اگر امکان دارد کمی در مورد چگونگی انجام ساختمان الف توضیح دهید. اینکه چطور درج و حذف از مرتبه logn است و چگونه یک بازه از مقادیر را می توان در زمان logn پیدا کرد.

(21 آذر 1392 02:26 ب.ظ)Morris نوشته شده توسط: [ -> ]

(21 آذر 1392 01:42 ب.ظ)izadan11 نوشته شده توسط: [ -> ]شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه

تشکر.
اگر امکان دارد کمی در مورد چگونگی انجام ساختمان الف توضیح دهید. اینکه چطور درج و حذف از مرتبه logn است و چگونه یک بازه از مقادیر را می توان در زمان logn پیدا کرد.

هیپ فیبوناچی یه فصل از کتاب سی ال آر اسه اگه وقت نداری بخونیش بهتره حفظش کنی(ولی حفظ احتمال اشتباه رو بالا می بره)

(21 آذر 1392 02:32 ب.ظ)izadan11 نوشته شده توسط: [ -> ]هیپ فیبوناچی یه فصل از کتاب سی ال آر اسه اگه وقت نداری بخونیش بهتره حفظش کنی(ولی حفظ احتمال اشتباه رو بالا می بره)

در مورد قسمت الف پرسیدم، فکر می کنم منظورتان از "درخت باینری متوازن" همان AVL می باشد. ممکن است توضیح دهید چطور یافتن مقادیر بین دو مقدار مثلا a و b را در logn می توان اجرا کرد؟

واسه الف شما از dynamic order statistic باید استفاده کنید

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

و این طوره که شما rank a و rank b رو حساب میکنید، و جواب میشه تفاضل این دو.


واسه ب هم هیچ داده دساختاری وجود نداره، ولی Fibonacci heap میشه فکر کنم که جز سر فصل نیست.

(21 آذر 1392 07:33 ب.ظ)Riemann نوشته شده توسط: [ -> ]واسه الف شما از dynamic order statistic باید استفاده کنید

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

و این طوره که شما rank a و rank b رو حساب میکنید، و جواب میشه تفاضل این دو.


واسه ب هم هیچ داده دساختاری وجود نداره، ولی Fibonacci heap میشه فکر کنم که جز سر فصل نیست.

تشکر فراوان !
این دو مورد "dynamic order statistic" و "Fibonacci heap" جایی ازش صحبت نشده لااقل من ندیدم. از چه منبعی این مواردو بررسی کنم ؟



تشکر.

(21 آذر 1392 09:58 ب.ظ)Morris نوشته شده توسط: [ -> ]

(21 آذر 1392 07:33 ب.ظ)Riemann نوشته شده توسط: [ -> ]واسه الف شما از dynamic order statistic باید استفاده کنید

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

و این طوره که شما rank a و rank b رو حساب میکنید، و جواب میشه تفاضل این دو.


واسه ب هم هیچ داده دساختاری وجود نداره، ولی Fibonacci heap میشه فکر کنم که جز سر فصل نیست.

تشکر فراوان !
این دو مورد "dynamic order statistic" و "Fibonacci heap" جایی ازش صحبت نشده لااقل من ندیدم. از چه منبعی این مواردو بررسی کنم ؟



تشکر.

من dynamic order statistic رو توی کتاب قدسی خوندم، Fibonacci heap هم در حد این که مرتبه زمانیاش چی میشه. توی کتاب clrs هم همه ی اینا هست توی فصل augmenting data structures فصل 14 و فصل 19 هم که Fibonacci heap هست ولی نیاز نیست بخونیدش مقاله ویگی پدیا بهتره.

(21 آذر 1392 01:42 ب.ظ)izadan11 نوشته شده توسط: [ -> ]شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه

دوست عزیز مگه AVL همه چیزش BIG O نیست؟ پس چرا مورد اولی که با small O هست میگی قابل قبوله؟
ی چیز دیگه من تو ویکی پدیا نگاه کردم زمان حذف هیپ فیبونانچی رو زده big O که .... موضوع چیه؟!!!

(08 بهمن 1392 12:43 ب.ظ)zahra412 نوشته شده توسط: [ -> ]

(21 آذر 1392 01:42 ب.ظ)izadan11 نوشته شده توسط: [ -> ]شما سوال رو اشتباه فهمیدین اولا تنها حالتی که میشه فرض کرد گزینه ی ب را می توان تشکیل داد هیپ فیبوناچی هست که در هیپ فیبوناچی فقط زمان حذف با o کوچک داریم ولی مشکل اینجاست که حذف مینیمم میشه همون O بزرگ که این موجب نمی توان بودن میشه
گزینه ی الف هم با درخت باینری متوازن حل میشه

دوست عزیز مگه AVL همه چیزش BIG O نیست؟ پس چرا مورد اولی که با small O هست میگی قابل قبوله؟
ی چیز دیگه من تو ویکی پدیا نگاه کردم زمان حذف هیپ فیبونانچی رو زده big O که .... موضوع چیه؟!!!

من اینجور برداشت کردم که نظر طراح اینه که فقط اون که کنارش نوشته (اوی کوچیک) اوی کوچیک هست و بقیه اش رو اوی بزرگ در نظر گرفتم

---

(21 آذر 1392 07:18 ب.ظ)Morris نوشته شده توسط: [ -> ]

(21 آذر 1392 02:32 ب.ظ)izadan11 نوشته شده توسط: [ -> ]هیپ فیبوناچی یه فصل از کتاب سی ال آر اسه اگه وقت نداری بخونیش بهتره حفظش کنی(ولی حفظ احتمال اشتباه رو بالا می بره)

در مورد قسمت الف پرسیدم، فکر می کنم منظورتان از "درخت باینری متوازن" همان AVL می باشد. ممکن است توضیح دهید چطور یافتن مقادیر بین دو مقدار مثلا a و b را در logn می توان اجرا کرد؟

یه متغییر به عنوان تعداد فرزندان به پارامتر های نود اضافه کنیم

واسه دومی ساختمان داده نمیشه طراحی کرد، چون اگه بشه ما میتونیم n بار حذف رو صدا بزنیم و بتونیم باهاش یه آرایه رو توی زمان [tex]o(n \lg n)[/tex] مرتب کنیم که این تناقض داره با این [tex]\Omega(n \lg n)[/tex].

(08 بهمن 1392 01:28 ب.ظ)Riemann نوشته شده توسط: [ -> ]واسه دومی ساختمان داده نمیشه طراحی کرد، چون اگه بشه ما میتونیم n بار حذف رو صدا بزنیم و بتونیم باهاش یه آرایه رو توی زمان [tex]o(n \lg n)[/tex] مرتب کنیم که این تناقض داره با این [tex]\Omega(n \lg n)[/tex].

دمت گرم