پاورپوینت درمورد طراحي الگوريتم ها
نوع فایل : پاورپوینت ( Power Point ) قابل ویرایش
تعداد اسلاید ها : 27اسلاید
بخشی از اسلاید ها :
•پیچیدگی چندجمله ای
•پیچیدگی نمایی و فاکتوریل
Qاین الگوریتم ها برای مسائل با اندازه کوچک بد نیستند ولی با افزایش اندازه ورودی به شدت کند می شوند
•
•مساله کنترل ناپذیر
Qبرای مساله راه حلی با زمان چندجمله ای وجود ندارد
•مسائل رام نشدنی(Intractable)
Qاثبات می گردد که یافتن راه حل کارآمد غیر ممکن است مثلا یافتن کلیه مسیر های همیلتونی
•مسائل NP-Complete
Qمسائلی هستند که یافتن راه حل کارآمد برای آنها غیر ممکن نیست (ثابت نشده است رام نشدنی هستند) مانند کوله پشتی 0-1 و فروشنده دوره گرد و رنگ آمیزی گراف ها
•چند جمله ایP (Polynomial) : مسائل تصمیم گیری که در زمان چند جمله ای توسط الگوریتم قطعی(ماشین تورینگ قطعی) قابل حل می باشد
•چند جمله ای غیر قطعی NP(none-deterministic Polynomial): مسائل تصمیم گیری که برای آن ها کسی راه حل چندجمله ای نیافته است اما توسط الگوریتم غیر قطعی(ماشین تورینگ غیر قطعی) در زمان چند جمله ای قابل حل است P Í NP
•NP-Complete: مساله P، NP-Complete است اگر NP باشد و سایر مسائل NP را در زمان چند جمله ای بتوان به آن تبدیل کرد
•NP-Hard: مساله H، NP-Hard است اگر وفقط اگر یک مساله NP-Compelete ، L وجود داشته باشد که در زمان چند جمله ای قابل تبدیل به H باشد
