فراموشی رمز عبور
اگر رمز خود را فراموش کردید با نوشتن آدرس پست الکترونیک خود در قسمت زیر میتوانید رمز عبور جدید بسازید.


با شرکت در نظرسنجی، به ما در بهبود کیفیت درس‌های مکتب‌خونه کمک کنید.
از پیشنهاد شما سپاسگزاریم .
خطایی رخ داده است. لطفا دوباره امتحان کنید .
لطفاً منتظر بمانید...

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

معرفی درس

الگوریتم تقریبی در علوم رایانه و تحقیق عملیاتی، الگوریتمی برای پیداکردن راه‌حل‌های تقریبی برای مسائل بهینه‌سازی است. این الگوریتم‌ها اغلب برای حل تقریبی مسائل ان‌پی سخت (به انگلیسی: NP-hard) بکار می‌روند زیرا بسیاری از مسائل بهینه‌سازی ان‌پی سخت هستند (در واقع بررسی کردن درستی جواب اینگونه مسائل با حل کلی آنها معادل است) طبق نظریه پیچیدگی محاسباتی تا زمانیکه P ≠ NP، الگوریتم‌های کارامد با زمان چندجمله‌ای برای چنین مسائلی پیدا نخواهد شد مگر اینکه P = NP که چنین فرضی هم خیلی بعید است.

برخلاف الگوریتم جستجوی کاشف که راه‌حل‌هایی بهینه، اغلب بدون اثبات و بدون کران برای جواب خود هستند؛ الگوریتم‌های تقریبی راه حلهایی شبه بهینه همراه با ضریبی برای میزان تقریب جواب واقعی ارائه می‌دهند همچنین وجود جواب خود را در بازهٔ خطای اعلام شده تضمین می‌کنند. (مثلاً جواب آنها ۲ برابر جواب بهینه است) منتها جواب خود را در زمان چندجمله‌ای تولید می‌کنند.

الگوریتم‌های تقریبی برای مسائل P نیز استفاده می‌شوند ولی به ازای ورودی‌های بزرگ خوب عمل نمی‌کنند.

تحصیلات :

فوق دکتری: علوم کامپیوتر، دانشگاه کارلتون، ۲۰۰۹-۲۰۱۱.

دکتری: علوم کامپیوتر، دانشگاه واترلو، ۲۰۰۳-۲۰۰۸.

کارشناسی ارشد: مهندسی نرم افزار، دانشگاه صنعتی شریف، ۱۹۹۸-۲۰۰۰.

کارشناسی: مهندسی نرم افزار، دانشگاه صنعتی شریف، ۱۹۹۴-۱۹۹۸