نظریه پیچیدگی محاسباتی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Hootandolati (بحث | مشارکتها) |
Hootandolati (بحث | مشارکتها) |
||
خط ۲:
== مقدمه ==
عمومی‌ترین منابع، زمان (مقدار زمان مورد نیاز برای حل مسئله) و فضا (مقدار حافظه مورد نیاز) می‌باشند. از سایر منابع می‌تواند به تعداد پردازنده‌های موازی (در حالت [[پردازش موازی]])
مواردی هست که
▲عمومی‌ترین منابع، زمان (مقدار زمان مورد نیاز برای حل مسئله) و فضا (مقدار حافظه مورد نیاز) می‌باشند. از سایر منابع می‌تواند به تعداد پردازنده‌های موازی (در حالت [[پردازش موازی]]) و... اشاره کرد. اما در اینجا عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با [[نظریه قابل حل بودن]] متفاوت است. این نظریه در مورد قابل حل بودن یک مسئله بدون توجه به منابع مورد نیاز آن، بحث می‌کند.
▲مواردی هست که میدانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل، منابع و ابزار لازم جهت پیاده‌سازی آن مسئله را نداریم.
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سؤال به نظر طبیعی می‌رسد که [[درجه سختی]] مسئله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.
سطر ۱۶ ⟵ ۱۵:
* '''P-SPACE''': مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولاً تابعی از اندازه مسئله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند.
* '''EXP-TIME''': مسائلی که زمان مورد نیاز برای حل آنها به صورت توانی می‌باشد. مسائل این کلاس شامل همه مسائل سه کلاس بالایی نیز می‌باشد. نکته جالب و قابل توجه این است که حتی این کلاس نیز جامع نمی‌باشد. یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم‌ها نیز زمان بیش‌تری نسبت به زمان توانی می‌گیرند.
* '''Un-decidable''' یا '''غیرقابل تصمیم‌گیری''': برای برخی از مسائل می‌توانیم اثبات کنیم که الگوریتمی را نمی‌شود پیدا کرد که همیشه آن مسئله را حل می‌کند، بدون در نظر گرفتن فضا و زمان. به عقیده
== آیا P=NP است؟ ==
برابر بودن مسائل کلاس P
== [[پیچیدگی زمانی]] ==
پیچیدگی زمانی
▲پیچیدگی زمانی یک مسئله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مسئله به عنوان [[تابع|تابعی]] از اندازهٔ ورودی (معمولاً بوسیله تعداد [[بیت (رایانه)|بیت‌ها]] بیان می‌شود) بوسیله کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مسئله، فرض کنید که یک مسئله با ورودی 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 حل نماید.
سطر ۳۶ ⟵ ۳۳:
== بررسی ناکارآمد بودن زمانی ==
مسائلی که در تئوری قابل حل شدن می‌باشند ولی در عمل نمی‌توان آنها را حل کرد، محال یا ناشدنی
برای ملموس‌تر شدن این مسئله فرض کنید که یک مسئله <math>2^n</math> مرحله لازم دارد تا حل شود (n اندازه ورودی می‌باشد). برای مقادیر کوچک n=۱۰۰ و با در نظر گرفتن کامپیوتری که <math>10^{10}</math> (10 giga) عملیات را در یک ثانیه انجام می‌دهد، حل کردن این مسئله زمانی حدود <math>10^{12}*4</math> سال طول خواهد کشید، که این زمان از عمر فعلی جهان بیشتر است!
سطر ۴۳ ⟵ ۴۰:
* '''به کار بردن یک روش حدسی''': یک الگوریتم که تا حد قابل قبولی در بیشتر موارد درست کار می‌کند، ولی تضمینی وجود ندارد که در همه موارد با سرعت قابل قبول نتیجه درستی تولید کند.
* '''حل کردن تقریبی مسئله به جای حل کردن دقیق آن''': اغلب موارد این روش قابل قبول می‌باشد که با یک الگوریتم نسبتاً سریع یک مسئله را به طور تقریبی حل کنیم که می‌توان ثابت کرد جواب بدست آمده تقرییا نزدیک به جواب کاملاً صحیح می‌باشد.
* '''الگوریتم‌های زمان توانی را به کار ببریم''': اگر
* '''از خلاصه کردن استفاده کنیم''': خلاصه کردن به این مفهوم می‌باشد که از برخی اطلاعات غیرضروری می‌توان صرف نظر کرد. اغلب این اطلاعات برای پیاده‌سازی مسئله پیچیده در دنیای واقعی مورد نیاز می‌باشد، ولی در شرایطی که بخواهیم به نحوی مسئله را حل کنیم (حداقل به صورت تئوری و نه در عمل) می‌توان از برخی اطلاعات غیرضروری صرف نظر کرد.
سطر ۶۱ ⟵ ۵۸:
* {{یادکرد |کتاب= Computers and Intractability: A Guide to the Theory of P-Completeness |نویسنده = M.R. Garey and D.S. Johnson |ناشر =W. H. Freeman|شهر=New York|سال=۱۹۸۳|شابک=ISBN 0-7167-1045-5}}
Wikipedia contributors, «Computational complexity theory,» Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Computational_complexity_theory&oldid=184433565 (accessed February
[http://qwiki.caltech.edu/wiki/Complexity_Zoo سایت Clatech]
| |||