تفاوت میان نسخه‌های «نظریه پیچیدگی محاسباتی»

جز
ابرابزار
جز (Bot: Removing Link FA template)
جز (ابرابزار)
== مقدمه ==
 
عمومی‌ترین منابع، زمان (مقدار زمان مورد نیاز برای حل مساله) و فضا (مقدار حافظه مورد نیاز) می‌باشند. از سایر منابع می‌تواند به تعداد پردازنده هایپردازنده‌های موازی (در حالت [[پردازش موازی]]) و... اشاره کرد. اما در اینجا عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با [[نظریه قابل حل بودن]] متفاوت است. این نظریه در مورد قابل حل بودن یک مساله بدون توجه به منابع مورد نیاز آن، بحث می‌کند.
مواردی هست که میدانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل، منابع و ابزار لازم جهت پیاده‌سازی آن مسئله را نداریم.
 
بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل [[عدم تعین]] صرفاً جنبهٔ آموزشی دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.
 
معروف‌ترین کلاس‌های پیچیدگی، '''P''' و '''NP''' هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت '''P''' کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما '''NP''' شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔوسیلهٔ یک [[کارایی الگوریتم‌ها|الگوریتم سریع]] ممکن است.
البته کلاس‌های پیچیدگی به مراتب سخت‌تری از '''NP''' نیز وجود دارند.
* '''P-SPACE''': مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولاً تابعی از اندازه مساله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند.
پیچیدگی زمانی یک مساله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مساله به عنوان [[تابع|تابعی]] از اندازهٔ ورودی (معمولاً بوسیله تعداد [[بیت|بیت‌ها]] بیان می‌شود) بوسیله کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مساله، فرض کنید که یک مساله با ورودی n بیت در n² گام حل شود. در این مثال می‌گوییم که مساله از درجه پیچیدگی n² می‌باشد. البته تعداد دقیق گام‌ها بستگی به ماشین و زبان مورد استفاده دارد. اما برای صرف نظر کردن از این مشکل، [[نماد O بزرگ]] (Big O notation) معمولاً بکار می‌رود. اگر یک مساله پیچیدگی زمانی از مرتبه (O(n² روی یک کامپیوتر نمونه داشته باشد، معمولاً روی اکثر کامپیوترهای دیگر نیز پیچیدگی زمانی از مرتبه (O(n² خواهدداشت. پس این نشانه به ما کمک می‌کند که صرف نظر از یک کامپیوتر خاص، یک حالت کلی برای پیچیدگی زمانی یک الگوریتم ارائه دهیم.{{سخ}}
پیچیدگی محاسباتی:{{سخ}}
هنگامی که یک الگوریتم خاص را تحلیل میمی‌کنیم، کنیم ،پیچیدگیپیچیدگی زمانی (یا حافظه ایحافظه‌ای) یا مرتبه پیچیدگی زمانی آن را تعیین می کنیممی‌کنیم. عبارت است از مطالعه یمطالعهٔ تمام الگوریتم هایالگوریتم‌های امکانپذبر برای حل یک مسئله مفروض است. در تحلیل پیچیدگی محاسباتی کوشش می کنیممی‌کنیم تا حد پایینی کارایی همه الگوریتم هاالگوریتم‌ها را برای یک مسئله مفروض به دست آوریم.{{سخ}}
تحلیل پیچیدگی محاسباتی را با مطالعه یمطالعهٔ مسئله مرتب سازیمرتب‌سازی معرفی میمی‌کنیم. کنیم.دو دلیل برای انتخاب مسئله وجود دارد. نخست چند مسئله ابداع شده اندشده‌اند که مسئله را حل می کنندمی‌کنند. با مطالعه و مقایسه این الگوریتمالگوریتم‌ها، ها،دیدیدیدی از چگونگی انتخاب از میان چند الگوریتم برای یک مسئله و بهبود بخشیدن به یک الگوریتم مفروض به دست می آوریممی‌آوریم.{{سخ}}
دوم،مسئلهدوم، مرتبمسئله سازیمرتب‌سازی یکی از معدود مسائلی است که در بسط الگوریتم هاییالگوریتم‌هایی با پیچیدگی زمانی نزدیک به حد پایینی از آن موفق بوده است.
 
== معرفی [[Np کامل]] ==
 
تا این بخش از مقاله مسائلی معرفی شدند که اگر بتوان روشی برای حل آنها حدس زد، در زمان نزدیک به زمان خطی و یا حداقل در زمان چند جمله‌ای برحسب ورودی می‌توانستیم صحت راه‌حل را بررسی کنیم.کنیم؛ ولی '''NP-Complete'''ها مسائلی هستند که اثبات شده به سرعت قابل حل نیستند.
در تئوری پیچیدگی NP-Completeها دشوارترین مسائل کلاس NP هستند و جزء مسائلی می‌باشند که احتمال حضورشان در کلاس P خیلی کم است. علت این امر این می‌باشد که اگر یک راه‌حل پیدا شود که بتواندیک مساله NP-Complete را حل کند، می‌توان از آن الگوریتم برای حل کردن سریع همه مسائل NP-Complete استفاده کرد. به خاطر این مساله و نیز بخاطر اینکه تحقیقات زیادی برای پیدا کردن الگوریتم کارآمدی برای حل کردن اینگونه مسائل با شکست مواجه شده‌اند، وقتی که مساله‌ای به عنوان NP-Complete معرفی شد، معمولاً اینطور قلمداد می‌شود که این مساله در زمان Polynomial قابل حل شدن نمی‌باشد، یا به بیانی دیگر هیچ الگوریتمی وجود ندارد که این مساله را در زمان Polynomial حل نماید.
کلاس متشکل از مسائل '''NP-Complete''' با نام '''NP-C''' نیز خوانده می‌شود.
 
== نمونه مساله ==
یک مسیر ساده در یک گراف به مسیری اطلاق می‌شود که هیچ راس یا یال تکراری در آن وجودنداشته‌باشد. برای پیاده سازیپیاده‌سازی مساله ما به این احتیاج داریم که بتوانیم یک سوال بلی/خیر طراحی کنیم. با داشتن گراف G، رئوس s و t و عدد k آیا یک مسیر ساده از s به t با حداقل k یال وجوددارد؟ راه‌حل این مساله جواب سوال خواهد بود.
چرا این مساله NP می‌باشد؟ چون اگر مسیری به شما داده شود، به راحتی می‌توان طول مسیر را مشخص نمود و آن را با k مقایسه کرد. همه این کارها در زمان خطی و صد البته در زمان Polynomial قابل انجام می‌باشد.
اگر چه می‌دانیم که این مساله آیا در کلاس P می‌باشد یا نه، با این حال روش خاصی برای پیدا کردن مسیری با ویژگی‌های ذکر شده نیز بیان نشده‌است.نشده‌است؛ و در حقیقت این مساله جز NP-Completeها می‌باشد، پس می‌توان به این نتیجه نیز رسید که الگوریتمی کارآمد با چنان عملیات وجود ندارد.
الگوریتم‌هایی وجود دارند که این مساله را حل می‌کنند، به عنوان مثال همه مسیرهای موجود و ممکن را بررسی نموده و نتایج مقایسه شوند که آیا این مسیر مساله را حل می‌کند یا نه. اما تا آنجایی که می‌دانیم، الگوریتمی با زمان Polynomial برای حل این مساله وجود ندارد.
 
۱۷٬۷۰۷

ویرایش