بشر در طول زندگی خود با مشکلات بسیاری مواجه میشود که ممکن است بسیاری از آنها بارها تکرار شوند. برای حل کردن مشکلاتی که چندین بار با آنها مواجه شدهایم، ثبت و دستهبندی راه حلهای مشخص کمک میکند که بتوانیم سریعتر و مطمئنتر با مسائل تکراری برخورد کنیم. ما به این راه حلهای تستشده و مطمئن، الگوریتم میگوییم. در این مطلب یاد میگیریم که الگوریتم چیست و در برنامه نویسی چه مفهومی دارد و با انواع آن آشنا میشویم.
ما معمولاً برای حل مشکلات به دنبال سادهترین و سریعترین راهحلها هستیم. سالها است که علم با یافتن پاسخ سؤالات خود و استفاده از آنها در پیشامدهایی که الگوی تکراری دارند، اهداف خود را پیش میبرد و سریعتر از انتظار ما رازهای طبیعت را از دل آن بیرون میکشد. راهحلهایی که تستشده و مطمئن هستند و میتوانند سوالاتی با مفاهیم یکسان را حل کنند، الگوریتم نامیده میشوند. ریشه کلمه الگوریتم از نام خوارزمی دانشمند ایرانی به دست آمده است.
اگر بخواهیم معنی الگوریتم را در زمینه ریاضیات و علوم کامپیوتر بررسی کنیم، میتوان گفت الگوریتمها مجموعه فرایندهایی هستند که به کمک آنها میتوان بسیاری از مسائل برنامهنویسی را بهراحتی حل کرد. بهعنوانمثال الگوریتم یک موتور جستجو را در نظر بگیرید. الگوریتم موتور جستجو گوگل بهطور ساده اینگونه ست که عبارت تایپ شده شما را دریافت کرده و آن را در پایگاه دادههای خود جستجو میکند.
سپس صفحات وب مربوطه را پیداکرده و به شما نشان میدهد. این روند کلی از ایجاد سؤال تا رسیدن به پاسخ یک الگوریتم محسوب میشود. استفاده از الگوریتمها در کاهش هزینههای مالی و زمانی یک پروژه اهمیت زیادی دارد. الگوریتمها با انجام سلسله اقدامات مشخصی و در ازای گرفتن ورودی تعریفشده، نتیجهای مطابق انتظار به ما خواهند داد.
الگوریتمها با توجه به ساختار منطقی که دارند در 3 دسته جا میگیرند:
الگوریتمها دارای نقش مهمی در برنامهنویسی و حل مسئله هستند و از لحاظ کارایی و با توجه به نوع مسئله انواع مختلفی دارند که ما در این بخش به بررسی تعدادی از آنها میپردازیم.
الگوریتمهای بازگشتی حالت پایه یا به اصطلاح base case مسئله را حل کرده و سپس با استفاده از این جواب، به حل مسائل تودرتو میپردازند. درواقع مسئله به چند بخش کوچک شکسته میشود که با استفاده از پاسخ مرحله قبل، مسئله بعدی قابلحل است. یکی از معروفترین مسائل بازگشتی، تابع فاکتوریل (factorial) است. در کد زیر عبارت If x is 0 حالت پایه محسوب میشود:
Fact(x) If x is 0 return 1 return (x*Fact(x-1))
از الگوریتمهای پویا یا دینامیک میتوان برای محاسبه بخشی از برنامه و استفاده از پاسخ آن، در مسائل آینده استفاده کرد. یعنی از پاسخهای یک بخش، میتوانید برای حل مسائل دیگر نیز بهره برد. دنباله فیبوناچی از الگوریتمهای دینامیک استفاده میکند:
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
الگوریتم عقبگرد به دنبال پیدا کردن سرنخهای امیدبخشی است تا بهینهترین جواب را پیدا کند. این شیوه برای حل مسائل درخت فضای آن مسئله را ایجاد کرده و تعیین میکند کدام گره امیدبخش است. الگوریتمهای عقبگرد از علامتهایی برای بیان اینکه یک راهحل کاندید به حل مسئله نمیانجامد استفاده میکنند.
مثلاً در ساخت درخت فضای حالت یک سؤال، اگر شاخهای از درخت جواب بهینهای در پی نداشته باشد، علامتگذاری میشود تا در عمق زیاد بررسی نشود و به جای آن، شاخه امیدبخشتر بررسی میشود. البته شاخه اول بهطورکلی هرس نمیشود بلکه موقتاً کنار گذاشته میشود تا در صورت پیدا نکردن بهینهترین جواب در شاخه دیگر، مجدداً به آن بازگردیم.
الگوریتمهای تقسیم و حل ابتدا مسئله را با توجه به نوع آن، چند بخش کوچکتر تقسیم کرده و به حل آنها میپردازند. سپس از ترکیب پاسخ بخشهای کوچکتر، پاسخ کلی مسئله بهدست میآید. برخی از روشهای مرتبسازی مانند مرتبسازی ادغامی (Merge Sort) و مرتبسازی سریع (Quick Sort) نیز از این دسته الگوریتمها محسوب میشوند.
بهعنوان مثال مرتبسازی ادغامی ابتدا آرایهای از مقادیر ورودی را دو قسمت کرده و بهصورت بازگشتی، دوباره هر قسمت را دو قسمت میکند. این روند آنقدر ادامه پیدا میکند تا اعداد در دستههای کوچکتر صعودی یا نزولی مرتب شوند. سپس از ادغام زیر بخش های کوچک، آرایه مرتبشدهی بخشهای بزرگتر به دست میآید.
الگوریتمهای حریصانه به دنبال جستجوی بهینهترین پاسخ ممکن هستند اما لزوماً در هر مسئلهای، نمیتوانند بهینهترین پاسخ را پیدا کنند اما یکی از جوابهای بهینه را به شما معرفی خواهند کرد. البته برخی مسائل هم بهطورکلی پاسخ بهینه ندارند که به آنها مسائل NP complete میگویند. در شیوه حریصانه در هر مرحله عنصری که بر مبنای معیارها بهترین به نظر میرسد، بدون توجه به انتخابهایی که قبلاً انجام شده یا در آینده انجام خواهد شد، انتخاب میشود.
مسئله خرد کردن سکهها یکی از مثالهای معروف در بهکارگیری الگوریتم حریصانه است. این مسئله میگوید فرض کنید که شما باید مبلغی مثلاً 36 تومان را با سکههای 20 تومانی، 10 تومانی، 5 تومانی و 1 تومانی پرداخت کنید به طوری که کمترین تعداد سکه را بپردازید. کمترین تعدادی که بتوان با آن 36 تومان را پرداخت کرد پاسخی بهینه برای مسئله ما خواهد بود که در اینجا، برداشتن یک سکه از هر 4 مدل است.
الگوریتم جستجوی جامع یا بروت فورس تمامی راهحلهای احتمالی را بررسی میکند تا بتواند بهینهترین پاسخ را پیدا کند. در این الگوریتم بهینهترین پاسخ با ویژگی “ارضا کردن شرط مسئله” سنجیده میشود و به همین دلیل بیشتر برای مسائل کوچک کاربرد دارد. این الگوریتم در رمزگشایی نیز کاربرد زیادی دارد و عملکرد آن بهگونهای است که تمامی کلیدها را چک میکند تا به جواب برسد. دادهکاوی نیز زمینه دیگری برای استفاده از این نوع الگوریتمها است.
در این مقاله به صورت کامل به این پرسش پرداختیم که الگوریتم چیست و به معرفی انواع الگوریتمها پرداختیم ، در این قسمت میخواهیم بگوییم الگوریتم چه کاربردی دارد ؟ در زیر به برخی از کاربردهای الگوریتمها اشاره میکنیم:
الگوریتمهای کاربردی زیادی در ریاضیات و علوم کامپیوتر وجود دارند که ما بهطور خلاصه به معرفی تعدادی از آنها پرداختیم. تسلط بر الگوریتم ها اهمیت زیادی برای برنامه نویسان و بهویژه Back-End کارها دارد زیرا میتواند نقطه قوتی برای استخدام در شرکتهای معتبر باشد. فلوچارتها و الگوریتمها ازجمله پیشنیازهای یادگیری برنامهنویسی هستند.