زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۹:۱۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

حل سوالات طراحی الگوریتم ۹۰

ارسال:
  

hatami پرسیده:

حل سوالات طراحی الگوریتم ۹۰

کلاً هیچ نظری رو الگوریتم ندارم. فکر کنم هیچی نزدم . دو تا سوال را میخواستم بزنم که شک کردم و پاک شون کردم بر خلاف بقیه دوستان که میگن الگوریتم آسان بوده من میگم الگوریتم مشکوکه

۰
ارسال:
  

sepid پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

بچه‌ها اون کد رو چی زدین؟
اون که گفته بود در نهایت k چند رو برمیگردونه ؟
من زدم الگوریتم تموم نمیشه یعنی با مثال به این جواب رسیدم.
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

ف.ش پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

آره منم مثال زدم دیدم تموم نمیشه یعنی به حالت اول برگشت!

ارسال:
  

mehr.iman پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۳۰ بهمن ۱۳۸۹ ۱۱:۰۶ ب.ظ)afagh1389 نوشته شده توسط:  آره منم مثال زدم دیدم تموم نمیشه یعنی به حالت اول برگشت!
من با دو تا مثال دیدم اون ۳ تا نمیشه!
در نتیجه همینی که شما زدیو تو آخرین لحظه زدم.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

sanaz پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

دفترچه های کنکور کارشناسی ارشد کامپیوتر سال ۱۳۹۰

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

۰
ارسال:
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

در مورد اون کد اره گزینه ۴ میشد کد تموم نمیشد.
در مورد اون سوال کا امین عنصر در اجتماع دو لیست میشه lgn
در مورد کد هافمن هم بگم که با جستجوی خطی میشه n به توان دو.

۰
ارسال:
  

hatami پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

معیار دفترچه D است که در سایت لینکشو دوستان گذاشتن
نظرتون در مورد سوال ۳۱ چیه ؟ کدوم گزینه درست است ؟من خودم ۳ زدم

۰
ارسال:
  

www پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

رو سوال چی بود؟
سوال ۳۰ هم من بین دو گزینه شک کردم بین ۲و۳ نزدم.
راستی بچه‌ها سوال ۳۲ گزینه ۲ جواب میشه؟
به نظر من که جواب ۲ میشه من اینو زدم.

۰
ارسال:
  

hatami پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

۳۲ یا ۲ یا ۳ من روی عبارت آخر شک دارم . البته من نزدم

۰
ارسال: #۱۰
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

تو هر گرافی در نظر بگیری با هر کدوم الگوریتم کوتاهترین مسیر بری درست در میاد پس تنها یه عبارت درسته.

۰
ارسال: #۱۱
  

psps1368 پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

ملاک گزینه‌ها دفترچه ۵۰۱D است.

سوال ۳۱: گزینه ۳، [tex]f(i)=MAX\begin{Bmatrix} f(i-1), w_{i} f(i-2) \end{Bmatrix}[/tex]
در این سوال برای محاسبه f برای خانه i ام، توجه می کنیم که پوستر یا در خانه i‌ام نصب می شود یا خیر، اگر نصب نشود که مسلما بیشینه خانه‌ها تا خانه i - 1‌ام جواب خواهد بود. اگر پوستر روی خانه i‌ام نصب شود، اولا w آن به جواب اضافه خواهد شد و ثانیا چون یک پوستر روی دو تابلوی پشت سر هم نمی تواند نصب شود مجموع وزن i‌ام با بیشینه تا خانه i - 2‌ام جواب خواهد بود.

