دانلود پاورپوینت مسائل رام نشدني

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