من بعد از کلی تست روی انواع گراف ها به جوا هردو رسیدم.!
بچه ها این سوال که ساده است .
البته حق میدم واقعا اعصاب آدمو خورد می کنن
۲ حالت داره: وزن یالها تکراری داشته باشه یا نداشته باشه . اگه متمایز باشه که درخت MST یکتاست . اگه متمایز نباشه هم درخت یکتا نیست ولی کم قدرت ترین درخت همون MST میشه که بالاخره وزن سنگین ترین یالش کمینه باشه . یعنی حتی اگه چند MST داشته باشیم بالاخره قدرتشون یکیه . پس هر دو الگورین کروسکال و پریم MST رو میدن که درسته . درست میگم؟
بچه ها جواب سوال ۹۶ و ۱۰۰ چی ؟ کسی میدونه ؟
۹۶ - بزرگترین زیردرخت کاملا متوازن
۱۰۰ - هزینه سرشکن شده درج n عنصر . نظر من:
بدترین حالت در هر مرحله از ۰ تا log n حلقه اجرا میشه و چون n عمل درج انجام میدیم میشه n Logn و هزینه سرشکن شده میشه (n Logn/n = o(Logn
گزینه ۲ درسته؟
(۲۹ بهمن ۱۳۹۰ ۰۳:۳۵ ب.ظ)afshinmu نوشته شده توسط: بچه ها این سوال که ساده است .-=-==-=-=-=-=-=-=-=-=-=--=-==--=-=
البته حق میدم واقعا اعصاب آدمو خورد می کنن
۲ حالت داره: وزن یالها تکراری داشته باشه یا نداشته باشه . اگه متمایز باشه که درخت MST یکتاست . اگه متمایز نباشه هم درخت یکتا نیست ولی کم قدرت ترین درخت همون MST میشه که بالاخره وزن سنگین ترین یالش کمینه باشه . یعنی حتی اگه چند MST داشته باشیم بالاخره قدرتشون یکیه . پس هر دو الگورین کروسکال و پریم MST رو میدن که درسته . درست میگم؟
بچه ها جواب سوال ۹۶ و ۱۰۰ چی ؟ کسی میدونه ؟
۹۶ - بزرگترین زیردرخت کاملا متوازن
۱۰۰ - هزینه سرشکن شده درج n عنصر . نظر من:
بدترین حالت در هر مرحله از ۰ تا log n حلقه اجرا میشه و چون n عمل درج انجام میدیم میشه n Logn و هزینه سرشکن شده میشه (n Logn/n = o(Logn
گزینه ۲ درسته؟
من تقریبا مطمئنم که o(1) میشه جواب.یه همچین سوالی تو یه جزو از پارسه بود.حلقه logn بار اجزا میشه.تو هربار اجراش یک یا دو مقایسه انجام میده.درحالت سرشکن میشه ۲logn/logn که میشه ۲ که همون o(1).من اینجوری استدلال کردم.تو جزوه پارسه هم بود همینجوری گفته بود.شایدک من اشتباه میکنمو این سوال شبیه اون نیست
(۲۹ بهمن ۱۳۹۰ ۰۶:۰۹ ب.ظ)reynard696969 نوشته شده توسط: من تقریبا مطمئنم که o(1) میشه جواب.یه همچین سوالی تو یه جزو از پارسه بود.حلقه logn بار اجزا میشه.تو هربار اجراش یک یا دو مقایسه انجام میده.درحالت سرشکن میشه ۲logn/logn که میشه ۲ که همون o(1).من اینجوری استدلال کردم.تو جزوه پارسه هم بود همینجوری گفته بود.شایدک من اشتباه میکنمو این سوال شبیه اون نیست
n عمل داره انجام میشه اونوقت شما بر logn تقسیم می کنید؟ با حساب شما میشه logn/n . در ضمن من خودم یه مثال زدم که با n=8 15 تا مقایسه لازم داشت که n نمیشه در نظر گرفت و اگه nlogn در نظر بگیریم میشه nlogn/n که همون logn هستش . البته من نمی دونم nlogn می تونیم در نظر بگیریم یا باید بیشتر باشه ولی مطمئنا از مرتبه logn کمتر نیست
(۲۹ بهمن ۱۳۹۰ ۰۷:۴۹ ب.ظ)afshinmu نوشته شده توسط: n عمل داره انجام میشه اونوقت شما بر logn تقسیم می کنید؟ با حساب شما میشه logn/n . در ضمن من خودم یه مثال زدم که با n=8 15 تا مقایسه لازم داشت که n نمیشه در نظر گرفت و اگه nlogn در نظر بگیریم میشه nlogn/n که همون logn هستش . البته من نمی دونم nlogn می تونیم در نظر بگیریم یا باید بیشتر باشه ولی مطمئنا از مرتبه logn کمتر نیستدرسته ، منم طی محاسباتی که سر جلسه کردم همون lgn میشه.
یکی nk بود یکی nlogk یکی klogn گزینه دیگه چی بود؟اصلا nlogn داشت?
بچه ها این سوال ۹۶ رو کسی زده لطفا بگید که تحلیلتون برای حل سوال چطور بوده؟
(۳۰ بهمن ۱۳۹۰ ۰۱:۲۸ ق.ظ)mp1368 نوشته شده توسط: بچه ها این سوال ۹۶ رو کسی زده لطفا بگید که تحلیلتون برای حل سوال چطور بوده؟
من ۱ زدم ولی هیچ دفاعی ندارم ازش
(۳۰ بهمن ۱۳۹۰ ۰۱:۲۹ ق.ظ)afshinmu نوشته شده توسط:(30 بهمن ۱۳۹۰ ۰۱:۲۸ ق.ظ)mp1368 نوشته شده توسط: بچه ها این سوال ۹۶ رو کسی زده لطفا بگید که تحلیلتون برای حل سوال چطور بوده؟
من ۱ زدم ولی هیچ دفاعی ندارم ازش
من خودم هم ۱ رو زذم (مبنا دفترچه A).
ولی به قول شما فقط به تحلیل اون لحظه خودم اعتماد کردم و تست رو زدم ولی خوب استدلالم حداقل واسه خودم که خوب بود.
بچه ها میتونن سوال ۹۹ رو با این گراف امتحان کنن؟
به نظر من دقت نمی کنیم که گفته کوچکتر باشد.نه کوچکتر مساوی
وزن بیشترین یال ۱۱ هست که برابر وزن یک درخت پوشاست.
خروجی کدوم الگوریتم [b]همواره [/b]کمتر است ؟
با این مثال می بینیم که هیچ کدوم
(۳۰ بهمن ۱۳۹۰ ۰۱:۳۰ ب.ظ)deledivouneh نوشته شده توسط: بچه ها میتونن سوال ۹۹ رو با این گراف امتحان کنن؟
به نظر من دقت نمی کنیم که گفته کوچکتر باشد.نه کوچکتر مساوی
وزن بیشترین یال ۱۱ هست که برابر وزن یک درخت پوشاست.
خروجی کدوم الگوریتم [b]همواره [/b]کمتر است ؟
با این مثال می بینیم که هیچ کدوم
میگم نکنه جواب الکی من به این تست درست دربیاد (ارسال ۳۵) چون این گرافی که شما کشیدی داره گزینه (هردو) را نقض می کنه.
درخت پوشای این گراف هم با کراسکال و هم با پریم میشه این: (اگه من اشتباه نکنم)
که این هم که خوب پرقدرت ترین ش یال ۵ هست دیگه.
(۳۰ بهمن ۱۳۹۰ ۰۸:۴۵ ب.ظ)AmirGooran نوشته شده توسط: درخت پوشای این گراف هم با کراسکال و هم با پریم میشه این: (اگه من اشتباه نکنم)
که این هم که خوب پرقدرت ترین ش یال ۵ هست دیگه.
جواب شما مربوط به یال هست ولی سوال گفته کم قدرت ترین درخت(یعنی جمع وزن یال های درخت ).
این درسته که هر دو تا می تونن باشن ولی همواره نه
سوال گفته : قدرت یعنی : وزن کمترین یال در یک درخت پوشا
بنابراین قدرت درخت پوشای من میشه : ۵
یعنی درختی وجود داره که قدرتش از این کمتر باشه؟!
(۳۰ بهمن ۱۳۹۰ ۰۱:۳۰ ب.ظ)deledivouneh نوشته شده توسط: بچه ها میتونن سوال ۹۹ رو با این گراف امتحان کنن؟
به نظر من دقت نمی کنیم که گفته کوچکتر باشد.نه کوچکتر مساوی
وزن بیشترین یال ۱۱ هست که برابر وزن یک درخت پوشاست.
خروجی کدوم الگوریتم [b]همواره [/b]کمتر است ؟
با این مثال می بینیم که هیچ کدوم
گفته کوچکترین دوست گلم . بین ۲و۴و۳و۲و۴ کدوم کوچکترینه؟؟؟؟مشخصه ۲ دیگه . ارتباطی به بحث کوچکتر یا کوچکتر مساوی نداره . به هیچ وجه . وگرنه هیچ الگوریتمی قابل ابداع نیست !!!! نه الان بلکه در آینده . چون همیشه گرافی میشه مثال زد که کوچکترین ( با تفسیر شما) رو نشه پیدا کرد .