سوال ۳۲: گزینه ۱، (۲ گزاره درست است. با یه مقدار شانس!)
گزاره ۱ درست است. فرض کنیم یال e = uv در درخت باشد. همان رئوس u و v را در نطر می گیریم. اگر e کوتاهترین مسیر بین آن‌ها نباشد پس راسی مثل w وجود دارد که uw+wv < uv . توجه داریم که uvw یک دور تشکیل خواهند داد. حال با توجه به این که چنین دوری موجود است، اگر بخواهیم MST را بسازیم، یال uv نمی تواند در درخت باشد.(تناقض) چرا که یکی از روش های ساخت MST این است که در هر دور یال های با وزن ماکسیمم را حذف کنیم تا زمانی که گراف همبند باقی بماند. با این روش یال uv در MST نخواهد بود.
گزاره ۲ هم راه حلی به غیر از دایجسترا به ذهنم نرسید. (از BFS نمی توان استفاده کرد چون گراف وزن دار است، پس ممکن است وزن یال‌ها متفاوت باشد.) من این گزاره رو غلط فرض کردم.
گزاره ۳ درست است. اگر این دو یال در دو دور مجزا باشند، یا یکی یا هر دوی آن‌ها یال برشی باشند، مسلما هر دوی آن‌ها در MST خواهند بود. اگر هر دو در یک دور باشند، واضح است که دور با حداقل ۳ یال تشکیل می شود. در هر دوری که شامل هر دوی آن‌ها باشند، باید بقیه یال‌ها حذف شوند، چون بقیه مسلما وزن بیشتری نسبت به این دو دارند و حذف هر کدام از این دو موجب افزایش وزن کل MST خواهد شد.

سوال ۳۳: گزینه ۳، log n جواب است. برای پیدا کردن میانه (سوال CLRS) هزینه log n است. برای دیگر آماره‌ها با تغییراتی می توان به این زمان رسید.

سوال ۳۴: نزدم، ولی فکر کنم، ممکن است تمام نشود، جواب باشد.

سوال ۳۵: گزینه ۲، n^2 جواب است. در هر مرحله دو مینیمم را با تتای i (از ۱ تا n) پیدا می کنیم. آن‌ها را با عناصر انتهای آرایه تعویض کرده و در همان انتهای آرایه ادغام را انجام می دهیم. در هر مرحله طول آرایه به اندازه یک کم خواهد شد. هزینه اصلی پیدا کردن مینیمم هاست. اگر بخواهیم آرایه را ابتدا مرتب کنیم، ادغام و درج در آرایه در هر مرحله به همین هزینه منتهی خواهد شد.

۰
ارسال: #۱۲
  

hatami پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

سوال ۳۲ گزاره ۱ غلطه من سر کنکور این گزاره را رد کردم یک مثلث با دو وزن ۱ و یک وزن ۲ مثال بزن

ارسال: #۱۳
  

psps1368 پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۲ اسفند ۱۳۸۹ ۰۳:۳۹ ب.ظ)hatami84 نوشته شده توسط:  سوال ۳۲ گزاره ۱ غلطه من سر کنکور این گزاره را رد کردم یک مثلث با دو وزن ۱ و یک وزن ۲ مثال بزن

درسته، نمی دونم چرا فرض کردم که گراف وزن هاش متفاوته...Huh
ان شاا... که دومی و سوی درستند....Big Grin

ویرایش: میشه یه مقدار توضیح بدی، آخه گفته حتما دو راسی وجود خواهند داشت، یعنی تو مثال شما هیچ دو راسی وجود ندارند؟
البته اثبات من که کاملا غلطه....
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۴
  

khoofi66 پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

نظر من درباره سوال ۳۴:
من تا الان ۳ بار مثال زدم و هر سه بار به جواب رسیدم
با استفاده از این مثال‌ها میتونم دو گزینه ۲و۳ رو حذف کنم و تا الان بیشتر از logn زمان نبرده.
به نظر من جواب گزینه ۴ هست.
دوستان اگه مثال نقض دارن بگن که چک کنیم شاید من ذهنم همش یه مدل داره مثال میزنه

ارسال: #۱۵
  

ramezanpour.r پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۲ اسفند ۱۳۸۹ ۰۴:۰۳ ب.ظ)khoofi66 نوشته شده توسط:  نظر من درباره سوال ۳۴:
من تا الان ۳ بار مثال زدم و هر سه بار به جواب رسیدم
با استفاده از این مثال‌ها میتونم دو گزینه ۲و۳ رو حذف کنم و تا الان بیشتر از logn زمان نبرده.
به نظر من جواب گزینه ۴ هست.
دوستان اگه مثال نقض دارن بگن که چک کنیم شاید من ذهنم همش یه مدل داره مثال میزنه
منم سر جلسه مثال زدم و log n رو زدم
ولی مثال زیر رو حل کن
A[1]=3
A[2]=1
A[3]=2
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۶
  

