به نظر من:
۱-۱۱۰
۳-۱۱ (تویه clrs کاملا گفته شده اگه یالها بین ۱ تا w باشد میشه e+vlogw یا حتی vw+e در نتیجه چون w=c و ثابته میشه e+v
۱-۱۱۲
۴-۱۱۴
۲-۱۱۵
(۳۰ بهمن ۱۳۹۰ ۰۲:۳۸ ب.ظ)fazel-d نوشته شده توسط: ۱۱۰- n-1 می شه
۱۱۱- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|
۱۱۲- وجود یا عدم وجود دور منفی. طبق گفته CLRS
۱۱۳- نزدم
۱۱۴- بحث سر اینه که گراف بدون وزنه-ممکنه ناهمبند/همبند باشه. DFS
۱۱۵- a=نادرست , b=درست
برای سوال ۱۱۱
دوست عزیز من، کوتاه ترین مسیر از لحاظ تعداد یال با وزن مساوی یا گراف بدون وزن را می توان با BFS بدست آورد در غیر این صورت باید از الگوریتم های مثل دایکسترا استفاده کرد
(۳۰ بهمن ۱۳۹۰ ۰۲:۳۸ ب.ظ)fazel-d نوشته شده توسط: ۱۱۱- شما با DFS یا BFS می تونید کوتاهترین مسیر رو هم پیدا کنید. |v|+|E|
کوتاهترین مسیر رو زمانی با BFSیا DFS میتونیم بیابیم که اندازه یالها برابر باشه که اینجا نیست..
خودش گفته اندازه حداکثرC
در مورد سوال ۱۱۲ فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه
۲۲/۲-۷
The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;
من خودم فکر میکنم که ۱۱۴ bfs هست اما نظرات دوستان هم حاوی نکاتی هست که نمیشه ازش چشم پوشید . درباره تست ۱۱۲ فکر میکنم۱ صحیح باشه .۱۱۳ هم احتمال زیاد ۲ صحیح هست اما تا حالا ندیدم کسی بتونه دقیق اثبات کنه ( همه اینا طبق دفترچه A ) هست
۱۱۵ فکر میکنم هر دو غلطه اما نمیتونم اثبات کنم.
(۳۰ بهمن ۱۳۹۰ ۰۶:۵۷ ب.ظ)tarang نوشته شده توسط: در مورد سوال ۱۱۲ فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه
۲۲/۲-۷
The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;
۱/ فلوید با یال منفی کار می کنه
۲/ وقتی دور منفی داشته باشیم خوب طبیعتا مساله جوابش منفی بینهایت هست.
۳/ الگوریتم فلوید می تونه با تکرار خودش، دور منفی رو تشخیص بده. یعنی در تکرار بعدی اگه فاصله ها کمتر شده دور منفی داره.
(۳۰ بهمن ۱۳۹۰ ۰۷:۰۶ ب.ظ)imi نوشته شده توسط:صورت سوال گفته فاصله هر گره با خودش در تمام مراحل صفر فرض شود نظرتون در مورد این چیه(30 بهمن ۱۳۹۰ ۰۶:۵۷ ب.ظ)tarang نوشته شده توسط: در مورد سوال ۱۱۲ فلوید
سوال گفته فرض کنید در هر مرحله فاصله هر گره با خودش صفر می باشد الگوریتم فلوید بعد از n-1 مرحله متوقف میشه پس در مرحله اخر عناصر قطر اصلی صفر می باشد ،نمی توانیم دور منفی تشخیص دهیم پس اگر دور منفی نداشته باشیم ولی یال منفی داشته باشیم درست کار نمی کند پس گزینه ۴ درسته طبق دفترچه A
سوال ۱۱۴
جزوه طراحی تابستان سیدجوادی همین مسئله رو با bfs حل کرده ،تمرین clrs هم هست که تمرینات bfs می باشه
۲۲/۲-۷
The diameter of a tree T = (V, E) is given by
max
u,v∈V
δ(u, v) ;
۱/ فلوید با یال منفی کار می کنه
۲/ وقتی دور منفی داشته باشیم خوب طبیعتا مساله جوابش منفی بینهایت هست.
۳/ الگوریتم فلوید می تونه با تکرار خودش، دور منفی رو تشخیص بده. یعنی در تکرار بعدی اگه فاصله ها کمتر شده دور منفی داره.
(۳۰ بهمن ۱۳۹۰ ۰۷:۱۵ ب.ظ)tarang نوشته شده توسط: صورت سوال گفته فاصله هر گره با خودش در تمام مراحل صفر فرض شود نظرتون در مورد این چیه
خوب همیشه همین طور بوده! مگه چیز خاصی هست؟ مثلا حالا این فرض چه اثری داره؟ من از این فرض مثلا این رو می فهم که گرف طوقه وزن دار نداره.
(۳۰ بهمن ۱۳۹۰ ۰۷:۲۰ ب.ظ)imi نوشته شده توسط: خوب همیشه همین طور بوده! مگه چیز خاصی هست؟ مثلا حالا این فرض چه اثری داره؟ من از این فرض مثلا این رو می فهم که گرف طوقه وزن دار نداره.نه ،برای شروع اره ولی برای بقیه مراحل اینجور نیست فرض کن فاصله یک گره خودش همیشه صفر باشه خوب اگر دور منفی داشته باشیم مرحله بعد باید منفی بشه ولی ما صفر رو انتخاب کردیم این مسئله با فلوید اصلی فرق داره
(۳۰ بهمن ۱۳۹۰ ۰۷:۳۵ ب.ظ)tarang نوشته شده توسط: نه ،برای شروع اره ولی برای بقیه مراحل اینجور نیست فرض کن فاصله یک گره خودش همیشه صفر باشه خوب اگر دور منفی داشته باشیم مرحله بعد باید منفی بشه ولی ما صفر رو انتخاب کردیم این مسئله با فلوید اصلی فرق داره
والله من نظرم عوض نشد. نمی دونم دیگه. باید کلید ها بیاد ببینم نظر اون ها چیه!
(۲۹ بهمن ۱۳۹۰ ۱۲:۳۰ ب.ظ)LordAriana نوشته شده توسط:(29 بهمن ۱۳۹۰ ۱۱:۴۱ ق.ظ)Masoud05 نوشته شده توسط: طبق صحبت های بچه های مانشت و دوستانم بعد از آزمون تا حالا این نتایج بدست آمده( نظر خودم نیست بلکه نظر بچه هاست )
سوالات با توجه عکس بالا هست:
۱۱۰‌: بعضیا میگفتن ۱ و بعضیا ۲
۱۱۱: بین ۱و ۳
۱۱۲: ۱ بنظرم همین درسته
۱۱۳: ۱ و ۲
۱۱۴: ۳ یا ۴ من فکر میکنم ۴ باشه اما مطمئن نیستم
۱۱۵: احتمال داره هر ۲ نادرست باشه اما راجع به این سوال بحث جدی نشده!
۱۱۰: بین ۱ و ۴ ولی من حساب کردم ۴
۱۱۱: ۱
۱۱۲: ۱
۱۱۳: -
۱۱۴: ۳ (DFS) شما تو ویکی پدیا هم بری نوشته اینو
۱۱۵: ۱مقدار بحث برانگیزه (:
سوال ۱ رو بر اساس n=4 بگیرد گزینه یک به دست میاد.
براساس n=0 , n=1 گزینه های ۲و۳ نقض میشن و گزینه ۱ ,۴ می مونه.
این دو گزینه تا n =2,n=3 هر دو برابر هستن. اما وقتی به مقادیر بالای ۳ یعنی ۴ و ۵ میرسه گزینه ۴ غلط از آب در میاد.
می تونید تست نمایید من کامل تست کردم. با تشکر.
(۳۰ بهمن ۱۳۹۰ ۰۷:۵۴ ب.ظ)lonelyforever نوشته شده توسط: سوال ۱ رو بر اساس n=4 بگیرد گزینه یک به دست میاد.
براساس n=0 , n=1 گزینه های ۲و۳ نقض میشن و گزینه ۱ ,۴ می مونه.
این دو گزینه تا n =2,n=3 هر دو برابر هستن. اما وقتی به مقادیر بالای ۳ یعنی ۴ و ۵ میرسه گزینه ۴ غلط از آب در میاد.
می تونید تست نمایید من کامل تست کردم. با تشکر.
نمی دونم چرا سره سوال ۱۱۱ مشکل دارید. دقیقا طراح از همین نکته clrs سوال داده که در تمرین ۶-۳-۲۴ و ۷-۳-۲۴ ذکر شده و logw=logc=constant .
(۳۰ بهمن ۱۳۹۰ ۱۱:۴۲ ب.ظ)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 | )
همه گزینه ها طولانی ترین مسیرو میدن. اما به نظر من سریع ترین الگوریتم ترتیب توپولوژیکی ایه