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

[msghasemi]

در باره سوال ۴۹ با تساوی اوزان هم میشه اظهار نظر کرد.
اگر همه‌ی اوزان به یک اندازه باشن باز هم خروجی آلگوریتم کروسکال روی اون گراف قطعا یکی خواهد بود.
چون مساله رو میشه مثل اعمال کروسکال روی لیست مرتبی در نظر گرفت که همه‌ی عناصر کلید آن یک واحد زیاد شده باشند.
طبیعتا ورودی فرقی نکرده.
پس III قطعا نا درست و II درسته.
اما در باره‌ی I نمی دونم چه نظری باید داد.چون فکر میکنم روی تعریف برش کمینه اتفاق نظر نباشه.
من درست فرضش کردم.
نظر دوستان مسلط‌تر چیه؟

---

۴ گزینه‌ی درسته.
E=False
P=False
KB غلط نمیشه.
البته من سر جلسه کل عبارات دیگه رو با Resolution بدست آوردم.

---

سوال ۶۰ ۴ گزینه‌ی درسته.
E=False
P=False
KB غلط نمیشه.
البته من سر جلسه کل عبارات دیگه رو با Resolution بدست آوردم.

---

در سوال ۵۷
اگر H©=5 or 6 باشه Overestimate کردیم پس گزینه‌ی ۲ و۳و ۴ حذف می شن.
اما در باره monotonic بودن طبق تعریف نلسون داریم:
H(n) is monotonic if for each node like n and every successor like n' which reaches with action a:
h(n)<=c(n,a,n') bashe
با توجه به تعریف فوق تنها در گزینه‌ی ۱ این شرط برقراره.
البته بنظر خودم یا تست خیلی بد گزینه بوده یا خیلی مشکوکه.

---

سوال ۵۵ هم آزمون یکی از دانشگاه های خارجیه.
با بررسی حالات تکراری اول سطح ۲*(x+y)(x+y+1) گره رو بسط می ده.
اگر حالات تکراری رو بررسی نکنیم با هر نوع جوستجویی تقریبا نمایی بسط خواهیم داشت.
گزینه‌ی صحیح ۱ است.

---

سوال ۵۶
با سور عمومی عطف نمی آید.
پس ۲ و ۳ صحیح نیست.
گزینه‌ی ۴ هم از نظر مفهومی ایراد دارد.
گزینه‌ی صحیح ۱ است.

---

اصلاح تعریف Monotonic سوال ۵۷
شرط باید بصورت زیر اصلاح بشه:
h(n)<=c(n,a,n')+h(n') bashe

[msghasemi]

درباره سوال ۵۰ هم گزینه‌ی صحیح ۳ است.
به اثبات زیر توجه فرمایید:
این اثبات مربوط میشه به دانشگاه KAIST

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

توی این فایل اثبات کرده که باروش حریصانه میشه با nlogn مساله رو حل کرد.

[MJRS]

گزینه های احتمالی درست درس طراحی الگوریتم ها:

۴۸: ۳
۴۹: ۲
۵۰: ۳
۵۱: ۴
۵۲: ۴
۵۳: ۲

[msghasemi]

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

۴۸: ۳
۴۹: ۳
۵۰: ۳
۵۱: ۴
۵۲: ۴
۵۳: ۲

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

---

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

۴۸: ۳
۴۹: ۳
۵۰: ۳
۵۱: ۴
۵۲: ۴
۵۳: ۲

$(Pk)\leq \frac{(Pk) (Pk 1) ... (Pk m-1)}{m} & (Pk m)\leq \frac{(Pk m) ... (Pk 2m-1)}{m} & . . . (Pk (r-1)m)\leq \frac{(Pk (r-1)m) ... (Pk rm-1)}{m} Hala-tatareyne-namosavi-ro-jam-mikonim.Darim :(Pk) (Pk m) ... (Pk (r-1)m)\leq (Pk)\leq \frac{(Pk) (Pk 1) ... (Pn-1)}{m}\leq \frac{S-Pn}{m} Pn$

این مطلب مبین صحیح بودن گزینه‌ی ۱ است.

---

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

۴۸: ۳
۴۹: ۳
۵۰: ۳
۵۱: ۴
۵۲: ۴
۵۳: ۲

$(Pk)\leq \frac{(Pk) (Pk 1) ... (Pk m-1)}{m} Va (Pk m)\leq \frac{(Pk m) ... (Pk 2m-1)}{m} Va . . .Va (Pk (r-1)m)\leq \frac{(Pk (r-1)m) ... (Pk rm-1)}{m} Hala-tatareyne-namosavi-ro-jam-mikonim.Darim :(Pk) (Pk m) ... (Pk (r-1)m)\leq (Pk)\leq \frac{(Pk) (Pk 1) ... (Pn-1)}{m}\leq \frac{S-Pn}{m} Pn$

این مطلب مبین صحیح بودن گزینه‌ی ۱ است.

[MJRS]

من هم بر اساس اینکه قبلا این سوال رو دیده بودم گزینه ۳ رو بدون اینکه فکر کنم زدم ولی الان که شما گفتی رفتم دوباره چک کردم و در نهایت تعجب دیدم که جواب نه گزینه ۱ و نه گزینه ۳ هست. جواب این سوال در کلید نهایی سال ۱۳۸۴ گزینه ۲ بوده یعنی S/ m - Pn !!!!

این لینک کلید این سال بوده:

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


سوال ۳۸ اون سال !!

MinCut در یک گراف یعنی یک سری از یال‌ها رو از بین ببری به طوری که گراف حاصله هم بند نباشه و مجموع یال هایی که cut شده مینیمم باشه.
وقتی اندازه همه یال‌ها یک واحد زیاد شه به وضوح هزینه Cut هم به اندازه تعداد یال هایی که cut میشه زیاد میشه و این دو مقدار برابر نیستند.

جواب سوال ۴۹ گزینه ۲ میشه که ویرایشش کردم. اولی و سومی غلط هستند به نظرم.

[yas67]

سوال ۵۹ گزینه اول اون که با ۸ شروع میشه چرا اشتباهه؟

[ف.ش]

دکتر تنهایی اگر ممکنه نظرتون رو در مورد سوالات ۴۸ و ۵۰ بگین.
آخه سوال ۵۰ گفته راه حل بهینه درسته که روش حریصانه این سوال رو میشه توی nlogn اجرا کرد ولی الزاما که بهینه نیست!

---

سوال ۵۱ رو هم من حساب کردم n میشه!

[msghasemi]

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

---

(۰۳ اسفند ۱۳۸۹ ۰۳:۱۷ ق.ظ)MJRS نوشته شده توسط:  من هم بر اساس اینکه قبلا این سوال رو دیده بودم گزینه ۳ رو بدون اینکه فکر کنم زدم ولی الان که شما گفتی رفتم دوباره چک کردم و در نهایت تعجب دیدم که جواب نه گزینه ۱ و نه گزینه ۳ هست. جواب این سوال در کلید نهایی سال ۱۳۸۴ گزینه ۲ بوده یعنی S/ m - Pn !!!!

این لینک کلید این سال بوده:

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


سوال ۳۸ اون سال !!

MinCut در یک گراف یعنی یک سری از یال‌ها رو از بین ببری به طوری که گراف حاصله هم بند نباشه و مجموع یال هایی که cut شده مینیمم باشه.
وقتی اندازه همه یال‌ها یک واحد زیاد شه به وضوح هزینه Cut هم به اندازه تعداد یال هایی که cut میشه زیاد میشه و این دو مقدار برابر نیستند.

جواب سوال ۴۹ گزینه ۲ میشه که ویرایشش کردم. اولی و سومی غلط هستند به نظرم.

من جواب سوال ۴۸ رو با دو مرجع چک کردم و هردو گزینه‌ی ۱ رو تایید کردن.اگر هم شما عدد بذارین گزینه‌ی ۱ رو نزدیکتر میبینین.من هم از کلید تعجب کردم.این مساله اثبات ریاضی داره.

[msghasemi]

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

[msghasemi]

ممکنه یکی از دوستان در مورد سول ۴۹ قسمت I و ۵۴ کمی توضیح بده.

[nasr]

سوال ۴۸ الگوریتم چراs-p/m+p نمیشه؟

[MJRS]

(۰۸ اسفند ۱۳۸۹ ۰۱:۵۰ ب.ظ)nasr نوشته شده توسط:  سوال ۴۸ الگوریتم چراs-p/m+p نمیشه؟

کلید اولیه هم همین گزینه رو اعلام کرده.

[inteligentium]

سوال ۵۹ هوش رو دوباره با دقت بررسی کنین
گزینه ای که با ۸ شروع میشه هم درسته:
هرس گره پایانی ۳ که مشخصه نیازی به توضیح نداره
حالا وقتی ۹ بررسی میشه چون گره ریشه مقدارفعلی ۸ رو داره و چون مقدار گره مینیمم حداکثر ۹ هست بقیه هرس می شوند.چرا؟چون اگر مقادیر سایر گره‌ها کمتر از ۹ هم باشد حداکثر ۸ است که همین مقدار ۸ را در گره ماکزیمم ریشه داریم ودیگر نیازی به بررسی گره های ۱۰،۰ ،۱ و ۴ نداریم پس حذف می شوند.گزینه ای که با ۹ شروع می شود هم صحیح است.لازم است به این سوال هم اعتراض شود.

[Mansoureh]

(۱۱ اسفند ۱۳۸۹ ۰۳:۰۶ ق.ظ)inteligentium نوشته شده توسط:  چرا؟چون اگر مقادیر سایر گره‌ها کمتر از ۹ هم باشد حداکثر ۸ است که همین مقدار ۸ را در گره ماکزیمم ریشه داریم ودیگر نیازی به بررسی گره های ۱۰،۰ ،۱ و ۴ نداریم پس حذف می شوند.

اعتراضت وارد نیست...
این جمله ات غلطه!
سئوال گفته اعداد بین بازه بسته‌ی ۰ تا ۱۰ هستند و نگفته که اعداد صحیح هستند! پس میتونه اعداد بین ۸ تا ۹ هم باشه، پس اگر به جای گره‌ی ۱۰ ما داشته باشیم یه عددی مثلا ۸/۵ (میشه چون تو که از اعداد در برگ خبر نداری!) اون موقع است که ۸/۵ میاد بالا و بررسی میشه، پس حذف نمیشه!!!!
من هم سر امتحان نزدیک بود همین اشتباه رو بکنم!!!

فقط و فقط در حالتی که با گره‌ی ۹ شروع بشه ما اون هرس‌ها رو خواهیم داشت...

[۱۲۳javad]

سوال ۵۹ هوش رو دوباره با دقت بررسی کنی
فکر کنم
هم گزینه ای که با ۱۰ شروع میشه و هم گزینه ای که با ۹ شروع میشه جواب باشه