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

نظریهٔ محاسبات یا تئوری محاسبات (به انگلیسی: Theory of computation) زمینهٔ وسیعی است که امکان و کارایی حل مسائل گوناگون به وسیلهٔ مدل‌های محاسباتی، با استفاده از الگوریتم‌ها را مورد مطالعه قرار می‌دهد.

این نظریه را به دو شاخهٔ عمده به‌صورت زیر تقسیم می‌کنند:

  • نظریهٔ محاسبه‌پذیری یا قابلیت محاسبه
  • نظریهٔ پیچیدگی

هر دو شاخهٔ فوق با مدل‌های صوری محاسبات سر وکار دارد.

تاریخچه

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

این نظریه را به دو شاخهٔ عمده به صورت زیر تقسیم می‌کنند:

  • نظریهٔ محاسبه‌پذیری یا قابلیت محاسبه
  • نظریهٔ پیچیدگی

هر دو شاخهٔ یادشده در بالا با مدل‌های صوری محاسبات سروکار دارد.

به منظور انجام یک مطالعه دقیق از محاسبات دانشمندان رایانه با انتزاع ریاضی رایانه به عنوان یک مدل محاسبه کار می‌کنند.

مدل‌های بسیاری در این زمینه وجود دارد ولی معمولاً مدل مورد بررسی ماشین تورینگ است.

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

ظرفیت حافظه به‌طور بالقوه بی‌نهایت یک ویژگی غیرمیسر است در حالی که تصمیم‌های ماشین تورینگ نیاز به تنها مقدار محدودی از حافظه دارد.

بنابرین هرمشکل که می‌تواند حل شود. تصمیم یک ماشین تورینگ را می‌توان با یک رایانه که دارای یک مقدار محدود از حافظه است حل کرد.

شاخه‌ها

نظریهٔ ماشین‌ها

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

نظریهٔ زبان رسمی

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

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

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

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

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

مدل‌های محاسبات

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

جستارهای وابسته
در ویکی‌کتاب کتابی با عنوان: حل تمرین نظریه محاسبات وجود دارد.

پانویس
    • Sudkamp, T. A. , An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed. , Pearson Education, Inc. , 2006. ISBN 0-321-32221-5
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.