مدل محاسبه: تفاوت میان نسخه‌ها

در [[نظریه رایانش پذیری]] و [[نظریه پیچیدگی محاسباتی]]، '''مدل محاسبه''' تعریف مجموعه‌ای از عملیات‌های قابل قبول مورد استفاده در [[محاسبات]] و نسبت هزینه هایشانهزینه‌هایشان است. برای اندازه‌ گیریاندازه‌گیری پیچیدگی یک [[الگوریتم]] در [[زمان اجرا]] یا حافظهٔ مصرف شده، با فرض مدل خاصی از محاسبات استفاده می‌شود، در تجزیه و تحلیل منابع محاسباتی مورد نیاز بحث کردن در مورد محدودیت‌های [[الگوریتم]] یا [[رایانه‌رایانه]]ها ممکن است.

بعضی از مثال‌ها عبارت اند از [[ماشین تورینگ]]، [[ماشین حالات متناهی]]، , [[توابع بازگشتی]]، [[حساب دیفرانسیل لامبادا]]، [[منطق ترکیبی]] و [[چکیده سیستم بازنویسی]].

در زمینه زمان [[تحلیل الگوریتم‌ها]]، مشخص کردن یک مدل محاسبه در رابطه با عملیات اولیه مجاز دارای [[هزینه واحد]] معمول است. یک مثالی که به طوربه‌طور معمول استفاده می‌شود [[ماشین دستیابی تصادفی]] است، که دارای [[ارزش واحد]] برای خواندن و نوشتن دستیابی به همهٔ خانه‌های حافظه است. از این منظر، با ماشین تورینگی که در بالا گفته شده استشده‌است تفاوت دارد.

یک نکته اصلی که اغلب چشم پوشی می‌شود این است که حدود پایین منتشر شده برای مشکل‌ها در بیشتر مواقع برای یک مدل محاسباتی بیشتر محدود می‌شوند تا مجموعه عملیاتی که کسی می‌تواند استفاده کند در پرداختن و از این رو ممکن است الگوریتم‌هایی سریع تر از آنچه به سادگی فکر می‌کردیم وجود داشته باشد. <ref>cstheory.stackexchange.com</ref>

مدل محاسباتی بسیاری وجود دارد که در مجموعه اعمال مجاز و هزینه محاسباتشان تفاوت می‌کنند. آن‌ها به گروه گستردهٔ زیر تعلق دارند: [[ماشین انتزاعی]] و مدل‌های معادل آن (برای مثال حساب دیفرانسیل لامبادا معادل با [[ماشین تورینگ]] است) در اثبات‌های شمارش پذیری و حدود بالا روی پیچیدگی محاسباتی الگوریتم‌ها استفاده می‌شود، و [[مدل‌های درخت تصمیم گیریتصمیم‌گیری]]، در اثبات‌های حدود پایین روی پیچیدگی محاسباتی مشکل‌های الگوریتمی استفاده می‌شود.

== مطالعهبرای مطالعهٔ بیشتر ==

== منابع ==