(۲۵ بهمن ۱۳۹۲ ۰۲:۵۲ ب.ظ)izadan11 نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
این ۴ میشه نمونه اش گراف بدون یال
گراف همبند بدون یال ؟؟؟
(۲۵ بهمن ۱۳۹۲ ۰۳:۳۴ ب.ظ)kh.jafarzade نوشته شده توسط:گفته "حداقل" ۳ تا!(25 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/
اگه اشتباه نکنم بخشی از سوال گفته با تعداد ۳ گره !
(۲۵ بهمن ۱۳۹۲ ۰۳:۱۴ ب.ظ)m-behdad نوشته شده توسط: به نظر من هم گزینه ی ۲ و ۳و ۴ جواب سوال بودهرس آلفا و بتا :
سوال هرس آلفا بتا n و O حذف میشدن؟
آره O,N فقط حذف میشد
(۲۵ بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:گزینه دو گفته قطر گراف حداکثر ۲ هست(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/
مثال نقض شما درخته ..!
به نظر من گزینه ۴ اشتباهه
(۲۵ بهمن ۱۳۹۲ ۰۴:۱۵ ب.ظ)E.SH نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:گزینه دو گفته قطر گراف حداکثر ۲ هست(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/
مثال نقض شما درخته ..!
به نظر من گزینه ۴ اشتباهه
یعنی می فرمایید درخت گراف نیست؟ درخت گرافیست با n-1 یال
توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس
- پیدا کردن زیر دنباله به طول k که میانه a داشته باشه
من nk زدم
- اعداد رو میخواست جمع کنه. n عدد ۱ بیتی
من بهترین رو n بدترین رو هم nlgn زدم
خواهشن بگین ۱ی از اینا رو درست زدم :دی
))(۲۵ بهمن ۱۳۹۲ ۰۴:۲۸ ب.ظ)mahdi-313 نوشته شده توسط:به نظر منم یه درختی که به صورت مورب باشه. یعنی غیر از اول و آخر درجه هر راسش ۲ باشه مثال نقض گزینه ۲ میشه(25 بهمن ۱۳۹۲ ۰۴:۱۵ ب.ظ)E.SH نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۲:۴۹ ب.ظ)mahdi-313 نوشته شده توسط:گزینه دو گفته قطر گراف حداکثر ۲ هست(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
یک درخت به صورت یک خط صاف متشکل از ۴ گره و ۳ یال در نظر بگیرید، هم bfs و هم dfs یکی می شود فلذا گزینه ۲ غلط میشه/
مثال نقض شما درخته ..!
به نظر من گزینه ۴ اشتباهه
یعنی می فرمایید درخت گراف نیست؟ درخت گرافیست با n-1 یال
پس گزینه ۴ میشه جواب
(۲۵ بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: به نظر منم یه درختی که به صورت مورب باشه. یعنی غیر از اول و آخر درجه هر راسش ۲ باشه مثال نقض گزینه ۲ میشه
پس گزینه ۴ میشه جواب
خدا کنه ۴ باشه من چهار زدم...
سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
%۱۰۰ %۱۰۰ گزینه ۴ میشه اینم مثال نقضش دیگه حرفی نمیمونه
(۲۵ بهمن ۱۳۹۲ ۰۵:۰۴ ب.ظ)mostafat نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
%۱۰۰ %۱۰۰ گزینه ۴ میشه اینم مثال نقضش دیگه حرفی نمیمونه
کاملا درست گفتی منم همینو زدم
(۲۵ بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس
من این سوال رو دیدم تعجب کردم چرا سیستم عامل دادن :ی
این سوال همون الگوریتم های زمانبدی ریال تایم بود :یییییی
اگر اشتباه نکنم باید لکستی تایم رو به دست می اوردیم به ترتیب اونی که کوچیکتر رو انجام میدادیم
td-ti
ti زمان پردازش
td زمانی که باید تموم بشه
(۲۵ بهمن ۱۳۹۲ ۰۶:۴۱ ب.ظ)mrdudu نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس
من این سوال رو دیدم تعجب کردم چرا سیستم عامل دادن :ی
این سوال همون الگوریتم های زمانبدی ریال تایم بود :یییییی
اگر اشتباه نکنم باید لکستی تایم رو به دست می اوردیم به ترتیب اونی که کوچیکتر رو انجام میدادیم
td-ti
ti زمان پردازش
td زمانی که باید تموم بشه
من چن تا فرآیند مثال زدم و این مقادیرو واسش حساب کردم گزینه ۲ یعنی Pi غیر نزولی با اختلاف کمی از Di غیر نزولی کمتر میشد
(۲۵ بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟اولی رو که گفتم موند دومی همم اینو من زدم nlogk چون k<=n/2 پس با n حتما a هم میوفته تو مجموعه k ولی اخرشه پس با عمله logk میشه مرتبش کرد :ی
- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس
- پیدا کردن زیر دنباله به طول k که میانه a داشته باشه
من nk زدم
- اعداد رو میخواست جمع کنه. n عدد ۱ بیتی
من بهترین رو n بدترین رو هم nlgn زدم
سومی من زدم بهترین بدترینش n
اون سوالی که گفته میخوایم a میانه باشه و kتا عدد از ارایه داشته باشیم که نصفشون کوچکتر و نصفشون بزرگتر از a باشند،میشه از مرتبه n.
روی آرایه با a یک پارتیشن میزنیم. اعداد قبل a از اون کوچیکترند و بعد از اون بزرگتر. البته ترتیبشون درست نیست! که صورت سوال هم اینو نخواسته.
حالا شما k/2 از قبل و k/2از بعد a انتخاب میکنی که a میشه میانه و مرتبه زمانی هم میشه n.
اشتباهی شد :دی
(۲۵ بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
گزینه ۳
روش من:
شما ۳ گره کامل و همبندو در نظر بگیرید ...ما میدونیم که یکی از روشهای تشخیص ۲بخشی بودن اینه که بتونیم با ۲تا رنگ به شکل سازگار(ارضای محدودیت) رنگ آمیزی بشن و ازونجایی که این اتفاق نمیوفته این گزینه قطعا غلطه.