سلام دوستان لطفا کمک کنید کمی توی تحلیل این تست ایراد دارم
(۰۹ شهریور ۱۳۹۲ ۱۰:۴۵ ب.ظ)aria نوشته شده توسط: سلام دوستان لطفا کمک کنید کمی توی تحلیل این تست ایراد دارم
گزینه اول اون اُ، بیگ اُ هست . نه لیتل اُو
لطفا درست کنید.
سلام
من به نظرم گزینه‌ی ۳ درست میشه. یعنی این گزینه غلطه
مثال نقض :
فرض کنید
f(n)=n^2
باشه. بنابراین یه مثال از مجموعه‌ی Omega (f(n)) مثلا n هستش. همین طور یه مثال از O(f(n)) میشه n^3 رو گفت. حالا جمع اینا چی میشه ؟؟
n^3 + n که این میشه O(f(n)) و نمیشه teta (f(n))
ببخشید این پرانتزا قاطیه. شما فک کن درسته
)
جواب گزینه۳
--------------------------------------------------------------------------------------------------------------------------------------------------
فرقی نمی کنه گزینه ۱ در هر صورت چه o وچه O درسته ولی در ستش همونیه که نوشتم توی کتاب پارسه O زده ولی o بودن ان زیبایی اون گزینه است کتاب نصیر o نوشته
در هر صورت من مشکلم اینجاست که مثلا گزینه ۳ چی رو با چی جمع کرده توی جواب ها از اونها به عنوان مجموعه یاد کرده یعنی حالتی مجموعه ای با اون رفتار شده
گزینه ۴ رو هم اگه می تونید تحلیل کنید
جواب تست رو هم پیوست کردم
___________________________________________________________________________________--
ببینید برای این که میگین چی رو با چی جمع کرده توی گزینه ۳، اینا مجموعه هستن دیگه. هر عضویش میشه انتخاب شه.
O(f(n)) مجموعه ای هستش که درجه اعضاش ببشتر از f هستن. حالا این توابع با هرچی که جمع بشن بازم درجشون بیشتر از f میمونه. یعنی میشه O(f(n)) ولی نمیتونه عضو teta باشه !
راجع به گزینه‌ی ۴ :
ببین میدونیم که
[tex]g(n) = \Omega (f(n))[/tex]
این یعنی چی ؟؟ یعنی g یه تابعی هستش که درجه ـش از f کمتره. حالا O(f(n)) چه تابعایی هستن ؟؟؟ تابعایی که درجه ـشون از f بیشتره. اسمشون رو میزاریم مثلا h.
چون میدونیم درجه h از f بیشتره پس درجه h از g هم بیشتره. پس میشه گفت
[tex]g(n) = \Omega (O(h))[/tex]
پس نتیجه میگیریم که :
[tex]g(n) = \Omega (O(f(n))[/tex]
(۱۰ شهریور ۱۳۹۲ ۰۳:۰۸ ق.ظ)mehdi1902 نوشته شده توسط: ببینید برای این که میگین چی رو با چی جمع کرده توی گزینه ۳، اینا مجموعه هستن دیگه. هر عضویش میشه انتخاب شه.ممنون از پاسختون
O(f(n)) مجموعه ای هستش که درجه اعضاش ببشتر از f هستن. حالا این توابع با هرچی که جمع بشن بازم درجشون بیشتر از f میمونه. یعنی میشه O(f(n)) ولی نمیتونه عضو teta باشه !
راجع به گزینه‌ی ۴ :
ببین میدونیم که
[tex]g(n) = \Omega (f(n))[/tex]
این یعنی چی ؟؟ یعنی g یه تابعی هستش که درجه ـش از f کمتره. حالا O(f(n)) چه تابعایی هستن ؟؟؟ تابعایی که درجه ـشون از f بیشتره. اسمشون رو میزاریم مثلا h.
چون میدونیم درجه h از f بیشتره پس درجه h از g هم بیشتره. پس میشه گفت
[tex]g(n) = \Omega (O(h))[/tex]
پس نتیجه میگیریم که :
[tex]g(n) = \Omega (O(f(n))[/tex]
ولی شما برداشت اشتباهی کردید شما می گید بیگ او تابع f به این معناست که شامل توابعی می شه که درجه(البته من تو مراجع چیزی به عنوان درجه ندیدم شاید منظورتون همون میزان رشد توابع است) انها بیشتر از f هست در حالی که بیگ او می گه توابعی رو شامل می شم که حد بالای رشد انها حداکثر f است یعنی نهایت به اندازه f رشد خواهند کرد اگه اشتباه می کنم لطفا بگید
(۱۰ شهریور ۱۳۹۲ ۰۱:۰۷ ق.ظ)aria نوشته شده توسط: در هر صورت من مشکلم اینجاست که مثلا گزینه ۳ چی رو با چی جمع کرده توی جواب ها از اونها به عنوان مجموعه یاد کرده یعنی حالتی مجموعه ای با اون رفتار شده
گزینه ۴ رو هم اگه می تونید تحلیل کنید
جواب تست رو هم پیوست کردم
گزینه ۱ درسته؛ طبق قضیه، جمع تعدادی متناهی عبارت عضو تتای مکس اونهاست؛ مشخصا f از همه توابع مجموعه اسمال اوی f بزرگتره؛
گزینه ۲ درسته؛
گزینه ۳ غلطه؛ شبیه گزینه یکه منتها اینجا هر سه تا عبارت مجموعه هستن که اگه به جای + علامت اشتراک باشه درست میشه؛
گزینه ۴ درسته؛ فرض شده f کران پایین g باشه؛ بنابراین رشد g از همه توابعی که f کران بالای اونها هست هم بزرگتره؛ یعنی g از همه اعضای بیگ اوی f بزرگتره؛ پس میشه گفت همه اعضای بیگ اوی f کران پایینی برای g هستن که به زبان ریاضی میشه [tex]g(n)\in\Omega (O(f(n)))[/tex]
(پیشنهاد میکنم به جای علامت مساوی که در گزینه های ۱ و ۲ و ۴ به اشتباه استفاده شده خودتون رو عادت بدید به علامت عضویت؛ مساوی فقط در گزینه ۳ معنی داره که هر سه تا مجموعه هستن)
(۱۰ شهریور ۱۳۹۲ ۰۱:۰۷ ب.ظ)Ghiasoddin نوشته شده توسط:ممنون از پاسختون(10 شهریور ۱۳۹۲ ۰۱:۰۷ ق.ظ)aria نوشته شده توسط: در هر صورت من مشکلم اینجاست که مثلا گزینه ۳ چی رو با چی جمع کرده توی جواب ها از اونها به عنوان مجموعه یاد کرده یعنی حالتی مجموعه ای با اون رفتار شده
گزینه ۴ رو هم اگه می تونید تحلیل کنید
جواب تست رو هم پیوست کردم
گزینه ۱ درسته؛ طبق قضیه، جمع تعدادی متناهی عبارت عضو تتای مکس اونهاست؛ مشخصا f از همه توابع مجموعه اسمال اوی f بزرگتره؛
گزینه ۲ درسته؛
گزینه ۳ غلطه؛ شبیه گزینه یکه منتها اینجا هر سه تا عبارت مجموعه هستن که اگه به جای + علامت اشتراک باشه درست میشه؛
گزینه ۴ درسته؛ فرض شده f کران پایین g باشه؛ بنابراین رشد g از همه توابعی که f کران بالای اونها هست هم بزرگتره؛ یعنی g از همه اعضای بیگ اوی f بزرگتره؛ پس میشه گفت همه اعضای بیگ اوی f کران پایینی برای g هستن که به زبان ریاضی میشه [tex]g(n)\in\Omega (O(f(n)))[/tex]
(پیشنهاد میکنم به جای علامت مساوی که در گزینه های ۱ و ۲ و ۴ به اشتباه استفاده شده خودتون رو عادت بدید به علامت عضویت؛ مساوی فقط در گزینه ۳ معنی داره که هر سه تا مجموعه هستن)
در مورد گزینه ۱ تفسیرتون کاملا درسته میدونستم گزینه ۲ و۴ به اشتباه از مساوی استفاده کرده ولی در مورد گزینه ۱ دقت نکردم واینکه اگر بیگ او هم بود در درستی این گزینه که تفاوتی نمی کرد چون نهایت رشدش اندازه f می شد
میشه در مورد گزینه ۳ بیشتر توضیح بدید توی جواب تستی که پیوست کردم نوشته امگای f شامل توابعی می شه که حد پایین انها f هست ورشد این توابع الزاما با f برابر نیست یعنی ممکنه رشدشون بیشتر از f باشه این مسئله برای بیگ او f هم برقراره دیگه
ودر اخر ایا میشه این جور مسائل رو منظورم گزینه ۳ هست رو با مثال زدن ورد گزینه حل کرد مقسمی این کارو کرده که متاسفانه جواب غلط زیاد داره حداقل توی این فصل ساختمان داده
بازم ممنوم
(۱۰ شهریور ۱۳۹۲ ۰۲:۳۶ ب.ظ)aria نوشته شده توسط: در مورد گزینه ۱ تفسیرتون کاملا درسته میدونستم گزینه ۲ و۴ به اشتباه از مساوی استفاده کرده ولی در مورد گزینه ۱ دقت نکردم واینکه اگر بیگ او هم بود در درستی این گزینه که تفاوتی نمی کرد چون نهایت رشدش اندازه f می شدبله، در گزینه ۱ بیگ او هم بود فرقی نمیکرد؛
میشه در مورد گزینه ۳ بیشتر توضیح بدید توی جواب تستی که پیوست کردم نوشته امگای f شامل توابعی می شه که حد پایین انها f هست ورشد این توابع الزاما با f برابر نیست یعنی ممکنه رشدشون بیشتر از f باشه این مسئله برای بیگ او f هم برقراره دیگه
ودر اخر ایا میشه این جور مسائل رو منظورم گزینه ۳ هست رو با مثال زدن ورد گزینه حل کرد مقسمی این کارو کرده که متاسفانه جواب غلط زیاد داره حداقل توی این فصل ساختمان داده
بازم ممنوم
در گزینه ۳ سمت چپ مساوی دو تا عبارت با هم جمع شدن که هر کدوم به جای اینکه یه تابع مشخص باشن، مجموعه ای از توابعن (مثلا بیگ اوی n یعنی مجموعه همه توابعی که درجه اونها حداکثر n هست که بیشمار تابع میشه)؛ تا جائیکه من یادمه جمع دو تا مجموعه بی معنیه؛ فقط یه قضیه داریم که قیافه این گزینه بهش شبیهه که تتای f اشتراک بیگ او و بیگ اومگای f هست؛
فکر میکنم گزینه های ۱ و ۳ رو یه جور دیگه باید تفسیر کرد که احتمالا منظور طراح همین بوده باشه (که باز هم صورت سوال به لحاظ گرامر ریاضی صحیح نیست)؛ گزینه ۳ رو اینطور بخونید: اگه هر عضو از بیگ اوی f با هر عضو از بیگ اومگای f جمع بشه حاصل عضو تتای f هست؛ که نمیتونه درست باشه؛ در اینجا چون گزینه داره یه "حالت کلی رو به صورت قانون" بیان میکنه همونطور که خودتون گفتید میتونید با یه مثال نقض ردش کنید (در صورت امکان)؛ مثلا f رو بگیرید n2، یک عضو از بیگ اوی f رو بگیرید n و عضوی از بیگ اومگای f رو بگیرید n3؛ حالا جمع n و n3 میشه تتای n3 نه n2؛
(۱۰ شهریور ۱۳۹۲ ۱۲:۲۸ ب.ظ)aria نوشته شده توسط: ممنون از پاسختوندرسته. شما درست میگین
ولی شما برداشت اشتباهی کردید شما می گید بیگ او تابع f به این معناست که شامل توابعی می شه که درجه(البته من تو مراجع چیزی به عنوان درجه ندیدم شاید منظورتون همون میزان رشد توابع است) انها بیشتر از f هست در حالی که بیگ او می گه توابعی رو شامل می شم که حد بالای رشد انها حداکثر f است یعنی نهایت به اندازه f رشد خواهند کرد اگه اشتباه می کنم لطفا بگید
من منظورم از درجه برای فهم راحت تر مسئله بود. اگه نه منظور اصلی همون رشد تابعه