hatami پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

منم دقیقاً سر امتحان همین آرایه را مثال زدم و در حلقه افتادم

۰
ارسال: #۱۷
  

hatami پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

منم خودم الان که چک کردم دیدم با این مثال جواب نمیده پس فعلاً در مورد درست و غلطی این سوال نظر نمیدم

۰
ارسال: #۱۸
  

موج پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

سوال ۳۲
بله دوستان به خاطر همون قیده یالی وجود دارد به نظر من هم ۳۲ گزاره اول و آخر درسته گزاره وسط رو شک دارم که امیدوارم غلط باشه
البته از طرز گفتنش هم غلطه چون گفته E و نه در V+E در حالی که به لحاظ عقلی اگه با E بشه با V+E که مرتبه بالاتره حتما میشه

سوال تابلو ۳۱ و سوال ۳۳ هم با حل pspsکاملا موافقم

سوال ۳۴ هم در دور خواهد افتاد آرایه ای که من مثال زدم پنج خونه ای بود و هر n مرحله بدون مرتب شدن به حالت اول بر میگشت که البته دوستمون هم بالا یه مثال آورده براش

۳۵ رو نزدم

ارسال: #۱۹
  

parvaz_hj پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۳ اسفند ۱۳۸۹ ۰۱:۰۰ ق.ظ)موج نوشته شده توسط:  سوال ۳۲
بله دوستان به خاطر همون قیده یالی وجود دارد به نظر من هم ۳۲ گزاره اول و آخر درسته گزاره وسط رو شک دارم که امیدوارم غلط باشه
البته از طرز گفتنش هم غلطه چون گفته E و نه در V+E در حالی که به لحاظ عقلی اگه با E بشه با V+E که مرتبه بالاتره حتما میشه

سوال تابلو ۳۱ و سوال ۳۳ هم با حل pspsکاملا موافقم

سوال ۳۴ هم در دور خواهد افتاد آرایه ای که من مثال زدم پنج خونه ای بود و هر n مرحله بدون مرتب شدن به حالت اول بر میگشت که البته دوستمون هم بالا یه مثال آورده براش

۳۵ رو نزدم


۳۲ گزاره وسط درست هم میشه!!!! شما فرض کنید از الگوریتم کراسکال بریم واسه این کار! همون طور که می دونید این الگوریم از o(v2) هست حالا فرض کنید گراف کامل باشه و o(e)=o(v2) پس می بینید که شدنیه! ما اگه از bfs واسه این کار بریم میشه از o(e+v)اما همون طور که گفتم با کروسکال و گراف کامل هم باشه میشه.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۲۰
  

MJRS پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

گزینه های احتمالی:
۳۱: ۳
۳۲: ۱
۳۳: ۲
۳۴: ۴
۳۵: ۲

۰
ارسال: #۲۱
  

ف.ش پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

آقای تنهایی میشه نظرتون رو در مورد سوال ۳۳ و ۳۴ بگین.
با تشکر

۰
ارسال: #۲۲
  

sepid پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

آره وسطی هم درسته.
چون گراف بیجهت هست در زمان v+e میشه مساله رو حل کرد.
حالا چون همبنده پس تعداد یالها از راسها همیشه بیشتره و در زمان eمیشه حلش کرد.
مشاهده‌ی وب‌سایت کاربر

۰
ارسال: #۲۳
  

admin پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

ولی به نظر من سوال ۳۲ همون گزینه ۱ درسته! Big Grin
استدلال هم دوستان آوردن به جای ما!

۰
ارسال: #۲۴
  

admin پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)

الگوریتمش خیلی پیچیده‌‍‏‏است و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!! Big Grin

