Difference between revisions of "نظریه پیچیدگی محاسباتی"

اصلاح املا، اصلاح سجاوندی، اصلاح ارقام، اصلاح نویسه، اصلاح فاصلهٔ مجازی، اصلاح نویسه‌های عربی
(اصلاح املا، اصلاح سجاوندی، اصلاح ارقام، اصلاح نویسه، اصلاح فاصلهٔ مجازی، اصلاح نویسه‌های عربی)
'''نظریهٔ پیچیدگی محاسباتی''' (Computational complexity theory) شاخه‌ای از [[نظریه محاسبات|نظریهٔ محاسبات]]، [[علوم نظری رایانه]] و [[ریاضی]] است که به بررسی دشواری حل مسائل به وسیلهٔ [[رایانه]] (به عبارت دقیق‌تر به صورت [[الگوریتم|الگوریتمی]]) می‌پردازد. این نظریه بخشی از [[نظریه محاسبات|نظریهٔ محاسباتی]] است که با منابع مورد نیاز برای حل یک مسئله سروکار دارد.
 
== مقدمه ==
بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل [[عدم تعین]] صرفاً جنبهٔ آموزشی دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.
 
معروف‌ترین کلاس‌های پیچیدگی، '''P''' و '''NP''' هستند که مسئله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طوربه‌طور شهودی می‌توان گفت '''P''' کلاس مسئله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما '''NP''' شامل آن دسته از مسئله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیلهٔ یک [[کارایی الگوریتم‌ها|الگوریتم سریع]] ممکن است.
البته کلاس‌های پیچیدگی به مراتب سخت‌تری از '''NP''' نیز وجود دارند.
* '''P-SPACE''': مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولاً تابعی از اندازه مسئله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند.
هنگامی که یک الگوریتم خاص را تحلیل می‌کنیم، پیچیدگی زمانی (یا حافظه‌ای) یا مرتبه پیچیدگی زمانی آن را تعیین می‌کنیم. عبارت است از مطالعهٔ تمام الگوریتم‌های امکانپذبر برای حل یک مسئله مفروض است. در تحلیل پیچیدگی محاسباتی کوشش می‌کنیم تا حد پایینی کارایی همه الگوریتم‌ها را برای یک مسئله مفروض به دست آوریم.{{سخ}}
تحلیل پیچیدگی محاسباتی را با مطالعهٔ مسئله مرتب‌سازی معرفی می‌کنیم. دو دلیل برای انتخاب مسئله وجود دارد. نخست چند الگوریتم ابداع شده‌اند که مسئله را حل می‌کنند. با مطالعه و مقایسه این الگوریتم‌ها، دیدی از چگونگی انتخاب از میان چند الگوریتم برای یک مسئله و بهبود بخشیدن به یک الگوریتم مفروض به دست می‌آوریم.{{سخ}}
دوم، مسئله مرتب‌سازی یکی از معدود مسائلی است که در بسط الگوریتم‌هایی با پیچیدگی زمانی نزدیک به حد پایینی از آن موفق بوده استبوده‌است.
 
== معرفی [[Np کامل]] ==
به خاطر اینکه تعداد مسائل NP-Complete بسیار زیاد می‌باشد، شناختن اینگونه مسائل به ما کمک می‌کند تا دست از پیدا کردن یک الگوریتم سریع و جامع برداریم و یکی از روش‌های زیر را امتحان کنیم:
* '''به کار بردن یک روش حدسی''': یک الگوریتم که تا حد قابل قبولی در بیشتر موارد درست کار می‌کند، ولی تضمینی وجود ندارد که در همه موارد با سرعت قابل قبول نتیجه درستی تولید کند.
* '''حل کردن تقریبی مسئله به جای حل کردن دقیق آن''': اغلب موارد این روش قابل قبول می‌باشد که با یک الگوریتم نسبتاً سریع یک مسئله را به طوربه‌طور تقریبی حل کنیم که می‌توان ثابت کرد جواب بدست آمده تقرییا نزدیک به جواب کاملاً صحیح می‌باشد.
* '''الگوریتم‌های زمان توانی را به کار ببریم''': اگر واقعاً مجبور به حل کردن مسئله به طوربه‌طور کامل هستیم، می‌توان یک الگوریتم با زمان توانی نوشت و دیگر نگران پیدا کردن جواب بهتر نباشیم.
* '''از خلاصه کردن استفاده کنیم''': خلاصه کردن به این مفهوم می‌باشد که از برخی اطلاعات غیرضروری می‌توان صرف نظر کرد. اغلب این اطلاعات برای پیاده‌سازی مسئله پیچیده در دنیای واقعی مورد نیاز می‌باشد، ولی در شرایطی که بخواهیم به نحوی مسئله را حل کنیم (حداقل به صورت تئوری و نه در عمل) می‌توان از برخی اطلاعات غیرضروری صرف نظر کرد.
 
* {{یادکرد |کتاب= 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 4, 2008).
 
[http://qwiki.caltech.edu/wiki/Complexity_Zoo سایت Clatech]
439

edits