زمان کنونی: ۲۶ آذر ۱۳۹۶, ۰۵:۲۸ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)
ارسال:
  

rad.bahar پرسیده:

تست ۴۴ طراحی الگوریتم آی تی ۹۰

چرا گزاره ضمیمه شده غلط است
زمانی g(n) = o(f(n که بر طبق تعریف ای بزرگ حداقل یک c باشد که g(n)<= c f(n پس جال که
g(n) <> o(f(n یعتی به ازای همه c‌ها g(n)> c f(n
بر ظبق تعریفی که از g(n از مرتبه امکای f(n داریم به ازای حداقل یک c
g(n)= c f(n یا g(n)> c f(n باشد g صورت سوال مطایق با شرایظ ذکر شذه در مقدم گزاره شرطی و توضیحات ذکر شده در بالا به ازای همه c‌ها g(n)> c f(n است پس یعنی حداقل یک c با شرایط مورد نظر امکا وجود دارد یعنی g(n از مرتبه امکای f(n
با استدلال بالا کزاره درست به نظر می رسد چرا گزاره ضمیمه شده غلط است
خواهشا جواب بدید


فایل‌(های) پیوست شده

مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

موج پاسخ داده:

RE: تست ۴۴ it90

به شکل ضمیمه توجه کنید
این دو تابع هیچ کرانی برای هم نیستند به ازای هیچ c


فایل‌(های) پیوست شده

۰
ارسال:
  

zzsnowdrop پاسخ داده:

تست ۴۴ it90

g(n)=O f(n
یعنی (g(n ‌کوچیکتر مساوی هست با (c f(n
حالا وقتی این میشه نامساوی یعنی (g(n بزرگتر است از( c f(n
دقت کن فقط بزرگتر نه بزرگتر مساوی

حالا داریم توی قسمت نتیجه گیری از رابطه که( g(n)>=cf(n
یعنی (g(n بزرگتر مساوی هست با( cf(n
و در حالی که از قبلی نتیجه گرفتیم شامل مساوی نمیشه

ارسال:
  

rad.bahar پاسخ داده:

RE: تست ۴۴ it90

(۰۲ بهمن ۱۳۹۰ ۱۲:۳۴ ب.ظ)zzsnowdrop نوشته شده توسط:  g(n)=O f(n
یعنی (g(n ‌کوچیکتر مساوی هست با (c f(n
حالا وقتی این میشه نامساوی یعنی (g(n بزرگتر است از( c f(n
دقت کن فقط بزرگتر نه بزرگتر مساوی

حالا داریم توی قسمت نتیجه گیری از رابطه که( g(n)>=cf(n
یعنی (g(n بزرگتر مساوی هست با( cf(n
و در حالی که از قبلی نتیجه گرفتیم شامل مساوی نمیشه
با تشکر از جوابتان
قبول دارم که (g(n بزرگتر است از( c f(n نه بزرگتر مساوی
ولی در تعریف امگا داریم که اگر g(n از مرتبه امگای f(n باشد انگاه( g(n)=cf(n
یا
( g(n)>cf(n
درست است که g با شرایط ذکر شده در سوال مساوی cf(n نیست ولی حداقل به ازای یک c
( g(n)>cf(n که هست
لطفا اگر تعریف امکا را اشتباه فهمیدم راهنمایی‌ام کنید
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

si.mozhgan پاسخ داده:

تست ۴۴ it90

ممکنه g نموداری نوسانی داشته باشه . مثل سینوس یا کسینوس.

ارسال:
  

rad.bahar پاسخ داده:

RE: تست ۴۴ it90

(۰۲ بهمن ۱۳۹۰ ۰۹:۵۴ ب.ظ)si.mozhgan نوشته شده توسط:  ممکنه g نموداری نوسانی داشته باشه . مثل سینوس یا کسینوس.

ممنون از جوابتان ولی متوجه نشدم حرفی که زدید با حرفهایی که من زدم جه ارتباطی داره
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Mohammad-A پاسخ داده:

تست ۴۴ it90

این مورد تناوب که دلیل منطقی هست اما دلیل بزرگ‌مساوی یا کوچکتر مساوی هم فکر میکنم می‌تونه مطرح باشه... درست نیست؟

۰
ارسال:
  

amir1369 پاسخ داده:

تست ۴۴ it90

همینطور که گفتن این تابع روی توابعی‌مثل توابع sin‌درست نیست. حرف شما درست هستش و در مواردی برای نمادهای امگا و بیگ او این رابطه صدق میکنه اما لزما با هم ارتباطی ندارن.
حالتی رو تصور کنید که ما مجموعه ای به اسم مثلا A داریم و مجموعه‌ی دیگه ای هست که زیرمجموعه‌ی اونه که میتونه شامل تمام اعضای a بشه و هم میتونه شامل اعضای a بدون اعضای مرزی اون باشه.
دراین صورت من الزاما نمیتونم بگم که این دو مجموعه با هم برابر هستن.
در هر صورت شاید منطق یاد گیری من درمورد این سوالا با شما تفاوت داشته باشه.اما من ازین نمونه‌ها دیگه خیلی حل کردم

بازم اگه خواستید اونو در حالتی که f(n)=|n^2 sin n| و g(n)=n باشه حل کنید
اما برایاین نمونه سوالا دانستن همون منطق >= و <= برای امگا و بیگ او
و > و < برای اسمال او و امگا کوچیک کفایت میکنه و با کمی دقت میشه تشخیص داد



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پاسخنامه تشریحی طراحی الگوریتم موسسه ماهان برای درس طراحی الگوریتم کنکور ۹۱ مهندسی MSsoftware ۸ ۶,۲۴۹ ۰۴ بهمن ۱۳۹۱ ۱۲:۰۲ ق.ظ
آخرین ارسال: fa_karoon
  تست ۳۸ طراحی الگوریتم سال ۸۵ پشتکار ۱۰ ۲,۹۰۱ ۲۹ دى ۱۳۹۱ ۰۹:۲۴ ب.ظ
آخرین ارسال: csharpisatechnology
  تست ۴۰ طراحی الگوریتم نرم افزار ۸۶ reyhaneh64 ۲ ۱,۶۳۸ ۲۹ دى ۱۳۹۱ ۰۲:۱۲ ب.ظ
آخرین ارسال: csharpisatechnology
  بررسی سوالات طراحی الگوریتم ۹۱ مهندسی کامپیوتر -گرایش هوش fatima1537 ۸۶ ۳۰,۹۵۱ ۲۰ اسفند ۱۳۹۰ ۰۹:۴۰ ب.ظ
آخرین ارسال: anyone
  تست (مرتبه اجرایی ) طراحی الگوریتم کنکور ۹۱ vijay ۷ ۳,۲۴۶ ۱۵ اسفند ۱۳۹۰ ۰۵:۳۴ ب.ظ
آخرین ارسال: لهمشد
  بررسی سوالات طراحی الگوریتم ۹۱ فناوری اطلاعات uniquegirl ۲۸ ۸,۰۹۶ ۰۶ اسفند ۱۳۹۰ ۱۱:۲۶ ب.ظ
آخرین ارسال: rotbe
  تست (گراف) طراحی الگوریتم آی تی کنکور ۹۱ vijay ۴ ۲,۷۳۵ ۰۱ اسفند ۱۳۹۰ ۰۶:۴۰ ق.ظ
آخرین ارسال: MSZ
  تست مرتبه اجرایی طراحی الگوریتم کنکور ۹۱ vijay ۲ ۲,۴۵۶ ۳۰ بهمن ۱۳۹۰ ۰۱:۵۴ ب.ظ
آخرین ارسال: arixooo
  تست ۳۲ طراحی الگوریتم سال ۹۰ Anahita.R ۳ ۲,۱۱۰ ۲۶ بهمن ۱۳۹۰ ۱۱:۳۶ ق.ظ
آخرین ارسال: atharrashno
  تست (درخت) طراحی الگوریتم آی تی سال ۸۸ netsupport ۲ ۱,۵۵۲ ۲۴ بهمن ۱۳۹۰ ۰۶:۳۳ ب.ظ
آخرین ارسال: homa

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close