راهنمایی: هر بار میانه دو لیست رو می‌‍‏‏گیریم و با هم مقایسه می‌‍‏‏کنیم اگه میانه یکی بزرگتر از دیگری بود میانه‌‍‏‏شو دوباره می‌‍‏‏گیریم! Smile بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان می‌‍‏‏بره. سوال فوق العاده زیبایی است این سوال.

ارسال: #۲۵
  

sepid پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۳ اسفند ۱۳۸۹ ۰۱:۰۷ ب.ظ)admin نوشته شده توسط:  سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)

الگوریتمش خیلی پیچیده‌‍‏‏است و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!! Big Grin

راهنمایی: هر بار میانه دو لیست رو می‌‍‏‏گیریم و با هم مقایسه می‌‍‏‏کنیم اگه میانه یکی بزرگتر از دیگری بود میانه‌‍‏‏شو دوباره می‌‍‏‏گیریم! Smile بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان می‌‍‏‏بره. سوال فوق العاده زیبایی است این سوال.
با الگوریتم موافقم منتها زمانش میشه logn نه به توان ۲ش.
در مورد سوال ۳۲ شما با گزاره دوم مشکلی دارین؟
توضیح من که بالا نوشتم مشکلی داره؟
دقت کنید که گراف بیجهت هست.
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

ارسال: #۲۶
  

mehdi_matrix پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۳ اسفند ۱۳۸۹ ۰۱:۰۷ ب.ظ)admin نوشته شده توسط:  سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)

الگوریتمش خیلی پیچیده‌‍‏‏است و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!! Big Grin

راهنمایی: هر بار میانه دو لیست رو می‌‍‏‏گیریم و با هم مقایسه می‌‍‏‏کنیم اگه میانه یکی بزرگتر از دیگری بود میانه‌‍‏‏شو دوباره می‌‍‏‏گیریم! Smile بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان می‌‍‏‏بره. سوال فوق العاده زیبایی است این سوال.
دکتر در حالت کل به نظرتون سوال ابهام نداره؟آرایه تک عنصری را در نظر بگیرید(این آرایه مرتبه دیگه)که با آرایه n-1 عنصری ترکیب میشه!حالا باید جای تک عنصر آرایه اول در مجموع n عنصر پیدا بشه که با رول partitioning در بدترین حالت از مرتبه n هستش،و پیدا کردن k امین عنصر از آرایه بدست اومده که مرتب هست از مرتبه ۱ هستش!پس الگوریتم در بدترین حالت از مرتبه n هست.که با توجه به اینکه
n زیر مجموعه n+logn هست،و تنها گزینه ای که می تونه جواب را پوشش بده همین گزینه هست!
اگر بدترین مرتبه حالت میانگین مد نظر باشه با استفاده از برنامه نویسیه تقسیم و غلبه می تونیم الگوریتمی از مرتبه log n بدست بیاریم.
باید دید منظور طراح چی بوده!
من خودم گزینه ۳ را زدم.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۲۷
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

سوال ۳۲ گزینه یک در کتاب طراحی الگوریتم ارشد سپاهان گفته غلطه. صفحه شو دقیق براتون میگم.
سوال ۳۳ به نظر من ابتدا اجتماع را در lgn پیدا میکنیم سپس در lgn ما k امین عنصر را مییابیم جمع اینا میشه lgn.
۳۴- کد تموم نمیشه
۳۵- n به توان دو میشه.

ارسال: #۲۸
  

موج پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۳ اسفند ۱۳۸۹ ۰۱:۲۴ ب.ظ)www نوشته شده توسط:  سوال ۳۲ گزینه یک در کتاب طراحی الگوریتم ارشد سپاهان گفته غلطه. صفحه شو دقیق براتون میگم.
سوال ۳۳ به نظر من ابتدا اجتماع را در lgn پیدا میکنیم سپس در lgn ما k امین عنصر را مییابیم جمع اینا میشه lgn.
۳۴- کد تموم نمیشه
۳۵- n به توان دو میشه.

