نظریه رایانش‌پذیری: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جزبدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۳:
'''نظریه محاسبه‌پذیری''' از مباحث پایه در [[علوم رایانه]] است که به بررسی محاسبه‌پذیر و محاسبه‌ناپذیر بودن عملیات با استفاده از ابزارهای کلاسیک نظیر [[ماشین ثبات]]، [[ماشین تورینگ]] و [[توابع بازگشتی]] میپردازد.
بدون شك يكي از علل پيشرفت اين نظريه تلاش محققين براي اثبات پاسخ منفي به مساله دهم هيلبرت بوده است.
دانشمندان کامپیوتر، برای مطالعه ی جدی نظریه رایانش( شماره پذیری)، با یک مفهوم انتزاعی ریاضی برای کامپیوترها که مدل رایانش گفته می شود، سر و کار دارند. قاعده سازی های متعددی، برای استفاده وجود دارد، اما ماشین ترینگ( Turing ) در این میان بیش ترین کاربرد را دارد. یک ماشین ترینگ را می توان هم ارز یک کامپیتر شخصی رومیزی، در نظر گرفت، با حافظه ی بی نهایت که به این حافظه از طریق تعداد زیادی تکه های کوچک گسسته، دسترسی دارد. دانشمندان کامپیوتر به دلیل قابلیت سادگی قاعده سازی، تحلیل و آنالیز و قابل استفاده برای اثبات نتایج از این ماشین استفاده می کنند.
چون حافظه ی بی نهایت یک نسبت غیر مادی در نظر گرفته می شود، برای هر مسئله که با استفاده از ماشین ترینگ حل می شود، حافظه ی مورد استفاده همواره محدود است. در نتیجه هر مسئله را می توان با استفاده از یک کامپیوتر شخصی که حافظه ی مورد نیاز بر روی آن نصب شده، از طریق یک ماشین ترینگ حل کرد.
==نظریه شماره پذیری==
نظریه شماره پذیری، با این سوال که آیا یک مسئله قابل حل بر روی یک کامپیوتر هست یا نه، سر و کار دارد. مسئله ی halting یکی از مهم ترین نتایج در نظریه ی شماره پذیری است. این مسئله به آسانی قابل قاعده سازی و به سختی با استفاده از ماشین ترینگ قابل حل است! بخش عمده ای از نظریه ی شماره پذیری، بر نتیجه ی مسئله ی halting، استوار است.
نظریه ی شماره پذیری، با یک شاخه از منطق ریاضی به نام نظریه ی بازگشت، در ارتباط تنگاتنگ است. بسیاری از ریاضی دانان و نظریه پردازان شمارش پذیری، که درباره ی نظریه ی بازگشت به مطالعه می پردازند، این نظریه را در آخر به نظریه ی شماره پذیری ارجاع می دهند.
==نظریه پیچیدگی==
نظریه ی پیچیدگی، نه تنها با این موضوع که آیا مسئله ی مطرح شده بر روی کامپیوتر قابل حل هست یا نه؛ بلکه با این موضوع که چقدر مسئله می تواند به صورت کارآمد حل شود، در ارتباط است. دو جنبه ی مهم در این نظریه مطرح است: پیچیدگی زمان و پیچیدگی فضا. یعنی برای حل مسئله چند پله باید طی شود و به چقدر حافظه نیاز است.
برای تحلیل این که یک الگوریتم به چقدر زمان و حافظه نیاز دارد، دانشمندان کامپیوتر زمان و حافظه ای را که برای حل یک مسئله مورد نیاز است، به عنوان یک تابع از سایز ورودی مسئله بیان می کنند. برای مثال پیدا کردن یک عدد خاص در یک لیست بلند از اعداد دشوارتر می شود هنگامی که تعداد اعداد افزایش می یابد.
{{ریاضی-خرد}}
| |||