[Amir Shahbazzadeh]

نظریه محاسبات

نظریه محاسبات سعی دارد به این پرسش‌ها پاسخ دهد که اساسا چه چیزی می‌تواند محاسبه شود و محاسبهٔ آن چقدر توان و منابع نیاز دارد. در تلاشی برای پاسخ گویی به پرسش اول، نظریه محاسبه‌پذیری (computability theory) بررسی می‌کند که چه مسائلی قابل حل هستند ( از طریق نظریات مدل‌های پردازش ). پاسخ دومین پرسش به نظریه پیچیدگی محاسباتی مرتبط می‌شود. این نظریه به زمان و فضای مورد نیاز برای رسیدن به پاسخ مطلوب در روشهای مختلف پاسخگویی، می‌پرازد.

مسئله مشهور "P=NP?" یکی مسائل حل نشده نظریه محاسبات است.

*نظریه محاسبه‌پذیری (computability theory)
*نظریه پیچیدگی محاسباتی

[Amir Shahbazzadeh]

نظریه پیچیدگی محاسباتی

نظریهٔ پیچیدگی محاسباتی شاخه‌ای از نظریهٔ محاسبات، علوم نظری رایانه و ریاضی است که به بررسی دشواری حل مسائل به وسیلهٔ رایانه (به عبارت دقیق‌تر به صورت الگوریتمی) می‌پردازد. این نظریه بخشی از نظریهٔ محاسباتی است که با منابع مورد نیاز برای حل یک مساله سروکار دارد.

1- مقدمه
۲ -آیا P=NP است؟
۳- پیچیدگی زمانی
۴ -معرفی Np کامل
۵ -بررسی ناکارآمد بودن زمانی
۶ -روش‌هایی برای حل مسائل NP-Complete
- ۷ نمونه مساله

مقدمه

عمومی‌ترین منابع زمان (چقدر زمان برای حل کردن مساله لازم است) و فضا (چقدر حافظه مورد نیاز است) می‌باشند. سایر منابع می‌تواند تعداد پروسسورهای موازی (در حالت پردازش موازی) و... باشند. اما در این صفحه عوامل بالا مورد بحث نیستند. باید به این نکته توجه داشت که نظریه پیچیدگی با نظریه قابل حل بودن متفاوت است. این نظریه در مورد قابل حل بودن یک مساله بدون توجه به منابع مورد نیاز آن، بحث می‌کند. بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سوال به نظر طبیعی می‌رسد که درجه سختی مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.

برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند به طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس‌های پیچیدگی خوانده می‌شوند.

بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل عدم تعین صرفاً جنبهٔ صوری دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.

معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت P کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما NP شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔ یک الگوریتم سریع ممکن است. البته کلاس‌های پیچیدگی به مرتبه سخت‌تری از NP نیز وجود دارند.

    P-SPACE: مسائلی که با اختصاص دادن مقدار کافی حافظه (که این مقدار حافظه معمولاً تابعی از اندازه مساله می‌باشد) بدون در نظر گرفتن زمان مورد نیاز به حل آن، می‌توانند حل شوند.

    EXP-TIME: مسائلی که زمان مورد نیاز برای حل آنها به صورت توانی می‌باشد. مسائل این کلاس شامل همه مسائل سه کلاس بالایی نیز می‌باشد. نکته جالب و قابل توجه این است که حتی این کلاس نیز جامع نمی‌باشد. یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم‌ها نیز زمان بیش‌تری نسبت به زمان توانی می‌گیرند.

    Un-decidable یا غیرقابل تصمیم‌گیری: برای برخی از مسائل می‌توانیم اثبات کنیم که الگوریتمی را نمی‌شود پیدا کرد که همیشه آن مساله را حل می‌کند، بدون در نظر گرفتن فضا و زمان. در این زمینه آقای ریچارد لیپتون (از صاحب‌نظران این زمینه) در مقاله‌ای نوشته‌اند: یک روش اثبات غیررسمی برای این مساله می‌تواند این باشد: تعداد زیادی مساله، مثلاً به زیادی اعداد حقیقی وجود دارند، ولی تعداد برنامه‌هایی که مسائل را حل می‌کنند در حد اعداد صحیح هستند. اما ما همیشه می‌توانیم مسائل به دردبخوری را پیدا کنیم که قابل حل نیستند.

آیا P=NP است؟

برابر بودن مسائل کلاس P دقیقا همان مسائل کلاس NP، یکی از مهم‌ترین سوال‌های بدون جواب علوم کامپیوتری است. به بیانی دیگر اگر همیشه به این سادگی بتوان صحت یک راه‌حل را بررسی کرد، آیا پیدا کردن راه‌حل نیز می‌تواند به آن سادگی باشد؟ برای این سوال یک جایزه ۱ میلیون دلاری از طرف انسیتیتو ریاضی Clay در نظرگرفته شده‌است. ما هیچ دلیلی برای قبول کردن آن نداریم ولی بین نظریه‌پردازان نیز این باور وجود دارد که باید جواب این سوال منفی باشد[نیازمند منبع]. همچنین دلیلی برای رد کردن آن نیز وجود ندارد.

پیچیدگی زمانی

پیچیدگی زمانی یک مساله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مساله به عنوان تابعی از اندازهٔ ورودی (معمولاً بوسیله تعداد بیت‌ها بیان می‌شود) بوسیله کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مساله، فرض کنید که یک مساله با ورودی 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 نیز خوانده می‌شود.


بررسی ناکارآمد بودن زمانی

مسائلی که در تئوری قابل حل شدن می‌باشند ولی در عمل نمی‌توان آنها را حل کرد، محال یا ناشدنی می‌نامند. در حالت کلی فقط مسائلی که زمان آنها به صورت Polynomial می‌باشد و اندازه ورودی آنها در حد کوچک یا متوسط می‌باشد قابل حل شدن می‌باشند. مسائلی که زمان آنها به صورت توانی (EXPTIME-complete) می‌باشند به عنوان مسائل محال یا ناشدنی شناخته شده‌اند. همچنین اگر مسائل رده NP جز مسائل رده P نباشند، مسائل NP-Complete نیز به عنوان محال یا نشدنی خواهند بود. برای ملموس‌تر شدن این مساله فرض کنید که یک مساله 2n مرحله لازم دارد تا حل شود (n اندازه ورودی می‌باشد). برای مقادیر کوچک n=۱۰۰ و با در نظر گرفتن کامپیوتری که 1010 (10 giga) عملیات را در یک ثانیه انجام می‌دهد، حل کردن این مساله زمانی حدود 1012 * 4 سال طول خواهد کشید، که این زمان از عمر فعلی جهان بیشتر است!

روش‌هایی برای حل مسائل NP-Complete

به خاطر اینکه تعداد مسائل NP-Complete بسیار زیاد می‌باشد، شناختن اینگونه مسائل به ما کمک می‌کند تا دست از پیدا کردن یک الگوریتم سریع و جامع برداریم و یکی از روش‌های زیر را امتحان کنیم:

    به کار بردن یک روش حدسی: یک الگوریتم که تا حد قابل قبولی در بیشتر موارد درست کار می‌کند، ولی تضمینی وجود ندارد که در همه موارد با سرعت قابل قبول نتیجه درستی تولید کند.

حل کردن تقریبی مساله به جای حل کردن دقیق آن: اغلب موارد این روش قابل قبول می‌باشد که با یک الگوریتم نسبتاً سریع یک مساله را به طور تقریبی حل کنیم که می‌توان ثابت کرد جواب بدست آمده تقرییا نزدیک به جواب کاملاً صحیح می‌باشد.

الگوریتم‌های زمان توانی را به کار ببریم: اگر واقعا مجبور به حل کردن مساله به طور کامل هستیم، می‌توان یک الگوریتم با زمان توانی نوشت و دیگر نگران پیدا کردن جواب بهتر نباشیم.

    از خلاصه کردن استفاده کنیم: خلاصه کردن به این مفهوم می‌باشد که از برخی اطلاعات غیرضروری می‌توان صرف نظر کرد. اغلب این اطلاعات برای پیاده‌سازی مساله پیچیده در دنیای واقعی مورد نیاز می‌باشد، ولی در شرایطی که بخواهیم به نحوی مساله را حل کنیم (حداقل به صورت تئوری و نه در عمل) می‌توان از برخی اطلاعات غیرضروری صرف نظر کرد.

نمونه مساله
یک مسیر ساده در یک گراف به مسیری اطلاق می‌شود که هیچ راس یا یال تکراری در آن وجودنداشته‌باشد. برای پیاده سازی مساله ما به این احتیاج داریم که بتوانیم یک سوال بلی/خیر طراحی کنیم. با داشتن گراف G، رئوس s و t و عدد k آیا یک مسیر ساده از s به t با حداقل k یال وجوددارد؟ راه‌حل این مساله جواب سوال خواهد بود. چرا این مساله NP می‌باشد؟ چون اگر مسیری به شما داده شود، به راحتی می‌توان طول مسیر را مشخص نمود و آن را با k مقایسه کرد. همه این کارها در زمان خطی و صد البته در زمان Polynomial قابل انجام می‌باشد. اگر چه می‌دانیم که این مساله آیا در کلاس P می‌باشد یا نه، با این حال روش خاصی برای پیدا کردن مسیری با ویژگی‌های ذکر شده نیز بیان نشده‌است. و در حقیقت این مساله جز NP-Completeها می‌باشد، پس می‌توان به این نتیجه نیز رسید که الگوریتمی کارآمد با چنان عملیات وجود ندارد. الگوریتم‌هایی وجود دارند که این مساله را حل می‌کنند، به عنوان مثال همه مسیرهای موجود و ممکن را بررسی نموده و نتایج مقایسه شوند که آیا این مسیر مساله را حل می‌کند یا نه. اما تا آنجایی که می‌دانیم، الگوریتمی با زمان Polynomial برای حل این مساله وجود ندارد.

[Amir Shahbazzadeh]

نظریه محاسبه‌پذیری از مباحث پایه در علوم رایانه است که به بررسی محاسبه‌پذیر و محاسبه‌ناپذیر بودن عملیات با استفاده از ابزارهای کلاسیک نظیر ماشین ثبات، ماشین تورینگ و توابع بازگشتی می‌پردازد. بدون شک یکی از علل پیشرفت این نظریه تلاش محققین برای اثبات پاسخ منفی به مساله دهم هیلبرت بوده‌است.

دانشمندان کامپیوتر، برای مطالعهٔ جدی نظریه رایانش(شماره پذیری)، با یک مفهوم انتزاعی ریاضی برای کامپیوترها که مدل رایانش گفته می‌شود، سر و کار دارند. قاعده سازی‌های متعددی، برای استفاده وجود دارد، اما ماشین تورینگ(Turing) در این میان بیش‌ترین کاربرد را دارد. یک ماشین تورینگ را می‌توان هم ارز یک کامپیتر شخصی رومیزی، در نظر گرفت، با حافظهٔ بی نهایت که به این حافظه از طریق تعداد زیادی تکه‌های کوچک گسسته، دسترسی دارد. دانشمندان کامپیوتر به دلیل قابلیت سادگی قاعده سازی، تحلیل و آنالیز و قابل استفاده برای اثبات نتایج از این ماشین استفاده می‌کنند. چون حافظهٔ بی نهایت یک نسبت غیر مادی در نظر گرفته می‌شود، برای هر مسئله که با استفاده از ماشین ترینگ حل می‌شود، حافظهٔ مورد استفاده همواره محدود است. در نتیجه هر مسئله را می‌توان با استفاده از یک کامپیوتر شخصی که حافظهٔ مورد نیاز بر روی آن نصب شده، از طریق یک ماشین تورینگ حل کرد.

۱ -نظریه شماره پذیری
۲ -نظریه پیچیدگی
۳- حساب لامبدا
۴ -منطق ترکیبیاتی
۵ -توابع بازگشتی مو

نظریه شماره پذیری
نظریه شماره پذیری، با این سوال که آیا یک مسئله قابل حل بر روی یک کامپیوتر هست یا نه، سر و کار دارد. مسئلهٔ halting یکی از مهم‌ترین نتایج در نظریهٔ شماره پذیری است. این مسئله به آسانی قابل قاعده سازی و به سختی با استفاده از ماشین ترینگ قابل حل است! بخش عمده‌ای از نظریهٔ شماره پذیری، بر نتیجهٔ مسئلهٔ halting، استوار است. نظریهٔ شماره پذیری، با یک شاخه از منطق ریاضی به نام نظریهٔ بازگشت، در ارتباط تنگاتنگ است. بسیاری از ریاضی دانان و نظریه پردازان شمارش پذیری، که دربارهٔ نظریهٔ بازگشت به مطالعه می‌پردازند، این نظریه را در آخر به نظریهٔ شماره پذیری ارجاع می‌دهند.

