محدودیت‌ها محاسبات
ترجمهٔ عنوان این مقاله دارای منبع نیست. ویرایشگران طبق سیاست تحقیق دستاول ممنوع نمی‌توانند اصطلاحات زبانهای دیگر را بدون منبع ترجمه کنند و از طرف دیگر بر اساس شیوهنامه در اکثر مواقع نمی‌توانند عنوان مقاله را با عنوان اصلی آن در الفباهای غیر فارسی و عربی ثبت کنند. |
پیدا کردن محدودیت‌های محاسبات نیازمند تعریفی دقیق از چیستی محاسبات است. منشا چیزی که امروز به عنوان نظریه_محاسبات می‌شناسیم به آلن_تورینگ ریاضی‌دان بریتانیایی برمی گردد که تعریفی از فعل محاسبه کردن ارائه داد. او که دستگاه محاسباتی که امروز به نام ماشین_تورینگ شناخته می‌شود را معرفی کرد، نشان داد که طبق تعریف او قطعاً حداقل یک تابع وجود دارد که نمی‌تواند در روش محاسبات پیشنهاد شده محاسبه شود. برای پیدا کردن محدودیت‌های محاسبات قدم اول پیدا کردن مسائلی است که حتی نمیتوان آن‌ها را در زمان و حافظه نامحدود محاسبه کرد.
سوالی که مطرح می‌شود این است که چه مسائلی را می‌توان در زمان و یا حافظه محدود محاسبه کرد که بر این اساس کلاس‌های مختلف پیچیدگی مسائل شکل می‌گیرند. در واقع پیچیدگی محاسبات را می‌توان مطالعه مسائل و دسته‌بندی آن‌ها بر این اساس که در مقیاس زمان و حافظه، یک مساله چه قدر سخت می‌تواند باشد نامید.
مهم‌ترین کلاس‌های پیچیدگی بر اساس زمان
ویرایش- P: مساله‌هایی که حل آن‌ها در زمان چند جمله‌ای امکان‌پذیر است.
- NP: مجموعه‌ای از مساله‌های تصمیم هستند که در زمان چند جمله‌ای می‌توان به آن‌ها پاسخ بله داد.
مهم‌ترین کلاس‌های پیچیدگی حافظه
ویرایش- PSPACE: مساله‌هایی هستند که با استفاده از حافظه چند جمله‌ای می‌توان آن‌ها را حل کرد.
- NL: مجموعه‌ای است از مساله‌های تصمیم که می‌توان آن‌ها را بایک ماشین تورینگ غیر قطعی با استفاده از حافظه لگاریتمی حل کرد.
به‌طور معمول وقتی در مورد محدودیت‌های محاسبات پرسیده می‌شود ذهن افراد به سمت محدودیت‌های دستگاهی که برای انجام محاسبه استفاده می‌شود، می‌رود. محدودیت‌هایی که می‌تواند در این زمینه وجود داشته باشد می‌توانند از انواع مختلفی باشند:
- محدودیت‌های ساخت قطعات: محدودیت‌هایی در قرار دادن در قرار دادن مواد روی سیلیکون در مقیاس بسیار کوچک با استفاده از تکنولوژی حاضر لیتوگرافی در نانوتکنولوژی وجود دارد که البته پیش‌بینی می‌شود در آینده پیشرفت‌هایی در این زمینه انجام گیرد.
- محدودیت‌های اتصال: سیم‌های فلزی می‌توانند سریع یا با ظرفیت باشند اما نمی‌توانند هم زمان هر دو باهم باشند.
- محدودیت‌های ترانزیستورها: ترانزیستورها به دلیل ضخامت دی الکتریک خود دارای محدودیت هستند، چرا که در حال حاضر ضخامت دی الکتریک به مقیاس اتم رسیده‌است و از حدی کمتر نمی‌شود. این باعث محدودیت در ساخت پردازنده‌های قوی تر می‌شود.
- محدودیت‌های طراحی: با توجه به افزایش پیچیدگی مدارهای مجتمع برای رسییدن به سرعت بیشتر و توان مصرفی کمتر استفاده از طراحی به کمک کامپیوتر(CAD) غیرقابل اجتناب است و هر طراحی جدید نیاز به ابزار CAD جدید دارد. در نتیجه الگوریتم‌های هوشمندانه برای بهره وری بهتر مورد نیاز است و محدودیت‌های نرم‌افزارهای CAD تأثیر مستقیم بر محدودیت محاسبات خواهد داشت.