الگوریتم چیست؟ بررسی مفهوم الگوریتم های مهم در برنامه نویسی

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

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

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

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

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

ساختار منطقی الگوریتم‌ها چیست؟

الگوریتم‌ها با توجه به ساختار منطقی که دارند در 3 دسته جا می‌گیرند:

• دنباله ای (Sequence): ساختاری مرحله به مرحله، که ترتیب گام‌ها برای رسیدن به پاسخ در آن مشحص است.
• شاخه ای(Branching): این الگوریتم‌ها طبق قانون اگر-آنگاه در ریاضیات کار می‌کنند. به این صورت که پس از تعیین شرط، پاسخ با توجه به نتیجه شرط تعیین می‌شود.
• حلقه ای (Loop): الگوریتم‌های حلقه ای یا تکراری، در تعداد دفعات مشخصی شرطی را در پروژه اعمال می‌کنند و پس از تمام شدن فرایند، برنامه را پایان می‌دهند.

انواع الگوریتم‌ها از نظر نوع مسئله

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

الگوریتم بازگشتی (Recursive)

الگوریتم‌های بازگشتی حالت پایه یا به اصطلاح base case مسئله را حل کرده و سپس با استفاده از این جواب، به حل مسائل تودرتو می‌پردازند. درواقع مسئله به چند بخش کوچک شکسته می‌شود که با استفاده از پاسخ مرحله قبل، مسئله بعدی قابل‌حل است. یکی از معروف‌ترین مسائل بازگشتی، تابع فاکتوریل (factorial) است. در کد زیر عبارت If x is 0 حالت پایه محسوب می‌شود:

Fact(x)
    If x is 0    
       return 1
     return (x*Fact(x-1))

الگوریتم دینامیک (Dynamic)

از الگوریتم‌های پویا یا دینامیک می‌توان برای محاسبه بخشی از برنامه و استفاده از پاسخ آن، در مسائل آینده استفاده کرد. یعنی از پاسخ‌های یک بخش، می‌توانید برای حل مسائل دیگر نیز بهره برد. دنباله فیبوناچی از الگوریتم‌های دینامیک استفاده می‌کند:

Fib(n)
    if n=0
	    return 0
	else
	    prev_Fib=0,curr_Fib=1
	repeat n-1 times  /*if n=0 it will skip*/
	    next_Fib=prev_Fib+curr_Fib   
	    prev_Fib=curr_Fib
	    curr_Fib=new_Fib
	return curr_Fib

الگوریتم برگشت به عقب (Backtracking)

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

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

الگوریتم تقسیم و حل (Divide and conquer )

الگوریتم‌های تقسیم و حل ابتدا مسئله را با توجه به نوع آن، چند بخش کوچک‌تر تقسیم کرده و به حل آن‌ها می‌پردازند. سپس از ترکیب پاسخ بخش‌های کوچک‌تر، پاسخ کلی مسئله به‌دست می‌آید. برخی از روش‌های مرتب‌سازی مانند مرتب‌سازی ادغامی (Merge Sort) و مرتب‌سازی سریع (Quick Sort) نیز از این دسته الگوریتم‌ها محسوب می‌شوند.

به‌عنوان مثال مرتب‌سازی ادغامی ابتدا آرایه‌ای از مقادیر ورودی را دو قسمت کرده و به‌صورت بازگشتی، دوباره هر قسمت را دو قسمت می‌کند. این روند آن‌قدر ادامه پیدا می‌کند تا اعداد در دسته‌های کوچک‌تر صعودی یا نزولی مرتب شوند. سپس از ادغام زیر بخش های کوچک، آرایه مرتب‌شده‌ی بخش‌های بزرگ‌تر به‌ دست می‌آید.

الگوریتم حریصانه (Greedy)

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

مسئله خرد کردن سکه‌ها یکی از مثال‌های معروف در به‌کارگیری الگوریتم حریصانه است. این مسئله می‌گوید فرض کنید که شما باید مبلغی مثلاً 36 تومان را با سکه‌های 20 تومانی، 10 تومانی، 5 تومانی و 1 تومانی پرداخت کنید به طوری که کمترین تعداد سکه را بپردازید. کمترین تعدادی که بتوان با آن 36 تومان را پرداخت کرد پاسخی بهینه برای مسئله ما خواهد بود که در اینجا، برداشتن یک سکه از هر 4 مدل است.

الگوریتم بروت فورس (Brute force)

 الگوریتم جستجوی جامع یا بروت فورس تمامی راه‌حل‌های احتمالی را بررسی می‌کند تا بتواند بهینه‌ترین پاسخ را پیدا کند. در این الگوریتم بهینه‌ترین پاسخ با ویژگی “ارضا کردن شرط مسئله” سنجیده می‌شود و به همین دلیل بیشتر برای مسائل کوچک کاربرد دارد. این الگوریتم در رمزگشایی نیز کاربرد زیادی دارد و عملکرد آن به‌گونه‌ای است که تمامی کلیدها را چک می‌کند تا به جواب برسد. داده‌کاوی نیز زمینه دیگری برای استفاده از این نوع الگوریتم‌ها است.

جمع بندی

الگوریتم‌های کاربردی زیادی در ریاضیات و علوم کامپیوتر وجود دارند که ما به‌طور خلاصه به معرفی تعدادی از آن‌ها پرداختیم. تسلط بر الگوریتم ها اهمیت زیادی برای برنامه نویسان و به‌ویژه Back-End کارها دارد زیرا می‌تواند نقطه قوتی برای استخدام در شرکت‌های معتبر باشد. فلوچارت‌ها و الگوریتم‌ها ازجمله پیش‌نیازهای یادگیری برنامه‌نویسی هستند.