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

کسی تعداد دقیق سوالات هر درسو میدونه؟پایگاه و سیستم چند تا یودن؟

(16 اسفند 1393 01:21 ق.ظ)cavalier نوشته شده توسط: [ -> ]فکر کنم شما تعریف همبند قویو رو فراموش کردین. برای اینکه ببینی یه گراف چند جز همبند قوی داره باید نعداد دورها رو بشمرین.
یعنی با انتخاب زیرمجموعه ای از راسها بتونیم از هر راس به راس دیگه بریم یعنی مسیر وجود داسته باشه
برای سوال یک هیچ دوری نداریم پس تعداد اجزای همبند میشه صفر
یعنی هیچ زیرمجموعه ای از راسها رو نمیشه انتخاب کرد که بشه از هر راس به راس دیگه بریم اما با اضافه کردن اون یال قرمز میبینین که تعداد دورها میشه سه تا پس سه جز همبند داریم. بنابراین با اضافه شدن یال تعداد اجزا بیشتر شد
دومیم که کلا نشون میده تعداد اجزای همبند میتونه با اضافه شدن یال تغییری نکنه در اینجا قبل و بعد از اضافه کردن یال تعداد اجزا صفر هست ..

---

تعریف اجزای همبند قوی
اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار از u به v یا از v به u، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار هم از u به v و هم از v به u داشته باشیم. مؤلفه‌های قوی، زیرگراف‌های قویاً همبند ماکسیمال هستند.

---

شما به ماکسیمال بودن تعریف توجه نکردین.
یک گراف با n راس و بدون یال، n جزء همبند قوی داره. با نفی مقدم(زیرگراف تک راسی دارای دو راس نیست که به هم وصل باشند یا نباشند!).
یک راه دیگه بررسی الگوریتم پیدا کردن مولفه همبند قوی روی گراف بالا هست: یک بار DFS میزنیم از یک راس دلخواه که فقط خود راس میشه. حالا روی ترانهاده گراف DFS میزنیم(بر اساس ترتیب خروج در DFS قبلی) که اونم میشه همون راس. زیر گرافهای باقی مونده میشه مجموعه مولفه های همبند قوی!

گراف کامل یک جزء همبند قوی داره که اونم خودشه، تعداد دورها برای n های بزرگتر از ۳ مطمئنا بیش از ۱ هست، پس لزوما تعداد دورها مشخص کننده اجزا همبند قوی نیست.

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

(15 اسفند 1393 07:02 ب.ظ)morelo نوشته شده توسط: [ -> ]شعاع هم r بزرگتر مساوی d/2
قد هم : n/2

قد که معادل مسئله استخدام(فصل تحلیل احتمالی کتاب CLRS) هست که میشه ln n

برای یک گراف با دو راس و یک یال، قطر و شعاع برابر میشه. پس گزینه هایی که نصف داشتن رد میشن!

سوال هزینه سرشکن هیپ تمرین کتاب CLRS هستش و گزینه درست میشه درج logn وحذف میشه 1
اون سوال هم که گفته یکی از مرتبه n یکی هم از مرتبه o(n) منظورشه از این دومی اینه که در حالت میانگین n باشه . مسئله انتخاب دو راه حل داره یکی با استفاده از پارتیشن بندی کویک سورت هست که از مرتبه میانگین n هست ولی یک الگوریتم دومی هست که در بدترین حالت در مرتبه n جواب میده و به نظرم اون دو گزینه درست بود.

نه اینی که میگین درست نیست خب اون طوری که میگی r d برابر یک میشه خب اون گزینه r بزرگتر از d/2 هم درسته
1 بزرگتر از 0.5

(15 اسفند 1393 07:02 ب.ظ)morelo نوشته شده توسط: [ -> ]ک سوال هم بود که ۳n و یافتن x<y که n تا کوچکتر و .... اگه اشتباه نکنم امگای nlogn میشد چون باید مرتب میشد

