بالا
لامپ رشد گیاه

 دانلود نمونه سوالات کارشناسی ارشد پیام نور با پاسخنامه

 دانلود نمونه سوالات فراگیر پیام نور

 فروشگاه پایان نامه و مقاله


 تایپ متن و مقاله و پایان نامه





 دانلود نمونه سوالات نیمسال دوم 93-94 پیام نور

 دانلود نمونه سوالات آزمونهای مختلف فراگیر پیام نور

نمایش نتایج: از شماره 1 تا 2 از مجموع 2

موضوع: الگوریتم‌های تقریبی

  1. #1
    negar92 آواتار ها
    • 2,687
    • 2,576

    عنوان کاربری
    باز نشسته بخش زبان و ادبیات انگلیسی
    تاریخ عضویت
    Jan 2012
    شغل , تخصص
    دانشجو مترجمی زبان انگلیسی
    رشته تحصیلی
    مترجمی زبان انگلیسی
    راه های ارتباطی
    تشکر ها
    3,653
    پست های وبلاگ
    24

    پیش فرض الگوریتم‌های تقریبی

    الگوریتم‌های تقریبی



    از ویکی‌پدیا، دانشنامهٔ آزاد

    پرش به: ناوبری، جستجو
    در علوم کامپیوتر الگوریتم های تقریبی، الگوریتمهایی برای پیداکردن راه حل های تقریبی برای مسائل بهینه سازی هستند.این الگوریتم ها اغلب برای حل تقریبی مسائل ان پی-سخت (NP-hard) بکار می‌روند زیرا بسیاری از مسائل بهینه سازی ان پی-سخت هستند ( در واقع بررسی کردن درستی جواب اینگونه مسائل با حل کلی آنها معادل است ) طبق تئوری پیچیدگی محاسباتی (Computational complexity theory) تا زمانیکه ، الگوریتم‌های کارامد با زمان چند جمله ای برای چنین مسائلی پیدا نخواهد شد مگر اینکه P=NP که چنین فرضی هم خیلی بعید است .
    برخلاف روش‌های مکاشفه ای (Heuristics) که راه حلهایی بهینه، اغلب بدون اثبات و بدون کران برای جواب خود هستند؛ الگوریتم‌های تقریبی راه حلهایی شبه بهینه همراه با ضریبی برای میزان تقریب جواب واقعی ارائه می‌دهند همچنین وجود جواب خود را در بازهٔ خطای اعلام شده تضمین می‌کنند .( مثلا جواب آنها ۲ برابر جواب بهینه است) منتها جواب خود را در زمان چندجمله‌ای تولید می‌کنند
    الگوریتم‌های تقریبی برای مسائل P نیز استفاده می‌شوند ولی به ازای ورودی‌های بزرگ خوب عمل نمی‌کنند.
    یکی از مثالهای معروف برای الگوریتم‌های تقریبی، مسئله پوشش راسی (vertex cover) در گراف است : پیدا کردن یال پوشش داده نشده و اضافه کردن هر دو رأس آن به مجموعه پوشش رأسی تا زمانی که هیچ یال پوشش نیافته نماند . واضح است که مجموعه جوابهای این الگوریتم دو برابر جوابهای بهینه یعنی مجموعه کمترین رأس‌ها برای پوشش دادن همه یالها در یک گراف است؛ پس ضریب ثابت این الگوریتم ۲ است .
    الگوریتم‌های تقریبی موجود برای مسائل ان پی-سخت با هم تفاوت بسیاری دارند؛ مثلاً مسئله بسته بندی(bin packing problem ) را می‌توان به ازای هر ضریب بزرگتر از یک تقریب زد ، (اگر بتوانیم الگوریتمی تقریبی با ضریب یک برای چنین مسائلی ارائه دهیم P=NP می‌شود) به این خانواده از مسائل PTAS می‌گویند؛ درحالیکه ثابت شده است که برای برخی مسائل دیگر هیچ الگوریتم تقریبی ای یافت نمی‌شود مگر آنکه P=NP شود مانند مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) (maximum clique problem)
    مسائل ان پی-سخت را می‌توان با دستورکارهای خطی (integer programs) (مسائل برنامه ریزی خطی ای که های صحیح دارند ) متناظر کرد و در نتیجه آنها را در زمانهای نمایی حل کرد (مسائل IP در مرتبه زمانی نمایی حل می‌شوند )
    تضمین کارایی الگوریتم‌های تقریبی

    می توانیم برای برخی از الگوریتم‌های تقریبی، خصوصیاتی را اثبات کنیم مثلاً برای الگوریتمهای تقریبی ثابت شده است که تقریب بیشتر ( و یا کمتر ) از برابر جواب بهینه نخواهد بود :

    ضریب را ضریب تضمین کارایی نسبی می‌گویند . هر الگوریتم تقریبی ای تضمین کارایی مطلق و یا کران خطای دارد اگر:


    به طور مشابه نسبت کارایی مطلق الگوریتم های تقریبی :

    ( یک نمونه از مسئله و تضمین کارایی روی است .)
    در واقع بزرگترین کران نسبت تقریب روی همه نمونه‌های مسئله است . همچنین نسبت کارایی مجانبی :


    طــــروات زندگـــی در جریان یادگیری است
    ذهن های بسته بوی مـــــرگ میدهند...

    http://up.pnu-club.com/images/vce8ofsvkn51mo3s63t.jpg

  2. # ADS
    نشان دهنده تبلیغات
    تاریخ عضویت
    -
    محل سکونت
    -
    ارسال ها
    -

     دانلود نمونه سوالات نیمسال دوم 93-94 پیام نور با پاسخنامه تستی و تشریحی
     

  3. #2
    negar92 آواتار ها
    • 2,687
    • 2,576

    عنوان کاربری
    باز نشسته بخش زبان و ادبیات انگلیسی
    تاریخ عضویت
    Jan 2012
    شغل , تخصص
    دانشجو مترجمی زبان انگلیسی
    رشته تحصیلی
    مترجمی زبان انگلیسی
    راه های ارتباطی
    تشکر ها
    3,653
    پست های وبلاگ
    24


    طــــروات زندگـــی در جریان یادگیری است
    ذهن های بسته بوی مـــــرگ میدهند...

    http://up.pnu-club.com/images/vce8ofsvkn51mo3s63t.jpg

برچسب برای این موضوع

مجوز های ارسال و ویرایش

  • شما نمی توانید موضوع جدید ارسال کنید
  • شما نمی توانید به پست ها پاسخ دهید
  • شما نمی توانید فایل پیوست ضمیمه کنید
  • شما نمی توانید پست های خود را ویرایش کنید
  •