پاورپوینت مسائل رام نشدنی
توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد
پاورپوینت مسائل رام نشدنی دارای ۱۱ اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است
فایل پاور پوینت پاورپوینت مسائل رام نشدنی کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه و مراکز دولتی می باشد.
لطفا به نکات زیر در هنگام خرید
دانلود پاورپوینت مسائل رام نشدنی
توجه فرمایید.
۱-در این مطلب، متن اسلاید های اولیه
دانلود پاورپوینت مسائل رام نشدنی
قرار داده شده است
۲-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید
۳-پس از پرداخت هزینه ، حداکثر طی ۱۲ ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد
۴-در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد
۵-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است
بخشی از متن پاورپوینت مسائل رام نشدنی :
اسلاید ۱ :
مقدمه
qراه حلهای ارئه شده برای مسائل در حالت کلی غالبا به دو صورت ظاهر می شوند.
- الگوریتمهایی که پیچیدگی زمانی آنها حداکثر چند جمله ای می باشد.
- مسائلی که لگوریتمهای ارائه شده برای آنها از درجه نمایی می باشد.
üدسته دوم در عمل کاربرد خاصی ندارند .
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الگوریتمهای نامعین علاوه بر دستورهایی که برای بیان الگوریتم معین وجود دارد ، باید دستورات دیگر را نیز اضافه کنند .
- معمولا دستورهای زیر به الگوریتم های معین اضافه می شوند تا الگوریتم به نامعین تبدیل شود :
- تابعی که یکی از عناصر مجموعه S را به دلخواه انتخاب کند .
- حدس انتخاب شده و مجموعه S ورودی این تابع می باشد . خروجی این تابع ، پایان موفق یا نا موفق عملیات الگوریتم را اعلام می کند(مرحله تصدیق)
üدر بیان یک الگوریتم نامعین لزومی ندارد از همه دستورها و تابع های ذکر شده استفاده شود .
اسلاید ۹ :
خلاصه
qمسائلی که نوشتن یک الگوریتم کارآمد برای آنها غیر ممکن است، مسائل رام نشدنی نامیده می شود .
q
qمسائلی که نوشتن یک الگوریتم کارا ( چند جمله ای ) برای آنها ابداع نشده است ولی غیر ممکن بودن آن نیز هنوز به اثبات نرسیده است را مسائل NP کامل می گویند .
q
qمسئله فروشنده دوره گرد ، مسئله nوزیر ، مسئله رنگ آمیزی گراف و مسئله کوله پشتی جزو مسائلی هستند که تا به حال نتوانسته اند الگوریتمی با مرتبه زمانی چند جمله ای برای آنها پیدا کنند .
qالگوریتمهایی با مرتبه زمانی n! , 3 n , 2 n یا هر الگوریتمی که مرتبه زمانی آن غیر چند جمله ای باشد ( نمایی ) را مسائل رام نشدنی نامند .
q
q
- در صورتی که به هر دلیلی موفق به دانلود فایل مورد نظر نشدید با ما تماس بگیرید.