لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت مسائل رام نشدني توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت مسائل رام نشدني قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

مقدمه

qراه حلهای ارئه شده برای مسائل در حالت کلی غالبا به دو صورت ظاهر می شوند.

  1. الگوریتمهایی که پیچیدگی زمانی آنها حداکثر چند جمله ای می باشد.
  2. مسائلی که لگوریتمهای ارائه شده برای آنها از درجه نمایی می باشد.

üدسته دوم در عمل کاربرد خاصی ندارند .

qدانشمندان علوم کامپیوتر نشان داده اند که مسئله فروشنده دوره گرد و هزاران مساله دیگر هم ارز هستند .چرا که با داشتن الگوریتمی کار آمد برای یکی از آنها ، برای تمامی آنها الگوریتمی کار آمد خواهیم داشت .

اسلاید ۲ :

مسائل رام نشدنی

qمسائلی که نتوان برای آنها الگوریتمی با مرتبه زمانی چند جمله ای پیدا کرد ، مسائل رام نشدنی نامیده می شود .

qالگوریتمهایی با مرتبه زمانی n! , 3n , 2n  یا هر الگوریتمی که مرتبه زمانی آن غیر چند جمله ای باشد ( نمایی ) را مسائل رام نشدنی نامند .

اسلاید ۳ :

مسائلی که الگوریتمهای زمانی چند جمله ای برای آنها پیدا شده است .

Øبرای مرتب سازی الگوریتم O ( n Log n )

Ø

Øبرای جستجو در یک آرایه مرتب ، یک الگوریتم O ( Log n )

Øبرای ضرب ماتریسها یک الگوریتم O ( n 2.38 )

Ø

Øبرای ضرب زنجیره ای ماتریسها O ( n3 )

Ø

Ø. . .

اسلاید ۴ :

مسائلی که رام نشدنی بودن آنها ثابت شده است .

Øمساله تعیین کلیه مدارهای هامیلتونی که در این مساله تعداد مدارها ( n-1)!  است.

ü

üهمه مسائلی که تا این تاریخ رام نشدنی بودن آنها ثابت شده است ، نبودن آنها در مجموعه NP  نیز ثابت شده است .

üتنها رام نشدنی بودن تعداد نسبتاً کمی از مسائل اثبات شده است .

اسلاید ۵ :

مسائلی که رام نشدنی بودن آنها ثابت نشده است ولی تاکنون هیچ الگوریتم زمانی چند جمله ای برای آنها یافت نشده است .

Øمسئله کوله پشتی صفر و یک

Ø

Øمسئله فروشنده دوره گرد

Ø

Øمسئله حاصل جمع زیر مجموعه ها

Ø

اسلاید ۶ :

نظریه NP

 نخست برای ورود به دنیای بررسی مسائل از نظر نوع الگوریتمهای قابل ارائه برای حل آنها ، مسائل تصمیم گیری را تعریف می کنیم .

qهر مسئله ای که جواب آن بلی یا خیر باشد مسئله تصمیم گیری است .

qکلاسهای NP-hard , NP-complete , NP , P از مسائل ، همه در چارچوب مسائل تصمیم گیری تعریف و بررسی می شوند .

اسلاید ۷ :

کلاس (Polynomial) P

qمسائلی که برای حل آنها الگوریتم یا الگوریتمهایی با مرتبه زمانی چند جمله ای یافت شده است کلاس الگوریتمهای قطعی را تشکیل می دهند .

q

qاین کلاس را با P که مخفف Polynomial  یا چند جمله ای می باشد ، نشان می دهند .

q

اسلاید ۸ :

کلاسNP (Nondeterministic Polynomial)

        برای مسائل کلاس NP باید کامپیوتر علاوه بر توانایی اجرای دستورهای معین وقطعی ، قادر باشد برخی دستورات نامعین را نیز اجرا کند .

        برای مثال فرض کنید دستوری داشته باشیم که بخواهد از بین ۱۰۰ شی یکی را انتخاب کند . قبل از اجرای چنین دستوری نمی توان پیش بینی کرد که دقیقا کدامیک از اشیا انتخاب خواهند شد !

qالگوریتمهای نامعین علاوه بر دستورهایی که برای بیان الگوریتم معین وجود دارد ، باید دستورات دیگر را نیز اضافه کنند .

  • معمولا دستورهای زیر به الگوریتم های معین اضافه می شوند تا الگوریتم به نامعین تبدیل شود :
  1. تابعی که یکی از عناصر مجموعه S را به دلخواه انتخاب کند .
  2. حدس انتخاب شده و مجموعه S ورودی این تابع می باشد . خروجی این تابع ، پایان موفق یا نا موفق عملیات الگوریتم را اعلام می کند(مرحله تصدیق)

üدر بیان یک الگوریتم نامعین لزومی ندارد از همه دستورها و تابع های ذکر شده استفاده شود .

اسلاید ۹ :

خلاصه

qمسائلی که نوشتن یک الگوریتم کارآمد برای آنها غیر ممکن است، مسائل رام نشدنی نامیده می شود .

q

qمسائلی که نوشتن یک الگوریتم کارا ( چند جمله ای ) برای آنها ابداع نشده است ولی غیر ممکن بودن آن نیز هنوز به اثبات نرسیده است را مسائل NP کامل می گویند .

q

qمسئله فروشنده دوره گرد ، مسئله nوزیر ، مسئله رنگ آمیزی گراف و مسئله کوله پشتی جزو مسائلی هستند که تا به حال نتوانسته اند الگوریتمی با مرتبه زمانی چند جمله ای برای آنها پیدا کنند .

qالگوریتمهایی با مرتبه زمانی n! , 3 n , 2 n  یا هر الگوریتمی که مرتبه زمانی آن غیر چند جمله ای باشد ( نمایی ) را مسائل رام نشدنی نامند .

q

q