دانلود مقالات ISI درباره پیچیدگی محاسباتی + ترجمه فارسی

پیچیدگی محاسباتی(به انگلیسی: Computational complexity) شاخه ای از علوم کامپیوتر و ریاضی است که به بررسی دشواری حل مسائل به وسیله ی رایانه (به عبارت دقیق تر به صورت الگوریتمی) می پردازد. این نظری بخشی از نظریه ی محاسباتی است که با منابع مورد نیاز برای حل یک مساله سروکار دارد. عمومی ترین منابع زمان (چقدر زمان برای حل کردن مساله لازم است) و فضا (چقدر حافظه مورد نیاز است) می باشند. سایر منابع می تواند تعداد پروسسور های موازی (در حالت پردازش موازی) و … باشند. اما در این مقاله ما در مورد عواملی مثل عوامل بالا بحثی نکرده ایم. باید به این نکته توجه داشت که نظریه پیچیدگی با نظریه قابل حل بودن متفاوت می باشد. این نظریه در مورد قابل حل بودن یک مساله بدون توجه به منابع مورد نیاز آن، بحث می کند. بعد از این نظریه که بیان می کند کدام مسائل قابل حل می باشند و کدام مسائل غیرقابل حل، این سوال به نظر طبیعی می رسد که درجه سختی مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه می باشد. برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند به طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس‌های پیچیدگی خوانده می‌شوند. معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت P کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما NP شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب ‌برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔ یک الگوریتم سریع ممکن است. البته کلاس‌های پیچیدگی به مرتبه سخت‌تری از NP نیز وجود دارند. ▪️ مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولا تابعی از اندازه مساله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند. PSPACE ▪️مسائلی که زمان مورد نیاز برای حل آنها به صورت توانی می‌باشد EXPTIME. مسائل این کلاس بسیار جذاب و سرگرم کننده می‌باشند (حداقل برای ما!). و شامل همه مسائل سه کلاس بالایی نیز می‌باشد. نکته جالب و قابل توجه این می‌باشد که حتی این کلاس نیز جامع نمی‌باشد. یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم‌ها نیز زمان بیش‌تری نسبت به زمان توانی می‌گیرند. ▪️غیرقابل تصمیم‌گیری یا( Un-decidable): برای برخی از مسائل می‌توانیم اثبات کنیم که الگوریتمی را نمی‌شود پیدا کردن که همیشه آن مساله را حل می‌کند، بدون در نظر گرفتن فضا و زمان. در این زمینه آقای ریچارد لیپتون (از صاحب‌نظران این زمینه) در مقاله‌ای نوشته‌اند: یک روش اثبات غیررسمی برای این مساله می‌تواند این باشد: تعداد زیادی مساله، مثلا به زیادی اعداد حقیقی وجود دارند، ولی تعداد برنامه‌هایی که مسائل را حل می‌کنند در حد اعداد صحیح می‌باشند. اما ما همیشه می‌توانیم مسائل به دردبخوری را پیدا کنیم که قابل حل نمی‌باشند. ● روش‌هایی برای حل مسائل NP-Complete به خاطر اینکه تعداد مسائل NP-Complete بسیار زیاد می‌باشد، شناختن اینگونه مسائل به ما کمک می‌کند تا دست از پیدا کردن یک الگوریتم سریع و جامع برداریم و یکی از روش‌های زیر را امتحان کنیم: ▪️به کار بردن یک روش حدسی: یک الگوریتم که تا حد قابل قبولی در بیشتر موارد درست کار می‌کند، ولی تضمینی وجود ندارد که در همه موارد با سرعت قابل قبول نتیجه درستی تولید کند. ▪️ حل کردن تقریبی مساله به جای حل کردن دقیق آن: اغلب موارد این روش قابل قبول می‌باشد که با یک الگوریتم نسبتا سریع یک مساله را به طور تقریبی حل کنیم که می‌توان ثابت کرد جواب بدست آمده تقرییا نزدیک به جواب کاملا صحیح می‌باشد. ▪️ الگوریتم‌های زمان توانی را به کار ببریم: اگر واقعا مجبور به حل کردن مساله به طور کامل هستیم، می‌توان یک الگوریتم با زمان توانی نوشت و دیگر نگران پیدا کردن جواب بهتر نباشیم. ▪️ از خلاصه کردن استفاده کنیم: خلاصه کردن به این مفهوم می‌باشد که از برخی اطلاعات غیرضروری می‌توان صرف نظر کرد. اغلب این اطلاعات برای پیاده‌سازی مساله پیچیده در دنیای واقعی مورد نیاز می‌باشد، ولی در شرایطی که بخواهیم به نحوی مساله را حل کنیم (حداقل به صورت تئوری و نه در عمل) می‌توان از برخی اطلاعات غیرضروری صرف نظر کرد.