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