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

به نظر من:
1-110
3-11 (تویه clrs کاملا گفته شده اگه یالها بین 1 تا w باشد میشه e+vlogw یا حتی vw+e در نتیجه چون w=c و ثابته میشه e+v
1-112
4-114
2-115

(30 بهمن 1390 02:38 ب.ظ)fazel-d نوشته شده توسط: [ -> ]۱۱۰- n-1 می شه
۱۱۱- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|
۱۱۲- وجود یا عدم وجود دور منفی. طبق گفته CLRS
۱۱۳- نزدم
۱۱۴- بحث سر اینه که گراف بدون وزنه-ممکنه ناهمبند/همبند باشه. DFS
۱۱۵- a=نادرست , b=درست

برای سوال 111
دوست عزیز من، کوتاه ترین مسیر از لحاظ تعداد یال با وزن مساوی یا گراف بدون وزن را می توان با BFS بدست آورد در غیر این صورت باید از الگوریتم های مثل دایکسترا استفاده کرد

(30 بهمن 1390 02:38 ب.ظ)fazel-d نوشته شده توسط: [ -> ]۱۱۱- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|

کوتاهترین مسیر رو زمانی با BFSیا DFS میتونیم بیابیم که اندازه یالها برابر باشه که اینجا نیست..
خودش گفته اندازه حداکثرC

در مورد سوال 112 فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه 4 درسته طبق دفترچه A
سوال 114
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه

22.2-7

The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;

من خودم فکر میکنم که 114 bfs هست اما نظرات دوستان هم حاوی نکاتی هست که نمیشه ازش چشم پوشید . درباره تست 112 فکر میکنم1 صحیح باشه .113 هم احتمال زیاد 2 صحیح هست اما تا حالا ندیدم کسی بتونه دقیق اثبات کنه ( همه اینا طبق دفترچه A ) هست
115 فکر میکنم هر دو غلطه اما نمیتونم اثبات کنم.

(30 بهمن 1390 06:57 ب.ظ)tarang نوشته شده توسط: [ -> ]در مورد سوال ۱۱۲ فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه

۲۲/۲-۷

The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;

1. فلوید با یال منفی کار می کنه
2. وقتی دور منفی داشته باشیم خوب طبیعتا مساله جوابش منفی بینهایت هست.
3. الگوریتم فلوید می تونه با تکرار خودش، دور منفی رو تشخیص بده. یعنی در تکرار بعدی اگه فاصله ها کمتر شده دور منفی داره.

(30 بهمن 1390 07:06 ب.ظ)imi نوشته شده توسط: [ -> ]

(30 بهمن 1390 06:57 ب.ظ)tarang نوشته شده توسط: [ -> ]در مورد سوال ۱۱۲ فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه

۲۲/۲-۷

The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;

۱/ فلوید با یال منفی کار می کنه
۲/ وقتی دور منفی داشته باشیم خوب طبیعتا مساله جوابش منفی بینهایت هست.
۳/ الگوریتم فلوید می تونه با تکرار خودش، دور منفی رو تشخیص بده. یعنی در تکرار بعدی اگه فاصله ها کمتر شده دور منفی داره.

صورت سوال گفته فاصله هر گره با خودش در تمام مراحل صفر فرض شود نظرتون در مورد این چیه

(30 بهمن 1390 07:15 ب.ظ)tarang نوشته شده توسط: [ -> ]صورت سوال گفته فاصله هر گره با خودش در تمام مراحل صفر فرض شود نظرتون در مورد این چیه

خوب همیشه همین طور بوده! مگه چیز خاصی هست؟ مثلا حالا این فرض چه اثری داره؟ من از این فرض مثلا این رو می فهم که گرف طوقه وزن دار نداره.

(30 بهمن 1390 07:20 ب.ظ)imi نوشته شده توسط: [ -> ]خوب همیشه همین طور بوده! مگه چیز خاصی هست؟ مثلا حالا این فرض چه اثری داره؟ من از این فرض مثلا این رو می فهم که گرف طوقه وزن دار نداره.

نه ،برای شروع اره ولی برای بقیه مراحل اینجور نیست فرض کن فاصله یک گره خودش همیشه صفر باشه خوب اگر دور منفی داشته باشیم مرحله بعد باید منفی بشه ولی ما صفر رو انتخاب کردیم این مسئله با فلوید اصلی فرق داره

(30 بهمن 1390 07:35 ب.ظ)tarang نوشته شده توسط: [ -> ]نه ،برای شروع اره ولی برای بقیه مراحل اینجور نیست فرض کن فاصله یک گره خودش همیشه صفر باشه خوب اگر دور منفی داشته باشیم مرحله بعد باید منفی بشه ولی ما صفر رو انتخاب کردیم این مسئله با فلوید اصلی فرق داره

والله من نظرم عوض نشد. نمی دونم دیگه. باید کلید ها بیاد ببینم نظر اون ها چیه!

(29 بهمن 1390 12:30 ب.ظ)LordAriana نوشته شده توسط: [ -> ]

(29 بهمن 1390 11:41 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]طبق صحبت های بچه های مانشت و دوستانم بعد از آزمون تا حالا این نتایج بدست آمده( نظر خودم نیست بلکه نظر بچه هاست )
سوالات با توجه عکس بالا هست:
۱۱۰‌: بعضیا میگفتن ۱ و بعضیا ۲
۱۱۱: بین ۱و ۳
۱۱۲: ۱ بنظرم همین درسته
۱۱۳: ۱ و ۲
۱۱۴: ۳ یا ۴ من فکر میکنم ۴ باشه اما مطمئن نیستم
۱۱۵: احتمال داره هر ۲ نادرست باشه اما راجع به این سوال بحث جدی نشده!

۱۱۰: بین ۱ و ۴ ولی من حساب کردم ۴
۱۱۱: ۱
۱۱۲: ۱
۱۱۳: -
۱۱۴: ۳ (DFS) شما تو ویکی پدیا هم بری نوشته اینو
۱۱۵: ۱مقدار بحث برانگیزه (:

سوال 1 رو بر اساس n=4 بگیرد گزینه یک به دست میاد.
براساس n=0 , n=1 گزینه های 2و3 نقض میشن و گزینه 1 ,4 می مونه.
این دو گزینه تا n =2,n=3 هر دو برابر هستن. اما وقتی به مقادیر بالای 3 یعنی 4 و 5 میرسه گزینه 4 غلط از آب در میاد.
می تونید تست نمایید من کامل تست کردم. با تشکر.

(30 بهمن 1390 07:54 ب.ظ)lonelyforever نوشته شده توسط: [ -> ]سوال ۱ رو بر اساس n=4 بگیرد گزینه یک به دست میاد.
براساس n=0 , n=1 گزینه های ۲و۳ نقض میشن و گزینه ۱ ,۴ می مونه.
این دو گزینه تا n =2,n=3 هر دو برابر هستن. اما وقتی به مقادیر بالای ۳ یعنی ۴ و ۵ میرسه گزینه ۴ غلط از آب در میاد.
می تونید تست نمایید من کامل تست کردم. با تشکر.

نمی دونم چرا سره سوال 111 مشکل دارید. دقیقا طراح از همین نکته clrs سوال داده که در تمرین 6-3-24 و 7-3-24 ذکر شده و logw=logc=constant .

(30 بهمن 1390 11:42 ب.ظ)esi نوشته شده توسط: [ -> ]نمی دونم چرا سره سوال ۱۱۱ مشکل دارید. دقیقا طراح از همین نکته clrs سوال داده که در تمرین ۶-۳-۲۴ و ۷-۳-۲۴ ذکر شده و logw=logc=constant .

منم همین زدم اما clrs رو نخوندم که مطمئن باشم.

For sparse graphs, that is, graphs with far fewer than O( | V | 2) edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. With a binary heap, the algorithm requires O(( | E | + | V | )log | V | ) time (which is dominated by O( | E | log | V | ), assuming the graph is connected). To avoid O(|V|) look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap's index (and keep it up to date as priority queue Q changes), making it take only O(log | V | ) time instead. The Fibonacci heap improves this to O( | E | + | V | log | V | ).

کارا (Efficiency) اشاره شده به Binary Heap و در نهایت O( | E | log | V | )

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