عزیزم نا سلامتی خود جناب تنهایی مدیر تالار دکترای این رشته رو دارن
اگه قرار باشه به سپاهان استناد کرد به نظر من استناد به حرف دکتر بهتره
سوال ۳۲ بخش الف گفته که حتما دو راس وجود دارد که ... شما اگه به نظرت غلطه یه مثال نقض بیار که هیچ دو راسی با این شرایط نباشه ما هم با تمام وجود میپذیریم
درمورد سوال ۳۳ من هم lgn زدم از خدامه که حرف تو درست باشه
۳۴ نظرم همینه
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۲۹
  

parvaz_hj پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

ولی من هنوز با اقای تنهایی مخالفم!!!!

۰
ارسال: #۳۰
  

MJRS پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

در سوال ۳۲ گفته شده که گراف وزن دار هست و مطمئنا نه در و O( E )l و نه در O( E + V )l الگوریتمی برای آن وجود ندارد.( دایسترا O( E log V )l و O( v ^ 2 )l خواهد بود. )

در مورد سوال ۳۳ هم که جناب تنهایی اظهار نظر فرمودند. دقت کنید که اگر بخوایم اجتماع دو لیست رو حساب کنیم O( n )l زمان میبره. راه حل دیگه این سوال دو باینری سرچ تودرتو هست که زمان آن O( logn ^ 2 )l خواهد بود.

۰
ارسال: #۳۱
  

sepid پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

برای سوال ۳۲ لطفا این فایل رو ببینید.
از کتاب clrs هست.
فصل ۲۴ صفحه ۶۴۲/


فایل‌(های) پیوست شده

مشاهده‌ی وب‌سایت کاربر

۰
ارسال: #۳۲
  

admin پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

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

۰
ارسال: #۳۳
  

www پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

حل دو سوال طراحی الگوریتم

۳۱-چند تا از گزاره های زیر درست هستند؟
الف)اگر در یک گراف وزن دار بدون جهت یال e=(u,v) در درخت فراگیر کمینه باشد حتما دو راس وجود دارد که کوتاهترین مسیر بین آن دو از e می گذرد.
ب)مسیله‌ی یافتن همه‌ی کوتاهترین مسیرها از یک راس به بقیه‌ی راسها را در یک گراف وزندار بدون جهت و همبند با مجموعه‌ی یال هایe را می توان در O(e) و نه درO(e+v) بدست آوزد.
ج)در یک گراف وزن دار و ساده بدون جهت با وزن های نامساوی یال با سبک ترین وزن و یال دومین سبک ترین وزن هر دو در درخت فراگیر کمینه هستند.
جواب
گزینه الف نادرست است برای نشان دادن اشتباه بودن آن گراف زیر را مثال میزنم
چون شکل گراف نمیافتد یک گراف با چهار راس و پنج یال را با اطلاعات زیر در نظر بگیرید.[/code]

یال(a,b) وزن ۱ دارد.
یال(a,d) وزن۱- دارد.
بقیه یالها وزن ۲ دارند.
یالهای (a,b),(a,d),(c,d) دردرخت کمینه هستند. فرض میکنیم e=(c,d) باشد اما کوتاهترین مسیر بین هر دو راس از e نمیگذرد. کوتاهترین مسیر بین(a,b)=1و بین(a,d)=-1و بین(c,d)=l میباشد. با این اوصاف گزینه الف غلط است.لازم به ذکر است که برای کوتاهترین مسیر برابر (c,d)=(a,c)+(a,d) میباشد.
گزینه ب غلط است قسمت اخرباعث اشتباه بودنش هست چون با(e+v)هم انجام میشود در ضمن طولانی ترین مسیر هم با این زمان انجام پذیر است.
گزینه اخر درست است.
با این اوصاف تنها یک مورد درست است.
سوال۳۳-
دو آرایه مرتبa1,a2با مجموع تعدادn عنصرداده شده اند فرض کنید که عناصر مجزا هستند میخواهیم kامین عنصرa UNION b را به دست اوریم این کار را میتوان در کدام زمان زیر انجام داد؟

