ویرگول
ورودثبت نام
رضا ثقفی
رضا ثقفی
رضا ثقفی
رضا ثقفی
خواندن ۳ دقیقه·۴ سال پیش

الگوریتم چیست؟

برای سؤالات یا مشکلات فقط با مجموعه محدودی از موارد یا مقادیر، یک الگوریتم همیشه وجود دارد (حداقل در اصل). از جدولی از مقادیر پاسخ ها تشکیل شده است. به طور کلی، پاسخ دادن به سؤالات یا مسائلی که تعداد بی‌نهایت موارد یا مقادیری برای در نظر گرفتن دارند، مانند "آیا عدد طبیعی (1، 2، 3،...) عدد اول است؟" یا "بزرگترین مقسوم علیه مشترک اعداد a و b چیست؟" اولین مورد از این سؤالات متعلق به کلاسی به نام decidable است. الگوریتمی که پاسخ بله یا خیر را تولید کند، رویه تصمیم گیری نامیده می شود. سوال دوم متعلق به کلاسی به نام computable است. الگوریتمی که به یک پاسخ عددی خاص منتهی می شود، روش محاسباتی نامیده می شود.

الگوریتم‌ها برای بسیاری از این دسته‌های نامتناهی از سؤالات وجود دارند. عناصر اقلیدس که حدود 300 سال قبل از میلاد منتشر شد، حاوی یکی برای یافتن بزرگترین مقسوم علیه مشترک دو عدد طبیعی بود. هر دانش آموز دبستانی در تقسیم طولانی دریل می شود، که الگوریتمی برای این سوال است که "با تقسیم یک عدد طبیعی a بر عدد طبیعی دیگر b، ضریب و باقیمانده چقدر است؟" استفاده از این روش محاسباتی منجر به پاسخ به سوال قابل تصمیم "آیا b تقسیم a است؟" (اگر باقیمانده صفر باشد، پاسخ مثبت است). استفاده مکرر از این الگوریتم‌ها در نهایت پاسخ این سوال قابل تصمیم را می‌دهد که "آیا عدد اول است؟" (اگر a بر هر عدد طبیعی کوچکتری غیر از 1 بخش پذیر باشد، پاسخ منفی است).

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

الگوریتم
۱
۰
رضا ثقفی
رضا ثقفی
شاید از این پست‌ها خوشتان بیاید