تحقیق موضوع اعداد p

لینک دانلود خرید پایین توضیحات

دسته بندی : وورد

نوع :  .doc ( قابل ویرایش اماده پرینت )

تعداد : 3 صفحه

---

 قسمتی متن : 

ارتباط بین کلاس پیچیدگی "P NP" یکی مسائل حل نشده علوم رایانه نظری عنوان مهمترین مسئله زمینه مطرح گردیده است.

سوال P=NP؟ واقع پرسش مطرح نماید که: اگر همیشه سادگی بتوان صحت یک راه‌حل بررسی کرد، ایا پیدا کردن راه‌حل می‌تواند سادگی باشد؟ ( زمان چندجمله‌ای جواب رسید. )

به عنوان مثال مسئله جمع اعضای زیرمجموعه نظر بگیرید. یک مثال مسئله‌ای تحقیق درستی راه حل ساده است، اما باور ( اما اثبات نشده ) محاسبه جواب مشکل است. فرض کنید یک مجموعه عداد صحیح داده شده است، ایا یک زیر مجموعه ناتهی وجود دارد مجموع اعضای ۰ شود؟ عنوان مثال،ایا زیر مجموعه‌ای مجموعه { ۲-، ۳-، ۱۵، ۱۴، ۷، ۱۰- } وجود دارد مجموع اعضای صفر شود؟ پاسخ مثبت زیرا زیرمجموعه { ۲-، ۳-، ۱۵، ۱۰- } وجود دارد شرط صدق کند تحقیق جواب درست خیر تنها انجام سه عمل جمع امکان پذیر است. اما پیدا کردن مجموعه اغاز کار، کمی وقت گیر است. اطلاعاتی تحقیق پاسخ مثبت دست سوال مورد نیاز است، یک Certificate گفته شود. اختیار داشتن اطلاعات درست، تحقیق درست بودن پاسخ مسئله ما، زمان چندجمله‌ای امکان پذیر است. بنابر این، مثال کلاس NP قرار گیرد.

پاسخ پرسش P=NP مشخص خواهد کرد ایا راه حل مسائلی مانند جمع اعضای زیرمجموعه سادگی تحقیق درستی پاسخ هاست خیر. صورتی ثابت شود P≠NP، انگاه توان نتیجه گرفت بعضی مسائل وجود دارند صورت ذاتی، یافتن پاسخ انها، "سخت تر" تحقیق درستی پاسخ است.

موسسه ریاضیات Clay، جایزه یک میلیون دلاری اولین اثبات درست مسئله تعیین کرده است.[۱]

مفهوم مسئله

ارتباط بین کلاس پیچیدگی P NP نظریه پیچیدگی محاسباتی -بخشی نظریه محاسبات بررسی منابع مورد نیاز زمان محاسبه جواب یک مسئله پردازد- مطالعه شود. مهمترین منابع یکی زمان (مراحل گام مورد نیاز دستیابی جواب) دیگری فضا (حافظه مورد نیاز حل مسئله) است.

در انالیزهایی شبیه این، یک مدل رایانه‌ای باید طبق ان، زمان محاسبه شود مورد نیاز است. طور معمول، مدل فرض کنند رایانه، "فطعی" (به مفهوم ازای یک حالت معین تمامی ورودی ها، رایانه تنها تواند یک عمل ممکن انجام دهد) "ترتیبی" (به معنی عملی بعد عمل دیگر انجام دهد) است.

در نظریه، کلاس P شامل تمام مسئله‌های تصمیم گیری -در زیر تعریف شده- پاسخ یک ماشین قطعی ترتیبی، زمان چندجمله‌ای ازای ورودی، ممکن باشد؛ کلاس NP شامل تمام مسئله‌های تصمیم گیری پاسخ مثبت تواند زمان چند جمله‌ای اطلاعات درست، تحقیق شود بطور معادل، پاسخ زمان چندجمله‌ای یک ماشین غیر قطعی، یافت شود.[۲]

با تعاریف، مهمترین سوال رابطه دو کلاس چگونه است؟ ایا P=NP؟

در یک نظرسنجی سال ۲۰۰۲ ۱۰۰ محقق، ۶۱ نفر پرسش پاسخ منفی دادند، ۹ نفر پاسخ مثبت ۲۲ نفر هنوز مطمئن نبودند. ۸ نفر معتقد بودند شاید سوال خارج اصول موضوعه پذیرفته شده کنونی باشد بنابر رد اثبات غیر ممکن است.[۳]

تعریف رسمی کلاس P NP

تعریف مسئله تصمیم گیری: مسئله‌ای یک رشته عنوان ورودی دریافت کرده پاسخ "بله" "خیر" دهد.اگر یک الگوریتم وجود داشته باشد (یک ماشین تورینگ یک برنامه رایانه‌ای حافظه نامتناهی) قادر باشد ازای هر ورودی طول n حداکثر مرحله k c اعداد ثابتی مستقل طول ورودی هستند، جواب درست بدهد انگاه گوییم مسئله تواند زمان چندجمله‌ای حل شود کلاس P قرار دهیم.