دانلود تحقیق P & NP Problems

اختصاصی از یارا فایل دانلود تحقیق P & NP Problems دانلود با لینک مستقیم و پرسرعت .

فرمت فایل : word(قابل ویرایش)

تعداد صفحات:16

فهرست مطالب:

نظریه پیچیدگی محاسباتی
کنترل ناپذیری
مسائلی برای الوریتم‌های زمان- چند جمله‌ای
مسائلی که کنترل ناپذیری آنها ثابت شده است
تعریف P :
تعریف NP
آیا NP=P می‌باشد؟
معرفی NP-Complete یا -NP کامل
بررسی ناکارآمد بودن زمانی
چرا حل مسائل NP-Complete مشکل است؟
روشهایی برای حل مسائل NP-Complete
به کار بردن یک روش حدسی:
حل کردن تقریبی مثاله به حل کردن دقیق آن:
الگورتیم های زمان توانی را بکار ببریم:
از خلاصه کردن استفاده کنیم:
مسائل NP شکل NP آسان NP معادل
تعریف NP مشکل
تعریف مسئله¬ی NP آسان
تعریف NP – معادل
نمونه مسأله:

نظریه پیچیدگی محاسباتی

نظریه ی پیچیدگی محاسباتی شاخه‌ای از علوم کامپیوتر و ریاضی که به بررسی دشواری حل مسائل به وسیله رایانه بصورت دقیق‌تر (بصورت الگوریتمی)‌ می پردازد، این نظریه بخضی از نظریه‌ی محاسباتی است که با سعاج مورد نیاز برای حل یک مسئله سر و کار دارد. عمومی ترین منابع زمان (چقدر زمان برای حل تمدن مساله لازم است و خضا (چقدر ناظم مورد نیاز است) می‌باشد. سایر منابع می‌تواند تعداد دیرسورهای موازی (در حالت پردازش موازی) باید به این نکته توجه داشت که نظریه‌ی پیچیدگی با نظریه‌ی قابل حل بودن متفاوت می باشد. این نظریه در مورد قابل حل بودن یک مسأله بدون توجه به منابع مورد نیاز آن، بحث می‌کند. بعد از این نظریه که بیان می کند کدام مسائل قابل حل می‌باشند و کدام مسائل غیرقابل حل، این سؤال به نظر طبیعی می‌رسد، درجه‌ی سختی مسأله چقدر است. نظریه‌ی پیچیدگی محاسبات در این زمینه می‌باشد. برای سادگی کار مسأله‌ها به کلاس‌هایی تقسیم می‌شوند بطوری مسألهژ های یک کسلاس از حیث زمان 1 فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس های پیچیدگی خوانده می‌شوند.

بعضی منابع دیگری که در این نظریه مورد بررسی قرار می گیرند مثل عدم تعین صرفاً جنبه‌ی صوری دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.

کنترل ناپذیری

زمانی یک مسئله در علم کامپیوتر کنترل ناپذیر ناحیه می شود که کامپیوتر به سختی بتواند آن را حل نماید (یعنی اینکه نتوان آن را با یک الگوریتم زمان جثه جمله‌ای برای یک مسئله، آن را از کنترل ناپذیری خارج می کند مثل الگوریتم brute-force برای مئسله ضرب ماتریس زنجیره‌ای، یک الگوریتم زمان، غیر چندجمله‌ای است. سه گروه کلی از مسائل کنترل ناپذیر وجود دارد:

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

جالب اینکه به نظر می‌رسد بسیاری از مسائل علم کامپیوتر علم کامپیوتر در گروه اول یا سوم قرار دارند. به هنگام تعیین زمان چند جمله‌ای الگوریتم بایستی توجه کافی به اندازه‌ی ورودی داشته باشیم.