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

[kh.jafarzade]

(۲۵ بهمن ۱۳۹۲ ۰۲:۵۲ ب.ظ)izadan11 نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط:  سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل

این ۴ میشه نمونه اش گراف بدون یال

گراف همبند بدون یال ؟؟؟

[mahdi-313]

(۲۵ بهمن ۱۳۹۲ ۰۳:۳۴ ب.ظ)kh.jafarzade نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط:  سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل

یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/

اگه اشتباه نکنم بخشی از سوال گفته با تعداد ۳ گره !

گفته "حداقل" ۳ تا!

[E.SH]

(۲۵ بهمن ۱۳۹۲ ۰۳:۱۴ ب.ظ)m-behdad نوشته شده توسط:  به نظر من هم گزینه ی ۲ و ۳و ۴ جواب سوال بود

سوال هرس آلفا بتا n و O حذف میشدن؟

هرس آلفا و بتا :
آره O,N فقط حذف میشد

[E.SH]

(۲۵ بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط:  سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل

یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/

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

[mahdi-313]

(۲۵ بهمن ۱۳۹۲ ۰۴:۱۵ ب.ظ)E.SH نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط:  سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل

یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/

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

یعنی می فرمایید درخت گراف نیست؟ درخت گرافیست با n-1 یال

[mehdi1902]

توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟

- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس

- پیدا کردن زیر دنباله به طول k که میانه a داشته باشه
من nk زدم

- اعداد رو میخواست جمع کنه. n عدد ۱ بیتی
من بهترین رو n بدترین رو هم nlgn زدم

خواهشن بگین ۱ی از اینا رو درست زدم :دی ))

---

(۲۵ بهمن ۱۳۹۲ ۰۴:۲۸ ب.ظ)mahdi-313 نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۴:۱۵ ب.ظ)E.SH نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط:  سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل

یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/

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

یعنی می فرمایید درخت گراف نیست؟ درخت گرافیست با n-1 یال

به نظر منم یه درختی که به صورت مورب باشه. یعنی غیر از اول و آخر درجه هر راسش ۲ باشه مثال نقض گزینه ۲ میشه
پس گزینه ۴ میشه جواب

[alagh]

(۲۵ بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط:  به نظر منم یه درختی که به صورت مورب باشه. یعنی غیر از اول و آخر درجه هر راسش ۲ باشه مثال نقض گزینه ۲ میشه
پس گزینه ۴ میشه جواب

خدا کنه ۴ باشه من چهار زدم...

[mostafat]

سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل


%۱۰۰ %۱۰۰ گزینه ۴ میشه اینم مثال نقضش دیگه حرفی نمیمونه

[ali_t1234]

(۲۵ بهمن ۱۳۹۲ ۰۵:۰۴ ب.ظ)mostafat نوشته شده توسط:  سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل


%۱۰۰ %۱۰۰ گزینه ۴ میشه اینم مثال نقضش دیگه حرفی نمیمونه

کاملا درست گفتی منم همینو زدم

[mrdudu]

(۲۵ بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط:  توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟

- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس

من این سوال رو دیدم تعجب کردم چرا سیستم عامل دادن :ی

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

اگر اشتباه نکنم باید لکستی تایم رو به دست می اوردیم به ترتیب اونی که کوچیکتر رو انجام میدادیم

td-ti

ti زمان پردازش

td زمانی که باید تموم بشه

[aniss]

(۲۵ بهمن ۱۳۹۲ ۰۶:۴۱ ب.ظ)mrdudu نوشته شده توسط:  

(25 بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط:  توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟

- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس

من این سوال رو دیدم تعجب کردم چرا سیستم عامل دادن :ی

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

اگر اشتباه نکنم باید لکستی تایم رو به دست می اوردیم به ترتیب اونی که کوچیکتر رو انجام میدادیم

td-ti

ti زمان پردازش

td زمانی که باید تموم بشه

من چن تا فرآیند مثال زدم و این مقادیرو واسش حساب کردم گزینه ۲ یعنی Pi غیر نزولی با اختلاف کمی از Di غیر نزولی کمتر میشد

[mrdudu]

(۲۵ بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط:  توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟

- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس

- پیدا کردن زیر دنباله به طول k که میانه a داشته باشه
من nk زدم

- اعداد رو میخواست جمع کنه. n عدد ۱ بیتی
من بهترین رو n بدترین رو هم nlgn زدم

اولی رو که گفتم موند دومی همم اینو من زدم nlogk چون k<=n/2 پس با n حتما a هم میوفته تو مجموعه k ولی اخرشه پس با عمله logk میشه مرتبش کرد :ی

سومی من زدم بهترین بدترینش n

[Amoojan]

اون سوالی که گفته میخوایم a میانه باشه و kتا عدد از ارایه داشته باشیم که نصفشون کوچکتر و نصفشون بزرگتر از a باشند،میشه از مرتبه n.
روی آرایه با a یک پارتیشن میزنیم. اعداد قبل a از اون کوچیکترند و بعد از اون بزرگتر. البته ترتیبشون درست نیست! که صورت سوال هم اینو نخواسته.
حالا شما k/2 از قبل و k/2از بعد a انتخاب میکنی که a میشه میانه و مرتبه زمانی هم میشه n.

[Riemann]

اشتباهی شد :دی

[kh.jafarzade]

(۲۵ بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط:  سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟

۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل

گزینه ۳
روش من:
شما ۳ گره کامل و همبندو در نظر بگیرید ...ما میدونیم که یکی از روشهای تشخیص ۲بخشی بودن اینه که بتونیم با ۲تا رنگ به شکل سازگار(ارضای محدودیت) رنگ آمیزی بشن و ازونجایی که این اتفاق نمیوفته این گزینه قطعا غلطه.