الگوریتم؛ نقشه راه گام به گام از یک مسئله تا راهحل
الگوریتم چیست و چه ویژگیهایی دارد؟
الگوریتم[1] را میتوان به دستور پخت یک غذا تشبیه کرد. همانطور که دستور پخت مشخص میکند ابتدا چه موادی را آماده کنید، سپس چگونه آنها را مخلوط کنید و در نهایت با چه دما و مدتی بپزید، الگوریتم نیز گامهای دقیق و مشخصی را برای رسیدن از وضعیت اولیه (مسئله) به وضعیت نهایی (پاسخ) تعیین میکند. برای نمونه، الگوریتم جمع دو عدد اعشاری را در نظر بگیرید: ابتدا ارقام را از راست به چپ زیر هم بنویسید، سپس هر ستون را جمع کنید، اگر حاصل از 9 بیشتر شد، یکی را به ستون بعدی حمل کنید و در نهایت مجموع را بنویسید.
یک الگوریتم استاندارد باید پنج ویژگی اصلی را داشته باشد:
۱) ورودیها: مقداری که الگوریتم از بیرون دریافت میکند (میتواند صفر یا چند ورودی باشد).
۲) خروجیها: حداقل یک نتیجه که پس از اجرا تولید میشود.
۳) قطعی بودن: هر گام باید بدون ابهام و دقیق باشد.
۴) متناهی بودن: الگوریتم پس از تعداد محدودی گام به پایان برسد.
۵) کارایی: با منابع موجود (زمان و حافظه) قابل اجرا باشد.
روشهای نمایش الگوریتم و ساختارهای پایه
برای نوشتن یک الگوریتم از سه روش اصلی استفاده میشود: بیان گام به گام به زبان طبیعی (مانند دستورالعمل مونتاژ یک میز تحریر)، شبهکد (ترکیبی از زبان طبیعی و ساختارهای برنامهنویسی) و نمودار جریان (نمایش گرافیکی با شکلهای استاندارد مانند بیضی برای شروع و پایان، متوازیالاضلاع برای ورودی/خروجی، مستطیل برای پردازش و لوزی برای شرط). در ادامه با سه ساختار پایهٔ هر الگوریتم آشنا میشوید:
- ساختار ترتیبی (توالی): گامها یکی پس از دیگری و به ترتیب اجرا میشوند. مثال: در الگوریتم پخت کیک، ابتدا تخممرغ را میشکنیم، بعد آرد را الک میکنیم و سپس مواد را مخلوط میکنیم.
- ساختار شرطی (انتخاب): بر اساس درستی یا نادرستی یک شرط، مسیر اجرا تغییر میکند. مثال: «اگر دمای فر به 180 درجه رسیده بود، خمیر را داخل فر بگذار؛ در غیر این صورت 5 دقیقه دیگر صبر کن.»
- ساختار تکراری (حلقه): یک یا چند گام به تعداد مشخص یا تا زمانی که شرطی برقرار است، تکرار میشوند. مثال: «تا زمانی که تخممرغها پخته نشدهاند، هر 1 دقیقه یک بار آنها را بچرخان.»
| نوع ساختار | توضیح | مثال در زندگی روزمره |
|---|---|---|
| ترتیبی | اجرای خطی گامها از بالا به پایین | دستورالعمل روشن کردن تلویزیون: دکمه پاور را بزن، سپس کانال مورد نظر را انتخاب کن. |
| شرطی | انتخاب بین دو یا چند مسیر بر اساس یک شرط | اگر باران میبارد چتر بردار؛ در غیر این صورت عینک آفتابی بزن. |
| تکراری | تکرار بلوکی از دستورات تا رسیدن به شرط خاتمه | تا زمانی که قوری سوت نزد، به جوشیدن ادامه بده. |
کاربرد عملی: الگوریتم اقلیدس برای بزرگترین مقسومعلیه مشترک
یکی از قدیمیترین و زیباترین الگوریتمهای ریاضی، الگوریتم اقلیدس[2] برای یافتن بزرگترین مقسومعلیه مشترک (ب.م.م)[3] دو عدد صحیح مثبت است. این الگوریتم که بیش از 2300 سال پیش توسط ریاضیدان یونانی اقلیدس ارائه شد، همچنان یکی از کارآمدترین روشها محسوب میشود. گامهای آن به زبان ساده عبارتند از:
- دو عدد a و b را با شرط a \gt b در نظر بگیر.
- اگر b = 0 آنگاه خروجی برابر a است و الگوریتم پایان مییابد.
- در غیر این صورت، باقیماندهٔ تقسیم a بر b را محاسبه کن (فرض کن r = a \mod b).
- مقدار a را برابر b و مقدار b را برابر r قرار بده.
- به گام شماره 2 برگرد (تکرار کن).
برای مثال، ب.م.م اعداد a = 48 و b = 18 را محاسبه میکنیم: باقیمانده 48 \div 18 برابر 12 است (48 = 2 \times 18 + 12). حالا a=18 , b=12 میشود. باقیمانده 18 \div 12 برابر 6. سپس a=12 , b=6. باقیمانده 12 \div 6 برابر 0. از آنجا که b=0 شد، خروجی برابر a = 6 است. بنابراین ب.م.م (48,18) = 6.
چالشهای مفهومی در درک الگوریتم
خیر. یک دستورالعمل صرفاً گامبهگام بودن کافی نیست، باید دارای ویژگی «قطعی بودن» و «متناهی بودن» نیز باشد. برای نمونه دستور «عددی را حدس بزن و آنقدر این کار را تکرار کن تا به پاسخ برسی» الگوریتم نیست چون مشخص نیست چه عددی را حدس بزنی و تضمینی برای پایان یافتن وجود ندارد.
الگوریتم یک مفهوم مستقل از زبان برنامهنویسی است، در حالی که برنامه پیادهسازی مشخصی از یک الگوریتم به زبان برنامهنویسی خاص (مانند پایتون یا جاوا) محسوب میشود. یک الگوریتم واحد را میتوان به زبانهای مختلف برنامهنویسی ترجمه کرد. به بیان دیگر، الگوریتم نقشه است و برنامه ساختمانی که بر اساس آن نقشه ساخته شده.
الگوریتمها از نظر کارایی با هم تفاوت دارند. گاهی الگوریتمی با گامهای بیشتر اما در عمل سریعتر اجرا میشود (مانند مرتبسازی سریع نسبت به مرتبسازی حبابی). همچنین برای مسائل کوچک، الگوریتم پیچیده ممکن است کندتر از روش مستقیم باشد. انتخاب الگوریتم مناسب به اندازهٔ داده و منابع موجود بستگی دارد. برای نمونه، فرمول بستهٔ مجموع اعداد از 1 تا n بسیار سریعتر از حلقه با n بار تکرار است.
پاورقیها
[1] الگوریتم (Algorithm): مجموعهای از دستورالعملهای گامبهگام و متناهی که برای حل یک مسئله یا انجام یک کار مشخص تدوین میشود. واژهٔ الگوریتم از نام ریاضیدان ایرانی «خوارزمی» گرفته شده است.
[2] الگوریتم اقلیدس (Euclidean Algorithm): روشی بازگشتی برای یافتن بزرگترین مقسومعلیه مشترک دو عدد که بر اساس اصل «باقیماندهٔ تقسیم» کار میکند.
[3] بزرگترین مقسومعلیه مشترک (Greatest Common Divisor - GCD): بزرگترین عدد صحیح مثبتی که هر دو عدد داده شده بر آن بخشپذیر باشند.