نیاز به مرتب سازی نیست، عنصر با مرتبه آماری n و عنصر با مرتبه 2n رو با پیچیدگی O(n بدست میاریم

---

(16 اسفند 1393 03:40 ب.ظ)cavalier نوشته شده توسط: [ -> ]نه اینی که میگین درست نیست خب اون طوری که میگی r d برابر یک میشه خب اون گزینه r بزرگتر از d/2 هم درسته
۱ بزرگتر از ۰/۵

درست میگین، من فکر کردم r کوچکتر از d/2 هست.

کلا d بین r , 2r هست. نمیدونم شرایط سوال چی بوده چون این طوری دو گزینه درسته

(16 اسفند 1393 03:58 ب.ظ)cavalier نوشته شده توسط: [ -> ]کلا d بین r , 2r هست. نمیدونم شرایط سوال چی بوده چون این طوری دو گزینه درسته

میشه بیشتر توضیح بدین.
من صورت سوال کامل یادم نیست. اگر شما یادتون هست، لطف کنین بنویسین که بتونیم بهتر بررسیش کنیم.

منم یادم نیس. خخخ.

(15 اسفند 1393 11:06 ب.ظ)cavalier نوشته شده توسط: [ -> ]صورت مساله رو یه بار دیگه بخونین. گفته حداکثر اختلاف دو نه یک.
پس هر درخت با ارتفاع n با چسبوندن درخت با ارتفاع n-1 گره و درخت با ارتفاع n-3 و اضافه کردن ریشه به دست میاد.

این استدلال کاملا درسته(متاسفانه). من نمی دونم چجوری گزینه درست رو رد کردم. فکر کنم تا h(5) رو بررسی کردم فقط
و داریم که:

بله بهتر بود همه گزینه ها رو چک میکردین اون طوری میدیدین دو گزینه مثل همه برای h5.. منم اشتباه زدنام داره پیدا میشه.

اما خودمونیم دکتر قدسی هم چه سوالاتی طرح میکنه

با سلام
گویا قرار بود سازمان سنجش تا دوشنبه ای که گذشت پاسخنامه رو هم بگذاره ولی فک کنم فراموش کردن!
به هر حال با توجه به مطالبی که در کتاب دکتر قدسی مطالعه کرده بودم پاسخ های من به سوالات ساختمان داده و الگوریتم ها به شرح ذیل بوده:
سوال 1: -
سوال 2: 3
سوال 3: -
سوال 4: 2
س 5: 2
س 6: 3
س 7: 2
س 8: 1
س 9: -
س 10: 2
س 11: 4
س 12: 4
س 13: -
س 14: 3
س15: 3
س16: 2
س17: 4
س 18: 2
س 19: -
س 20: 3

دوستان لطفا نظرات خودشونو بگذارند به صورت فوق تا بتونیم جمع بندی کنیم.
یاحق

(22 اسفند 1393 12:13 ق.ظ)norimotlagh نوشته شده توسط: [ -> ]با سلام
گویا قرار بود سازمان سنجش تا دوشنبه ای که گذشت پاسخنامه رو هم بگذاره ولی فک کنم فراموش کردن!
به هر حال با توجه به مطالبی که در کتاب دکتر قدسی مطالعه کرده بودم پاسخ های من به سوالات ساختمان داده و الگوریتم ها به شرح ذیل بوده:
سوال ۱: -
سوال ۲: ۳
سوال ۳: -
سوال ۴: ۲
س ۵: ۲
س ۶: ۳
س ۷: ۲
س ۸: ۱
س ۹: -
س ۱۰: ۲
س ۱۱: ۴
س ۱۲: ۴
س ۱۳: -
س ۱۴: ۳
س۱۵: ۳
س۱۶: ۲
س۱۷: ۴
س ۱۸: ۲
س ۱۹: -
س ۲۰: ۳

دوستان لطفا نظرات خودشونو بگذارند به صورت فوق تا بتونیم جمع بندی کنیم.
یاحق

سوال 4 میشه توضیح بدی؟