فیلم آموزش کلاس درس الگوریتم تقریبی - بخش دوم

فیلم آموزش کلاس درس الگوریتم تقریبی – بخش دوم

سلام و عرض ادب خدمت دوستان و همراهان همیشگی وب سایت آموزش برنامه نویسی سورس باران. در این مطلب فیلم آموزش کلاس درس الگوریتم تقریبی – بخش دوم رو برای شما جهت دانلود قرار داده ایم. این دوره از کلاس درس دکتر حمید ضرابی زاده در دانشگاه صنعتی شریف ضبط شده است و توضیحات بیشتر آن در ادامه مطلب موجود می باشد. لطفا با ما همراه باشید…

فیلم آموزش کلاس درس الگوریتم تقریبی – بخش دوم

  • آموزش درخت اشتاینر در الگوریتم تقریبی
  • آموزش برش بیشینه (max cut) در الگورتیم تقریبی
  • آموزش متصل کردن راس های مهم یک گراف با کمترین هزینه در الگوریتم تقریبی
  • آموزش گراف های وزن دار متریک در الگوریتم تقریبی
  • توضیح دو الگوریتم تقریبی برای مسئله ست کاور در الگوریتم تقریبی
  • آموزش خوشه بندی در الگوریتم تقریبی
  • آموزش قطر نقاط در فضای هندسی در الگوریتم تقریبی

نکته!!! لطفا توجه داشته باشید که این فیلم در خود کلاس ضبط شده است.

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

الگوریتم تقریبی چیست؟

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

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

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

بسیاری از مسائل بهینه‌سازی در ریاضیات، علوم کامپیوتر، و مهندسی ان‌پی-سخت هستند و بنابراین به دست‌ آوردن جواب‌های بهینه برای این مسائل در زمان چندجمله‌ای غیرمحتمل است. الگوریتم‌های تقریبی این امکان را فراهم می‌آورند که جواب‌هایی نزدیک به جواب‌ بهینه با ضریب تقریب قابل اثبات برای این دسته از مسائل به دست آورد. هدف این درس، آشنایی با مفاهیم و تکنیک‌های متداول در طراحی الگوریتم‌های تقریبی حول محور مسائل بنیادی در بهینه‌سازی ترکیبیاتی، و نیز بررسی روش‌های اثبات سختی تقریب برخی از این مسائل است. یکی از مثال‌های معروف برای الگوریتم‌های تقریبی، مسئله پوشش راسی (به انگلیسی: vertex cover) در گراف است: پیدا کردن یال پوشش داده نشده و اضافه کردن هر دو رأس آن به مجموعه پوشش رأسی تا زمانی که هیچ یال پوشش نیافته نماند.

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

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

واضح است که مجموعه جوابهای این الگوریتم دو برابر جواب‌های بهینه یعنی مجموعه کمترین رأس‌ها برای پوشش دادن همه یال‌ها در یک گراف است؛ پس ضریب ثابت این الگوریتم ۲ است. الگوریتم‌های تقریبی موجود برای مسائل ان پی-سخت با هم تفاوت بسیاری دارند؛ مثلاً مسئله بسته‌بندی (به انگلیسی: bin packing problem) را می‌توان به ازای هر ضریب بزرگتر از یک تقریب زد، (اگر بتوانیم الگوریتمی تقریبی با ضریب یک برای چنین مسائلی ارائه دهیم P = NP می‌شود) به این خانواده از مسائل Polynomial time approximation scheme می‌گویند؛ درحالیکه ثابت شده است که برای برخی مسائل دیگر هیچ الگوریتم تقریبی‌ای یافت نمی‌شود مگر آنکه P=NP شود مانند مسئله بزرگترین خوشه (به انگلیسی: maximum clique problem) (پیدا کردن بزرگترین زیرگراف کامل) مسائل ان پی-سخت را می‌توان با برنامه‌ریزی خطی (مسائل برنامه‌ریزی خطی‌ای که x i {\displaystyle x_{i}} x_iهای صحیح دارند) متناظر کرد و در نتیجه آنها را در زمانهای نمایی حل کرد. (مسائل IP در مرتبه زمانی نمایی حل می‌شوند)

شاید برایتان جذاب باشد: آموزش برنامه نویسی برای صفرکیلومترها

دمو دوره (جهت اجرا آنلاین دمو، فلش پلیر نصب نمایید) “”لینک دانلود دمو””

 

لیست جلسات قبل دوره الگوریتم تقریبی

  1. فیلم آموزش کلاس درس الگوریتم تقریبی – بخش اول
  2. فیلم آموزش کلاس درس الگوریتم تقریبی – بخش دوم
  3. فیلم آموزش کلاس درس الگوریتم تقریبی – بخش سوم
  4. فیلم آموزش کلاس درس الگوریتم تقریبی – بخش چهارم
  5. فیلم آموزش کلاس درس الگوریتم تقریبی – بخش پنجم

معرفی مدرس حمید ضرابی زاده

تحصیلات :

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

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

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

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

ایمیل : zarrabi@sharif.edu

5/5 - (1 امتیاز)

راستی! برای دریافت مطالب جدید در کانال تلگرام یا پیج اینستاگرام سورس باران عضو شوید.

پکیج حرفه ای فیلم های آموزشی برنامه نویسی به زبان فارسی
دانلود با لینک مستقیم

دسته بندی موضوعات

آخرین محصولات فروشگاه

مشاهده همه

نظرات

بازخوردهای خود را برای ما ارسال کنید

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