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

دوره‌های دانشگاهی
20 جلسه

سرفصل‌ها

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

مدرس دوره
حمید ضرابی زاده

تحصیلات :

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

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

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

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