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

PowerPoint قابل ویرایش
11 صفحه
11900 تومان
119,000 ریال – خرید و دانلود

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

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت مسائل رام نشدنی قرار داده شده است

2-در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

اسلاید ۱ :

مقدمه

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

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

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

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

اسلاید ۲ :

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

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

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

اسلاید ۳ :

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

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

 

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

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

 

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

 

. . .

اسلاید ۴ :

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

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

 

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

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

اسلاید ۵ :

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

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

 

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

 

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

 

اسلاید ۶ :

نظریه NP

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

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

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

اسلاید ۷ :

کلاس (Polynomial) P

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

 

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

 

اسلاید ۸ :

کلاسNP (Nondeterministic Polynomial)

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

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

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

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

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

اسلاید ۹ :

خلاصه

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

 

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

 

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

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

 

 

 

 

مطالب فوق فقط متون اسلاید های ابتدایی پاورپوینت بوده اند . جهت دریافت کل ان ، لطفا خریداری نمایید .
PowerPoint قابل ویرایش - قیمت 11900 تومان در 11 صفحه
119,000 ریال – خرید و دانلود
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد