نظریهی پیچیدگی محاسباتی
در این قسمت به کاری که بتواند
توسط کامپیوتر حل شود، مسئلهی محاسباتی اطلاق میشود (به این معنی که مسئلهی
مورد نظر بتواند به صورت مجموعهای از دستورالعملهای ریاضی بیان شود). یک مسئلهی
محاسباتی از نمونه مسائل و جوابهایی برای آن مسائل تشکیل شده است. به عنوان
مثال، آزمون اول بودن[1]، مسئلهی تشخیص دادن اول بودن یا
نبودن یک عدد معین است. نمونههای این مسئله اعداد طبیعی میباشند و بر اساس این
که یک نمونه اول باشد یا خیر جواب به آن نیز آری یا خیر خواهد بود.
زمانی به یک مسئله ذاتا دشوار اطلاق میشود که الگوریتم برای رسیدن به جواب آن نیاز به منابع عمده و قابل توجهی داشته باشد. نظریهي پیچیدگی محاسباتی با وارد کردن مدلهای محاسباتی به منظور بررسی این مسائل و محاسبهی منابع مورد نیاز برای حل آنها، مثل زمان و حافظه، این مطلب را تحقق میبخشد. معیارهای پیچیدگی دیگری مثل میزان ارتباطات (که در پیچیدگی ارتباطی[2] مورد استفاده قرار میگیرد)، تعداد گیتهای منطقی در یک مدار (که در پیچیدگی مداری[3] مورد استفاده قرار میگیرد) و تعداد پردازندهها (که در محاسبات موازی مورد[4] استفاده قرار میگیرد) نیز مورد استفاده قرار میگیرند. یکی از وظایف پیچیدگی محاسباتی این است که محدودیتهای عملی کامپیوترها را تعیین کند که قادر به انجام چه کارهایی هستند و چه کارهایی را نمیتوانند انجام دهند.
تحلیل
الگوریتمها[5] و نظریهي
قابل محاسبه بودن[6] دو زمینهی
بسیار مرتبط با هم در علوم نظری کامپیوتر به شمار میروند. تفاوت کلیدی بین آن دو
در این است که تحلیل الگوریتمها به تعیین میزان منابع مورد نیاز یک الگوریتم خاص
برای حل یک مسئله اختصاص دارد در حالی که نظریهي قابل محاسبه بودن پرسشی عمومیتر
در مورد تمام الگوریتمهای ممکن که میتوانند برای حل همان مسئله به کار روند،
مطرح میکند. به طور دقیقتر، این نظریه سعی دارد تا مسائلی را که میتوانند یا
نمیتوانند با استفاده از تعداد محدود اما مناسبی از منابع حل شوند، طبقهبندی
کند.
+ نوشته شده در شنبه هجدهم شهریور ۱۳۹۱ ساعت 15:22 توسط مدیر وبلاگ
|
الگوریتم ژنتیک، الگوریتم های ژنتیک، الگوریتم بهینه سازی اجتماع مورچگان، الگوریتم بهینه سازی کولونی مورچگان، الگوریتم بهینه سازی هجوم ذرات، الگوریتم بهینه سازی اجتماع ذرات، الگوریتم تبرید تدریجی، الگوریتم شبیه سازی تبرید فلزات، الگوریتم بهینه سازی زنبور عسل، بهینه سازی، پیچیدگی محاسباتی، هوش مصنوعی، جستجوی ناآگاهانه، جستجوی عمومی، جستجوی عمقی، جستجوی سطحی، جستجوی مکاشفه ای، جستجوی حریصانه، الگوریتم تپه نوردی، الگوریتم جستجوی تابو، جستجوی جامع، بهینه سازی تحلیلی، روش غیرمرکب سرازیری نلدر مید، ادغام، جهش، نسل، همگرایی، الگوریتم ژنتیک پیوسته، الگوریتم ژنتیک گسسته، بهینه سازی چندمنظوره، بهینه سازی پارتو، ژنتیک مرکب، مسائل جایگشت، غالب و مغلوب، نیچ، متاژنتیک، نژادمانه، رخ مانه، ژنتیک موازی، مسئله فروشنده دوره گرد، طراحی خط سیر روبات، طراحی حرکت رادارگریز، ساخت مدل های معکوس دینامیکی خطی و غیر خطی، مسائل زمان بندی، بهنیه سازی شبکه های عصبی مصنوعی، حل معادلات دیفرانسیل جزئی غیرخطی مرتبه بالا، تابع شایستگی، تابع آزمون، متلب، فرترن، ++C، C