(29 بهمن 1390 02:14 ق.ظ)sh4477 نوشته شده توسط: [ -> ]دوستان همه این سوال‌ها تکراری بودن، من چک کردم
سوال فلوید گزینه ۱
طولانی ترین مسیر bfs
مرتبه زمانی e log v یا v log e
میشه آدرس بدید؟
طبق این برگه شماره تست رو بیان کنید
[
attachment=2778]
در مورد اون سوال BFS و DFS من که خیلی مطمئن زدم BFS مخصوصا وقتی یال ها وزن ندارن و یعنی تعداد اعمال مهمه!
نمی دونم چطور می گید DFS میشه.
طبق صحبت های بچه های مانشت و دوستانم بعد از آزمون تا حالا این نتایج بدست آمده( نظر خودم نیست بلکه نظر بچه هاست )
سوالات با توجه عکس بالا هست:
۱۱۰‌: بعضیا میگفتن ۱ و بعضیا ۲
۱۱۱: بین ۱و ۳
۱۱۲: ۱ بنظرم همین درسته
۱۱۳: ۱ و ۲
۱۱۴: ۳ یا ۴ من فکر میکنم ۴ باشه اما مطمئن نیستم
۱۱۵: احتمال داره هر ۲ نادرست باشه اما راجع به این سوال بحث جدی نشده!
(29 بهمن 1390 11:41 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]طبق صحبت های بچه های مانشت و دوستانم بعد از آزمون تا حالا این نتایج بدست آمده( نظر خودم نیست بلکه نظر بچه هاست )
سوالات با توجه عکس بالا هست:
۱۱۰‌: بعضیا میگفتن ۱ و بعضیا ۲
۱۱۱: بین ۱و ۳
۱۱۲: ۱ بنظرم همین درسته
۱۱۳: ۱ و ۲
۱۱۴: ۳ یا ۴ من فکر میکنم ۴ باشه اما مطمئن نیستم
۱۱۵: احتمال داره هر ۲ نادرست باشه اما راجع به این سوال بحث جدی نشده!
110: بین 1 و 4 ولی من حساب کردم 4
111: 1
112: 1
113: -
114: 3 (DFS) شما تو ویکی پدیا هم بری نوشته اینو
115: 1مقدار بحث برانگیزه (:
110- 4 (من با محاسبه و رسم درخت به دست آوردم)
111- 3 (مطمئن نیستم)
112- بدون جواب
113 - 2 (چون یه آرایه کشیدم و با چند لیست حلقوی تست کردم دیدم مثل مرتب جستجوی دودویی است)
114- 3
115- بدون جواب
کسی جواب سوال 113 رو نمیدونه؟همون لیست حلقویه؟
من logN زدم.
(29 بهمن 1390 05:24 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]۱۱۰- ۴ (من با محاسبه و رسم درخت به دست آوردم)
۱۱۱- ۳ (مطمئن نیستم)
۱۱۲- بدون جواب
۱۱۳ - ۲ (چون یه آرایه کشیدم و با چند لیست حلقوی تست کردم دیدم مثل مرتب جستجوی دودویی است)
۱۱۴- ۳
۱۱۵- بدون جواب
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-
در مورد سوال 111 من مطمئنم 3 نمیشه.اگه DAG بود سه درست بود ولی اینجا میشه VlogV+E.این بهترین زمان برای الگوریتم دیکسترا(که اینجا همین الگوریتمو می خواد) است.این زمانو با هیپ فیبوناچی بدست میاد.اگه تو تشخیص الگوریتم مورد نیاز اشتباه نکرده باشم مطمئنم که VlogV+E میشه.
در مورد سوال 114 من زدم BFS یه چیزی یادم بود از اینکه بهترین الگوریتم برای بدست اوردن دورترین راس از راس شروعرو میده.مطمئن نیستم.تو جزوهام میگردم اگه چیزی پیدا کردم اینجا میذارم
(29 بهمن 1390 06:29 ب.ظ)reynard696969 نوشته شده توسط: [ -> ] (29 بهمن 1390 05:24 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]۱۱۰- ۴ (من با محاسبه و رسم درخت به دست آوردم)
۱۱۱- ۳ (مطمئن نیستم)
۱۱۲- بدون جواب
۱۱۳ - ۲ (چون یه آرایه کشیدم و با چند لیست حلقوی تست کردم دیدم مثل مرتب جستجوی دودویی است)
۱۱۴- ۳
۱۱۵- بدون جواب
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-
در مورد سوال ۱۱۱ من مطمئنم ۳ نمیشه.اگه DAG بود سه درست بود ولی اینجا میشه VlogV+E.این بهترین زمان برای الگوریتم دیکسترا(که اینجا همین الگوریتمو می خواد) است.این زمانو با هیپ فیبوناچی بدست میاد.اگه تو تشخیص الگوریتم مورد نیاز اشتباه نکرده باشم مطمئنم که VlogV+E میشه.
در مورد سوال ۱۱۴ من زدم BFS یه چیزی یادم بود از اینکه بهترین الگوریتم برای بدست اوردن دورترین راس از راس شروعرو میده.مطمئن نیستم.تو جزوهام میگردم اگه چیزی پیدا کردم اینجا میذارم
چون تو سوال در مورد چگالی یا انبوه تعداد یال ها در گراف صحبتی نشده و تاکید بر الگوریتم کارا بوده از هیپ باینری استفاده می شه که eLogV می شه اگر تعداد یال ها زیاد باشه از هیپ فیبوناچی استفاده می شه که VlogV +E است که بر این اساس E هم تراز با n^2 است
ترتیت توپولوژیکی با دو بار dfs زدن بدست میاد ...
(29 بهمن 1390 06:29 ب.ظ)reynard696969 نوشته شده توسط: [ -> ] (29 بهمن 1390 05:24 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]۱۱۰- ۴ (من با محاسبه و رسم درخت به دست آوردم)
۱۱۱- ۳ (مطمئن نیستم)
۱۱۲- بدون جواب
۱۱۳ - ۲ (چون یه آرایه کشیدم و با چند لیست حلقوی تست کردم دیدم مثل مرتب جستجوی دودویی است)
۱۱۴- ۳
۱۱۵- بدون جواب
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-
در مورد سوال ۱۱۱ من مطمئنم ۳ نمیشه.اگه DAG بود سه درست بود ولی اینجا میشه VlogV+E.این بهترین زمان برای الگوریتم دیکسترا(که اینجا همین الگوریتمو می خواد) است.این زمانو با هیپ فیبوناچی بدست میاد.اگه تو تشخیص الگوریتم مورد نیاز اشتباه نکرده باشم مطمئنم که VlogV+E میشه.
در مورد سوال ۱۱۴ من زدم BFS یه چیزی یادم بود از اینکه بهترین الگوریتم برای بدست اوردن دورترین راس از راس شروعرو میده.مطمئن نیستم.تو جزوهام میگردم اگه چیزی پیدا کردم اینجا میذارم
منم با vlogv + e موافقم ،دلیلمم استفاده از همون هیپ فیبوناچیه،اتفاقا اینجا چون راجبه چگالی یال ها صحبتی نشده باید واسه کاراترین حالت الگوریتم بدترین شکل گراف و فرض کنیم
واسه اون پیمایشم dfs میشد
این سوال بیشتر به تیپ سوالا هوش میخورد تا الگوریتم!
یادتونه حتما تو bfs هوش گفته بود وقتی هزینه مسیر ها یکسان باشد نزدیکترین هدف و پیدا میکنه ولی واسه دورترین هدف هیچ نظری نداش این الگوریتم،یعنی اگه دورترین یال سطح آخر باشه باید کل گراف بررسی شه.
ولی در مورد dfs چون عمق محدوده در هر صورت زودتر به راس مورد نظر میرسه و کاراتره.
۱۱۰- --
۱۱۱- ۳
۱۱۲- ----
۱۱۳ - ۲
۱۱۴- ۳
3-115
کی گفته مرتب سازی توپولوژیکی با دوباره DFS به دست میاد؟
من این سوال رو مرتب سازی توپولوژیکی زدم به دلایل زیر
اولا مرتب سازی توپولوژیکی به این ترتیبه که یک بار DFS می رید و سپس بر گره ها رو بر اساس زمان خروج به صورت نزولی مرتب می کنید.
حالا دورترین نقطه رو می شه با این مساله به دست اورد.
دقیقا در فصل 22 کتاب CLRS مثالی رو در خصوص تقدم ارائه می ده تحت عنوان مرتب سازی موضعی یا توپولوژیی که از مرتبه تتای V+E است.
همان مثالی که در پوشیدن لباس کدوم رو اول می پوشیم کدوم رو آخر
اینجا هم دورترین نقاط رو می شه همینجوری به دست اورد
دوستان نظر بدن
110- n-1 می شه
111- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|
112- وجود یا عدم وجود دور منفی. طبق گفته CLRS
113- نزدم
114- بحث سر اینه که گراف بدون وزنه-ممکنه ناهمبند/همبند باشه. DFS
115- a=نادرست , b=درست
(30 بهمن 1390 02:25 ب.ظ)باد نوشته شده توسط: [ -> ]کی گفته مرتب سازی توپولوژیکی با دوباره DFS به دست میاد؟
ا
اون مسئله اجزا همبند قوی هست که 2 بار dfs میخواد .
یه نکته : قطر گراف توسط bfs محاسبه میشود.
(30 بهمن 1390 02:25 ب.ظ)باد نوشته شده توسط: [ -> ]کی گفته مرتب سازی توپولوژیکی با دوباره DFS به دست میاد؟
من این سوال رو مرتب سازی توپولوژیکی زدم به دلایل زیر
اولا مرتب سازی توپولوژیکی به این ترتیبه که یک بار DFS می رید و سپس بر گره ها رو بر اساس زمان خروج به صورت نزولی مرتب می کنید.
حالا دورترین نقطه رو می شه با این مساله به دست اورد.
دقیقا در فصل ۲۲ کتاب CLRS مثالی رو در خصوص تقدم ارائه می ده تحت عنوان مرتب سازی موضعی یا توپولوژیی که از مرتبه تتای V+E است.
همان مثالی که در پوشیدن لباس کدوم رو اول می پوشیم کدوم رو آخر
اینجا هم دورترین نقاط رو می شه همینجوری به دست اورد
دوستان نظر بدن
من نمی دونم چرا این قدر بحث سر این سوال شده!!! من که واقعا به نظر BFS میشه.
اولا مرتب سازی توپولوژکی می تونه همون DFS باشه که فقط آخر تابعش یه چاپ بزارید. (از کتاب مقسمی) یه جورایی معادل هستن.
بعد این که داره میگه گراف بدون وزن. خوب ما از همون راسی می خوایم BFS می زنیم حواب به دست میاد. پیچیدگی پیمایش BFS
DFS هم یکیه. به نظر من BFS میشه. حتی اگه کلید چیز دیگه ای رو بگه. درسته که اون ملاک هست ولی اگرچه و اما! :دی
دست کم الان نظرم این هست! :دی