جواب:
با توجه مطلب گفته شده در فصل ۲۱ کورمن عملیات find,union هر کدام به زمان O(lgn) نیاز دارد. جواب این سوال میشهklgn.
راستی اگر کسی تو کشیدن شکل مشکلی داشت بگه براش ایمیل کنم.

ارسال: #۳۴
  

۸۷۸۵۵۶۱۱ پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۴ اسفند ۱۳۸۹ ۰۱:۳۲ ب.ظ)www نوشته شده توسط:  حل دو سوال طراحی الگوریتم

۳۱-چند تا از گزاره های زیر درست هستند؟
الف)اگر در یک گراف وزن دار بدون جهت یال e=(u,v) در درخت فراگیر کمینه باشد حتما دو راس وجود دارد که کوتاهترین مسیر بین آن دو از e می گذرد.
ب)مسیله‌ی یافتن همه‌ی کوتاهترین مسیرها از یک راس به بقیه‌ی راسها را در یک گراف وزندار بدون جهت و همبند با مجموعه‌ی یال هایe را می توان در O(e) و نه درO(e+v) بدست آوزد.
ج)در یک گراف وزن دار و ساده بدون جهت با وزن های نامساوی یال با سبک ترین وزن و یال دومین سبک ترین وزن هر دو در درخت فراگیر کمینه هستند.
جواب
گزینه الف نادرست است برای نشان دادن اشتباه بودن آن گراف زیر را مثال میزنم
چون شکل گراف نمیافتد یک گراف با چهار راس و پنج یال را با اطلاعات زیر در نظر بگیرید.[/code]

یال(a,b) وزن ۱ دارد.
یال(a,d) وزن۱- دارد.
بقیه یالها وزن ۲ دارند.
یالهای (a,b),(a,d),(c,d) دردرخت کمینه هستند. فرض میکنیم e=(c,d) باشد اما کوتاهترین مسیر بین هر دو راس از e نمیگذرد. کوتاهترین مسیر بین(a,b)=1و بین(a,d)=-1و بین(c,d)=l میباشد. با این اوصاف گزینه الف غلط است.لازم به ذکر است که برای کوتاهترین مسیر برابر (c,d)=(a,c)+(a,d) میباشد.
گزینه ب غلط است قسمت اخرباعث اشتباه بودنش هست چون با(e+v)هم انجام میشود در ضمن طولانی ترین مسیر هم با این زمان انجام پذیر است.
گزینه اخر درست است.
با این اوصاف تنها یک مورد درست است.
سوال۳۳-
دو آرایه مرتبa1,a2با مجموع تعدادn عنصرداده شده اند فرض کنید که عناصر مجزا هستند میخواهیم kامین عنصرa UNION b را به دست اوریم این کار را میتوان در کدام زمان زیر انجام داد؟

جواب:
با توجه مطلب گفته شده در فصل ۲۱ کورمن عملیات find,union هر کدام به زمان O(lgn) نیاز دارد. جواب این سوال میشهklgn.
راستی اگر کسی تو کشیدن شکل مشکلی داشت بگه براش ایمیل کنم.


تعریف یال کمینه: یالی با کمترین وزن در یک گراف را می گویند
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۳۵
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

یال کمینه را تعزیفشو بلدیم لطفایاد نده سوالو دقیق بخون اینم مثال نقضش.
متاسفانه هر چقدم بخوای دلیل منطقی بیایی برخی نمیخوان قبول کنن حتما برا اینکه خودش اشتبا حل کرده نمیتونه بپذیره تا ادم‌ها تعصب روی چیزای غلط را داشته باشن نمیتونن مطلب جدید یاد بگیرن.
امیدوارم کسی ناراحت نشه و امیدوارم که سوال را دقیق بخونید.
برای سوال ۳۱ اینم با شکل.


فایل‌(های) پیوست شده
حل سوالای مبهم.doc
اندازه فایل: ۲۹/۵ KB

ارسال: #۳۶
  