نظریه پیچیدگی

نظریه پیچیدگی، نه تنها با این موضوع که آیا مسئلهٔ مطرح شده بر روی کامپیوتر قابل حل هست یا نه؛ بلکه با این موضوع که چقدر مسئله می‌تواند به صورت کارآمد حل شود، در ارتباط است. دو جنبهٔ مهم در این نظریه مطرح است: پیچیدگی زمان و پیچیدگی فضا. یعنی برای حل مسئله چند پله باید طی شود و به چقدر حافظه نیاز است. برای تحلیل این که یک الگوریتم به چقدر زمان و حافظه نیاز دارد، دانشمندان کامپیوتر زمان و حافظه‌ای را که برای حل یک مسئله مورد نیاز است، به عنوان یک تابع از سایز ورودی مسئله بیان می‌کنند. برای مثال پیدا کردن یک عدد خاص در یک لیست بلند از اعداد دشوارتر می‌شود هنگامی که تعداد اعداد افزایش می‌یابد.. اگر n عدد در لیست وجود داشته باشد که مرتب نشده باشند و یا اندیس گذاری نشده باشند در هر صورت ما باید همهٔ اعداد را برای پیدا کردن عدد خاص، چک کنیم. بنابراین در این مثال برای حل مسئلهٔ مطرح شده، کامپیوتر باید مراحلی را طی کند که تعداد آن‌ها به صورت خطی تغییر می‌کند.

حساب لامبدا

یک محاسبه یک
منطق ترکیبیاتی

مفهومی است که شباهت‌های زیادی به حساب لامبدا دارد. اما تفاوت‌های عمده‌ای نیز دارند. منطق ترکیبیاتی با تلاش‌های بسیار پیشرفت زیادی در زمینه‌های زیر داشته‌است:

- کشف طبیعت تناقض‌ها

-اقتصادی تر کردن شالودهٔ ریاضیات

- کاهش نشان گذاری متغیرها

توابع بازگشتی مو

یک محاسبه به صورت یک تابع بازگشتی مو است، اگر دنبالهٔ تعریف شدهٔ آن، متغیرهای ورودی و یک دنبالهٔ توابع بازگشتی همراه با ورودی‌ها و خروجی‌های آن مشخص باشند. بنابراین اگر در تعریف دنبالهٔ بازگشتی تابع f(x)، توابع g(x) و h(x,y) وجود داشته باشند، در نتیجه عباراتی به شکل g(۵)=۷ و یا h(۳٬۲)=۱۰ ممکن است ظاهر شوند. در این گونه توابع، اگر آخرین عبارت مقدار تابع بازگشتی ایی که به ورودی‌ها داده شده است؛ را بدهد، محاسبات پایان می‌پذیرند. ؛ الگوریتم مارکف یک سیستم رشته‌ای با قابلیت دوباره نویسی، که از قوانین گرامری شکلی برای به کار انداختن رشته‌ها استفاده می‌کند.

ماشین رجیستر(Register Machine)

یک کامپیوتر ایده آل تئوریک است! متغیرهای بیشتری وجود دارد. در بسیاری از آن‌ها، هر رجیستر می‌تواند یک عدد طبیعی با سایز نامحدود، را نگهداری کند، دستور العمل‌ها ساده هستند؛ برای مثال فقط کاستن پله‌ای و نمو وجود دارد. کمبود ذخیرهٔ خارجی که در ماشین‌های تورینگ دیده می‌شود، می‌تواند با جایگذاری نقشش با استفاده از روش‌های عددی Godel درک شود. این حقیقت که هر رجیستر قابلیت نگهداری یک عدد طبیعی را دارد، امکان نمایش یک چیز پیچیده تر (مثلاً یک دنباله یا یک ماتریس)، را فراهم می‌سازد.

P

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