بخشی از پاورپوینت
اسلاید 1 :
مقدمه
راه حلهای ارئه شده برای مسائل در حالت کلی غالبا به دو صورت ظاهر می شوند.
- الگوریتمهایی که پیچیدگی زمانی آنها حداکثر چند جمله ای می باشد.
- مسائلی که لگوریتمهای ارائه شده برای آنها از درجه نمایی می باشد.
دسته دوم در عمل کاربرد خاصی ندارند .
دانشمندان علوم کامپیوتر نشان داده اند که مسئله فروشنده دوره گرد و هزاران مساله دیگر هم ارز هستند .چرا که با داشتن الگوریتمی کار آمد برای یکی از آنها ، برای تمامی آنها الگوریتمی کار آمد خواهیم داشت .
اسلاید 2 :
مسائل رام نشدنی
مسائلی که نتوان برای آنها الگوریتمی با مرتبه زمانی چند جمله ای پیدا کرد ، مسائل رام نشدنی نامیده می شود .
الگوریتمهایی با مرتبه زمانی n! , 3n , 2n یا هر الگوریتمی که مرتبه زمانی آن غیر چند جمله ای باشد ( نمایی ) را مسائل رام نشدنی نامند .
اسلاید 3 :
مسائلی که الگوریتمهای زمانی چند جمله ای برای آنها پیدا شده است .
برای مرتب سازی الگوریتم O ( n Log n )
برای جستجو در یک آرایه مرتب ، یک الگوریتم O ( Log n )
برای ضرب ماتریسها یک الگوریتم O ( n 2.38 )
برای ضرب زنجیره ای ماتریسها O ( n3 )
. . .
اسلاید 4 :
مسائلی که رام نشدنی بودن آنها ثابت شده است .
مساله تعیین کلیه مدارهای هامیلتونی که در این مساله تعداد مدارها ( n-1)! است.
همه مسائلی که تا این تاریخ رام نشدنی بودن آنها ثابت شده است ، نبودن آنها در مجموعه NP نیز ثابت شده است .
تنها رام نشدنی بودن تعداد نسبتاً کمی از مسائل اثبات شده است .
اسلاید 5 :
مسائلی که رام نشدنی بودن آنها ثابت نشده است ولی تاکنون هیچ الگوریتم زمانی چند جمله ای برای آنها یافت نشده است .
مسئله کوله پشتی صفر و یک
مسئله فروشنده دوره گرد
مسئله حاصل جمع زیر مجموعه ها
اسلاید 6 :
نظریه NP
نخست برای ورود به دنیای بررسی مسائل از نظر نوع الگوریتمهای قابل ارائه برای حل آنها ، مسائل تصمیم گیری را تعریف می کنیم .
هر مسئله ای که جواب آن بلی یا خیر باشد مسئله تصمیم گیری است .
کلاسهای NP-hard , NP-complete , NP , P از مسائل ، همه در چارچوب مسائل تصمیم گیری تعریف و بررسی می شوند .
اسلاید 7 :
کلاس (Polynomial) P
مسائلی که برای حل آنها الگوریتم یا الگوریتمهایی با مرتبه زمانی چند جمله ای یافت شده است کلاس الگوریتمهای قطعی را تشکیل می دهند .
این کلاس را با P که مخفف Polynomial یا چند جمله ای می باشد ، نشان می دهند .
اسلاید 8 :
کلاسNP (Nondeterministic Polynomial)
برای مسائل کلاس NP باید کامپیوتر علاوه بر توانایی اجرای دستورهای معین وقطعی ، قادر باشد برخی دستورات نامعین را نیز اجرا کند .
برای مثال فرض کنید دستوری داشته باشیم که بخواهد از بین 100 شی یکی را انتخاب کند . قبل از اجرای چنین دستوری نمی توان پیش بینی کرد که دقیقا کدامیک از اشیا انتخاب خواهند شد !
الگوریتمهای نامعین علاوه بر دستورهایی که برای بیان الگوریتم معین وجود دارد ، باید دستورات دیگر را نیز اضافه کنند .
- معمولا دستورهای زیر به الگوریتم های معین اضافه می شوند تا الگوریتم به نامعین تبدیل شود :
- تابعی که یکی از عناصر مجموعه S را به دلخواه انتخاب کند .
- حدس انتخاب شده و مجموعه S ورودی این تابع می باشد . خروجی این تابع ، پایان موفق یا نا موفق عملیات الگوریتم را اعلام می کند(مرحله تصدیق)
در بیان یک الگوریتم نامعین لزومی ندارد از همه دستورها و تابع های ذکر شده استفاده شود .
اسلاید 9 :
خلاصه
مسائلی که نوشتن یک الگوریتم کارآمد برای آنها غیر ممکن است، مسائل رام نشدنی نامیده می شود .
مسائلی که نوشتن یک الگوریتم کارا ( چند جمله ای ) برای آنها ابداع نشده است ولی غیر ممکن بودن آن نیز هنوز به اثبات نرسیده است را مسائل NP کامل می گویند .
مسئله فروشنده دوره گرد ، مسئله nوزیر ، مسئله رنگ آمیزی گراف و مسئله کوله پشتی جزو مسائلی هستند که تا به حال نتوانسته اند الگوریتمی با مرتبه زمانی چند جمله ای برای آنها پیدا کنند .
الگوریتمهایی با مرتبه زمانی n! , 3 n , 2 n یا هر الگوریتمی که مرتبه زمانی آن غیر چند جمله ای باشد ( نمایی ) را مسائل رام نشدنی نامند .