piloop پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۴ اسفند ۱۳۸۹ ۰۷:۳۱ ب.ظ)www نوشته شده توسط:  یال کمینه را تعزیفشو بلدیم لطفایاد نده سوالو دقیق بخون اینم مثال نقضش.
متاسفانه هر چقدم بخوای دلیل منطقی بیایی برخی نمیخوان قبول کنن حتما برا اینکه خودش اشتبا حل کرده نمیتونه بپذیره تا ادم‌ها تعصب روی چیزای غلط را داشته باشن نمیتونن مطلب جدید یاد بگیرن.
امیدوارم کسی ناراحت نشه و امیدوارم که سوال را دقیق بخونید.
برای سوال ۳۱ اینم با شکل.

سلام

مثال نقضتون برای این سوال درست به نظر نمیاد. چون کوتاه ترین مسیر بین a تا c از یال (c,d) عبور می کنه. من اثبات دقیق نکردم، ولی فکر می کنم که گزاره اول حتی برای گراف با یال های منفی هم درست باشه.

برای سوال ۳۳ اگر بخواهیم که اجتماع در زمان log انجام بشه و حتی کمتر امکان پذیر هست، ولی مساله این هست که در این حالت (یعنی اجتماع گیری با زمانی کمتر از n) با ساختمان داده پیچیده تری از یک آرایه سر کار داریم که غالبا هم یک درخت هست. حالا سوال اینه که آیا پیدا کردن k امین عنصر در این ساختمان داده با همون زمان logn که در آرایه انجام می شه امکان پذیر هست. من فکر می کنم که همون گزینه logn^2 درست باشه.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۳۷
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

تو گراف که یال c,d) در درخت کمینه هست اما در بین کوتاهترین مسیرها نیست. یکم دقت کن.

ارسال: #۳۸
  

MJRS پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۵ اسفند ۱۳۸۹ ۰۱:۱۴ ب.ظ)www نوشته شده توسط:  تو گراف که یال c,d) در درخت کمینه هست اما در بین کوتاهترین مسیرها نیست. یکم دقت کن.

پیشنهاد میکنم شما یکم بیشتر دقت کنی. مثال نقض این سوال برای یال c->d بود که برای این یال هم دو راس a و c وجود دارند که کوتاهترین مسیر بین این دو راس از این یال میگذره.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۳۹
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

دقت کن کلمه حتما باعث غلط شدن این گزینه شده است.

۰
ارسال: #۴۰
  

www پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

با توجه به گراف قبلی که ناقص بود این گراف را کامل کردم بیا اینم جواب الف که نشون میده این گزینه غلطه.


فایل‌(های) پیوست شده
حل سوالای مبهم.doc
اندازه فایل: ۲۹ KB

ارسال: #۴۱
  

piloop پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۵ اسفند ۱۳۸۹ ۰۷:۲۸ ب.ظ)www نوشته شده توسط:  با توجه به گراف قبلی که ناقص بود این گراف را کامل کردم بیا اینم جواب الف که نشون میده این گزینه غلطه.

اگر ما رو متهم نکنی که "چون فلانی خودش یک چیزی زده نمی خواد قبول کنه!!" DodgyTongue، من نیمچه اثباتی که کرده بودم با مثال شما تطبیق دادم که ببینم کجا اشتباه کردم. خلاصه بخوام بگم مساله اینه که در گراف های وزن دار اما بدون جهت، کوتاه ترین مسیر بین هر زوج راس در مولفه های شامل یال منفی، منهای بینهایت خواهد بود و از اون جایی که مساله یافتن درخت پوشای کمینه هست، یک مولفه داریم. نتیجه اخلاقی باز هم این می شه که در سوالات کنکور از اون جایی که بسیاری از فرض‌ها ناقص بیان می شه و گاها بیان نمی شه، مخصوصا در سوالاتی تئوری از این دست، فقط می شه منتظر موند تا ببنیم که آقای طراح موقع نوشتن این سوال داشته به چی فکر می کرده!!!Angel
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۴۲
  

حامد پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

