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

تست ۶۶ طراحی الگوریتم گرایش هوش مصنوعی سال ۸۳

ارسال:
  

atharrashno پرسیده:

تست ۶۶ طراحی الگوریتم گرایش هوش مصنوعی سال ۸۳

این سوا در مورد پیچیدگی بهترین الگوریم برای الگوریم داده شذه است که میشه ثابت کرد قطعا از درجه nlogk
است اما انچه که یاعث شبهناک بودنه گزینه ۱ و ۳ هست
حالت متوسط nlogk
یا همیشه از درجه nlogk است در مفهوم چه فرقی دارند

اقای مقسمی گزینه ۱ را زدند
اقای قلی زاده گزینه ۳ را زدند.
!!


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

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

۰
ارسال:
  

hadi_m پاسخ داده:

RE: طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

با سلام
اول از لحاظ مفهمی:
وقتی میگه حالت متوسط یعنی میتونه مرتبه یا هزینه ما بیشتر از این مقدار هم بشه اما وقتی میگه همیشه یعنی چه در در حالت بدترین و چه در حالت متوسط یا بهترین همیشه همین مقدار را باید هزینه کنیم.
و اما در ادامه ...
بگذارید اینجور توضیح بدم که فرض کنید این همان الگرویتم مرتب سازی سریع است .
توضیح: در مرتب سازی سریع ما تا زمانی که به ارایه های تک عضوی برسیم مراحل تقسیم و پارتیشن بندی را انجام میدهیم .
حال اینطور تصور کنید که این الگوریتم وقتی به ارایه هایی به طول [tex]\frac{N}{K}[/tex]
رسید دیگر پارتیشن بندی را متوقف کرده و کار تمام شده است .
محاسبه پیچدگی:
در این الگروریتم هر بار هزینه پارتیشن بندی را داریم [tex]O(n)[/tex]
اما عمق درخت از Lgn به Lgk کاهش پیدا میکند زیرا:
تعداد گره‌ها در برگها برابر با [tex]\frac{N}{K}[/tex] میباشد .(در مرتب سازی سریع تا ۱ پیش میرفتیم )و لذا داریم: :

[tex]\frac{N}{2^{h}}= \frac{N}{K} \Rightarrow h=log(k)[/tex]

و در نهایت همیشه مرتبه ان برابر است با‌ ::[tex]Nlog(k)[/tex]

نکته اخر بر سر اختلاف نظر بزرگان در حل این تست:
همانطور که میدانید کارایی مرتب سازی سریع به نحوه پارتیشن بندی بستگی دارد اگر پارتیشن بندی به طرز مناسبی صورت گیرد لذا مرتب سازی سریع همیشه nlgn است و همانطور که میدانید در بدترین حال از مرتبه ۲ است اما الگوریتمهایی وجود دارندکه با انتخاب عنصر محور مناسب جهت پارتیشن بندی (روش میانه سه و یا انتخاب تصادفی) همواره هزینه nlgn را دارند و لذا هزینه ان همیشه nlgn است (برای اثبات قضیه به کتاب Clrs مراجعه کنید.)
تمام ماجرا همین بود
موفق باشید.

۰
ارسال:
  

Sunshine Off پاسخ داده:

RE: طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

جواب این سوال گزینه ۱ میشه حالا چرا؟
nعنصر داریم که میخواهیم آنها رابهkمجموعه پارتیشن کنیم که همه عناصر مجموعه اول از همه عناصر مجموعه دوم،همه عناصرمجموعه دوم از همه عناصر مجموعه سوم و...کوچکترهستند.برای اینکار ابتدا میانه راپیداکرده که هزینه آنO(n وروی آنpivot میزنیم دراینصورت همه عناصر سمت چپ ازآن کوچکتر وهمه عناصرسمت راست ازآن بزرگترهستند(درواقع انکاردوتا مجموعه ساختیم)سپس دوباره همین اعمال را روی زیر آرایه‌ها انجام میدیمیعنی میانه هرزیر آرایه رابدست میاوریم وتا آخر...وقتی kتا مجموعه داریم باید log k بار آرایه رابشکنیم وچون هزینه هر سطرO(n پس در مجموع همیشه از مرتبهnlogkهست.امیدوارم متوجه شده باشید.Shy

۰
ارسال:
  

atharrashno پاسخ داده:

طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

خوب پس بزارید ببینیم من درست متوجه شدم یا نه:
درسته الگوریتم سریع در بدتریت حات درجهn^2 را داره اما باید دید طراح احتمال وقوع بدترین ورودی را در نظر داشته است با خیر اگر فرض طراح randomized _quick sort (یا هر الگوریتم انتخاب تصادفی میانه) باشد
باید گفت بدترین حالت چون رخ نمیدهد (یا با احتمال خیلی کم )پس همیشه از درجه nlog n میباشد
و در این سوال گزینه همیشه از درجه nlog k _با همون در نظر داشتن فرض بالا _انتخاب میشه.
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

atharrashno پاسخ داده:

طراحی الگوریم گرایش هوش مصنوعی سال ۸۳ سوال ۶۶

دوست متین من متوجه شده بودم و اصلش اینه که جواب را بدست اورده بودم اما نمی فهمیدم که همیشه از درجه nlogk با به طور متوسط از درجه nlog k چه فرقی دارند که با توضیحات دوستان اونم برطرف شد و به گزیه همیشه از درجه nlogk روی اوردم!
مشاهده‌ی وب‌سایت کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل و بررسی سوالات مدارمنطقی دکتری ۹۲ گرایش معماری nomad:D ۲۵ ۲۳,۹۳۸ ۲۰ بهمن ۱۴۰۲ ۱۰:۳۸ ق.ظ
آخرین ارسال: masoumeh97
  دانلود سوالات تخصصی گرایش فناوری اطلاعات آزمون دکتری ۹۱(کد ۲۳۵۸) Lonely Palm ۲ ۵,۸۶۰ ۲۶ دى ۱۴۰۲ ۰۲:۳۳ ب.ظ
آخرین ارسال: bijibuji
  گرایش های علوم کامپیوتر alisaaa ۴ ۳,۶۵۲ ۱۳ آذر ۱۴۰۲ ۰۴:۲۷ ب.ظ
آخرین ارسال: hashemhamidi
  [دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی هاتف ۳۳ ۴۰,۸۰۸ ۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ
آخرین ارسال: solmaz58
  درخواست کتاب یا جزوه برای ارشد و دکتری هوش مصنوعی H.Mohammadi ۱ ۱,۲۹۸ ۰۴ تیر ۱۴۰۲ ۰۱:۳۷ ب.ظ
آخرین ارسال: solmaz58
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۹ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  دانشگاه صنعتی اصفهان یا گرایش معماری امیرکبیر sima84 ۰ ۱,۷۶۶ ۱۶ شهریور ۱۴۰۰ ۰۳:۳۷ ب.ظ
آخرین ارسال: sima84
  منابع آزمون دکتری گرایش تجارت الکترونیک wskf ۳ ۵,۹۷۵ ۳۱ اردیبهشت ۱۴۰۰ ۱۰:۱۳ ب.ظ
آخرین ارسال: Ametrine
  طراحی ui/ux kimiya1234 ۲ ۲,۰۱۲ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۶ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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