دوشنبه، ۲ اسفند ۱۳۹۵   


دانشگاه تحصیلات تکمیلی علوم پایه زنجان

بلوار استاد یوسف ثبوتی، پلاک 444

صندوق پستی 1159-45195 زنجان 66731-45137 ایران

دورنگار: 33155142 -024

تلفن: 33151 -024


طراحی و برنامه نويسی توسط مركز كامپيوتر دانشگاه تحصيلات تكميلي علوم پايه زنجان

خانه>دانشکده علوم رایانه و فناوری اطلاعات>
دانشکده علوم رایانه و فناوری اطلاعات
 
 

سخنران مدعو

راه حل های Max-Min یا Min-Max برای مسائل الگوریتمی

مهدی خسرویان

تاریخ: ۱۳۹۵-۱۰-۱۲

زمان: ۱۷:۱۵

مکان: آمفی تئاتر ترکمان

خلاصه: ما کلاس خاصی از مسائل بهینه سازی را با عنوان بهینه سازی های Max-Min و Min-Max را بررسی می کنیم. مساله Π^' از مسشاله بهینه سازی مرجع Π ساخته می شود. در این تبدیل برای نمونه x از Π داده شده، ترتیب جزیی ≺^x روی مجموعه جواب F(x)تعریف می شود. در این مطالعه تمرکز ما بیشتر بر روی مسائل کلاسیک در علوم کامپیوتر نظری مثل ماکسیمم مجموعه مستقل، مینیمم رئوس پوششی و ... می باشد. معمولا پیدا کردن جواب دقیق برای نمونه های maxmin و minmax از این مسائل NP-hard می باشد. از آنجائیکه حل این مسائل بسیار مهم می باشد نیاز به راهکارهایی برای حل آنها در زمان سریع داریم. ما از راهکارهای همچون الگوریتم های تقریبی، الگوریتم هایی در حوزه پیچیدگی های پارامتری و حل این مسائل به صورت محدود شده برای حل این مسائل بهره می بریم.