منم نظرم با www یکسانه.
دقیقا جمله مورد نظر رو چند جا خوندم که گفته بود غلطه.یکجا رو که دقیقا یادم هست تمرینهای اخر فصل کتاب الگوریتم یوسفی بود که از کتاب مرجع کپی کرده بود.و فکر کنم جوابش رو کامل داده بود و مثال نغز هم اورده بود.

۰
ارسال: #۴۳
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

ای خدا باز که بهونه میایین حالا با عوض کردن وزن‌ها میشه یک میلیون مثال نقض اورد. مثلا اگه میگین اون یال در درخت کمینه نمیشه وزنش را یک کنین باز جواب من درسته.

ارسال: #۴۴
  

parvaz_hj پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۶ اسفند ۱۳۸۹ ۰۷:۲۳ ب.ظ)www نوشته شده توسط:  ای خدا باز که بهونه میایین حالا با عوض کردن وزن‌ها میشه یک میلیون مثال نقض اورد. مثلا اگه میگین اون یال در درخت کمینه نمیشه وزنش را یک کنین باز جواب من درسته.
دوست گرامی بهونه نیست!!! اگه منظورتون ۱ کردن وزن یال d,e هست که باز هم درست در میاد!! اما اگه منظورتون ۱ کردن وزن یالd,c هست بعد یگه d,e جزء درخت نمیشه و dc که ۱ است میشه و باز درست در میاد....یکم صبور باشBig GrinBlush
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۴۵
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

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

ارسال: #۴۶
  

parvaz_hj پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۷ اسفند ۱۳۸۹ ۰۲:۵۷ ب.ظ)www نوشته شده توسط:  در مورد حلقه منفی برین فصل ۲۴ و۲۵کورمنو بخون ببین اونجا گفته میشه پس اگر مرجع نخوندین بهتون حق میدم اما اینو مطمین باشین.
در ضمن حلقه منفی را انتخاب نکردیم و باز میگم طراح فقط با کلمه حتما بچه‌ها را خواسته فریب بزنه مثل اینکه خوب موفق شده بالاخره انشالله جواب من درست بشه.

من فرض اینی که حلقه منفی هم کار نداشته باشیم زدم!!!هنوز مثالهاتون مطمئن نیست!
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۴۷
  

www پاسخ داده:

حل سوالات طراحی الگوریتم ۹۰

این سوالو مطمینم بالاخره بازم میگم کلمه حتما را دقت کن .

ارسال: #۴۸
  

parvaz_hj پاسخ داده:

RE: حل سوالات طراحی الگوریتم ۹۰

(۰۷ اسفند ۱۳۸۹ ۰۳:۵۸ ب.ظ)www نوشته شده توسط:  این سوالو مطمینم بالاخره بازم میگم کلمه حتما را دقت کن .

شما هم به کلمه وجود دارد دقت کن...وجود دارددد...نه همه راس‌ها لزوما....البته اینو توی مثال هات نشون داده بودی اما مثال هات مثال نقض نبود.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  [دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی هاتف ۳۳ ۴۰,۷۹۲ ۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ
آخرین ارسال: solmaz58
  طراحی ui/ux kimiya1234 ۲ ۲,۰۰۹ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۲ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  طراحی یک سیستم عامل (از صفر) sina4everafter ۱۲ ۱۵,۶۲۵ ۰۶ بهمن ۱۳۹۹ ۱۲:۵۳ ب.ظ
آخرین ارسال: nahalmomen2007@yahoo.com
  طراحی سایت ریسپانسیو wikidemy1 ۰ ۱,۶۰۲ ۱۳ دى ۱۳۹۹ ۰۴:۰۱ ب.ظ
آخرین ارسال: wikidemy1
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۱,۴۸۲ ۳۰ آذر ۱۳۹۹ ۰۸:۲۴ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۱,۳۳۳ ۳۰ آذر ۱۳۹۹ ۰۸:۲۰ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۷,۲۲۱ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۳,۱۹۷ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t
  تاثیر بودجه در انتخاب شرکت طراحی سایت wone ۱ ۲۰ ۲۳ آبان ۱۳۹۸ ۰۱:۱۴ ب.ظ
آخرین ارسال: xiaomi

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close