بشر در طول زندگی خود با مشکلات بسیاری مواجه میشود که ممکن است بسیاری از آنها بارها تکرار شوند. برای حل کردن مشکلاتی که چندین بار با آنها مواجه شدهایم، ثبت و دستهبندی راه حلهای مشخص کمک میکند که بتوانیم سریعتر و مطمئنتر با مسائل تکراری برخورد کنیم. ما به این راه حلهای تست شده و مطمئن، الگوریتم میگوییم. در این مطلب یاد میگیریم که الگوریتم چیست و در برنامه نویسی چه مفهومی دارد و با انواع آن آشنا میشویم.
ما اغلب برای حل مشکلات به دنبال سادهترین و سریعترین راهحلها هستیم. سالها است که علم با یافتن پاسخ سؤالات خود و استفاده از آنها در پیشامدهایی که الگوی تکراری دارند، اهداف خود را پیش میبرد و سریعتر از انتظار ما رازهای طبیعت را از دل آن بیرون میکشد. راهحلهایی که تست شده و مطمئن هستند و میتوانند سوالاتی با مفاهیم یکسان را حل کنند، الگوریتم نامیده میشوند.
اگر بخواهیم معنی الگوریتم را در زمینه علوم کامپیوتر بررسی کنیم، میتوان گفت الگوریتمها مجموعه فرایندهایی هستند که به کمک آنها میتوان بسیاری از مسائل برنامهنویسی را بهراحتی حل کرد. به عنوان مثال الگوریتم یک موتور جستجو را در نظر بگیرید. الگوریتم موتور جستجو گوگل بهطور ساده اینگونه است که عبارت تایپ شده شما را دریافت کرده، آن را در پایگاه دادههای خود جستجو میکند و سپس صفحات وب مربوطه را پیداکرده و به شما نشان میدهد. این روند کلی از ایجاد سؤال تا رسیدن به پاسخ یک الگوریتم محسوب میشود. استفاده از الگوریتمها در کاهش هزینههای مالی و زمانی یک پروژه اهمیت زیادی دارد. الگوریتمها با انجام سلسله اقدامات مشخصی و در ازای گرفتن ورودی تعریف شده، نتیجهای مطابق انتظار به ما خواهند داد.
جالب است بدانید که ریشه کلمه الگوریتم از نام خوارزمی دانشمند ایرانی به دست آمده است. خوارزمی در قرن دوم هجري شمسي در دوره مامون عباسي زندگی میکرد. از آنجایی که زبان آن دوره عربي بود از اين رو خوارزمي را به صورت الخوارزمي صدا ميزدند.
روش دانشمند ايراني؛ در عمليات جمع و تفريق، ضرب و تقسيم مورد توجه دانشمندان رياضي اروپا قرار گرفت و خوارزمي در محاسبات چهار عمل اصلي و حل انواع مسايل رياضي روش مرحله به مرحله و دقيقي ارائه داده بود و در نهايت به جواب منجر ميشد. به همين خاطر از آن به بعد، هر روشي را که حل مسايل را به صورت مرحله به مرحله و دقيق و با جزئيات کافي بيان کند و در پايان به جواب برسد روش الگوريتمي ناميدند. کلمه الگوریتم از تلفظ لاتيني الخوارزمي به صورت Algorism يا الگوريتمي Algorithmic به دست آمده است.
تا به اینجا در این مقاله به صورت کامل به این پرسش پرداختیم که الگوریتم چیست، در این قسمت میخواهیم بگوییم الگوریتم چه کاربردی دارد؟ در زیر به برخی از کاربردهای الگوریتمها اشاره میکنیم:
تمامی الگوریتمها در هنگام طراحی باید معیارهای زیر را رعایت کنند تا بتوانند به جواب درستی برسند:
صرفاً نوشتن توالی دستورالعملها به عنوان یک الگوریتم برای انجام یک کار خاص کافی نیست. داشتن ویژگیهای زیر در ارتباط با یک الگوریتم ضروری است:
الگوریتمها با توجه به ساختار منطقی که دارند در 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 مدل است.
الگوریتم جستجوی جامع یا بروت فورس تمامی راهحلهای احتمالی را بررسی میکند تا بتواند بهینهترین پاسخ را پیدا کند. در این الگوریتم بهینهترین پاسخ با ویژگی “ارضا کردن شرط مسئله” سنجیده میشود و به همین دلیل بیشتر برای مسائل کوچک کاربرد دارد. این الگوریتم در رمزگشایی نیز کاربرد زیادی دارد و عملکرد آن بهگونهای است که تمامی کلیدها را چک میکند تا به جواب برسد. دادهکاوی نیز زمینه دیگری برای استفاده از این نوع الگوریتمها است.
فلوچارت یا روندنما، نموداری است که یک فرآیند، یک سیستم یا یک الگوریتم کامپیوتری را به صورت تصویری نشان میدهد. این نمایش نموداری یکی از راه حل مسئله است و تجزیه و تحلیل مراحل ضروری برای حل مسئله را ارائه میدهد. این مفهوم برای اولین بار در سال 1921 به عنوان نمودار فرآیند جریان برای اعضای انجمن مهندسین مکانیک آمریکا معرفی شد و در محاسبات اولیه در دهه 50 بسیار محبوبیت گردید.
به یاد داشته باشید که فلوچارت فقط توضیح میدهد که در هر مرحله چه اتفاقی باید بیفتد، چه ورودی لازم است و خروجی آن مرحله چیست، اما چیزی در مورد نحوه اجرای مرحله نمیگوید. هنگامی که یک فلوچارت رسم میشود، به یافتن ویژگیهای کمتر آشکار فرآیند کمک میکند و سپس میتواند برای بهبود کارایی آن اصلاح شود، مانند نقص ها، مراحل غیر ضروری، نقاط خطاخیز و…. یک فلوچارت باید به عنوان یک نمودار تکامل یافته دیده شود.
اگر تعداد دستورات زیاد شود ایجاد الگوریتم کار آسانی نخواهد بود و باعث ایجاد بینظمی و اشتباه خواهد شد، در چنین مواقعی باید طرح خود را در قالب فلوچارت یا روندنما ارائه کنید.
فلوچارت علاوه بر این که روند کلی طرح را در قالب نمودار نمایش میدهد از اعتبار بیشتری نیز برخوردار است و همچنین امکان به وجود آمدن خطا را به حداقل میرساند. هنگام طراحی و برنامه ریزی یک فرآیند، فلوچارتها میتوانند به شما در شناسایی مراحل مهم کمک کنند و همزمان تصویر بزرگتری از آنچه را که در حال انجام است ارائه دهند. فلوچارت وظایف را به ترتیب زمانی سازماندهی میکند و آنها را بر اساس نوع عمل دسته بندی میکند، به عنوان مثال. فرآیند، تصمیم، داده و… .
اغلب متخصصان توصیه میکنند تا به صورت عملی و همراه با کدنویسی برنامه نویسی را یاد بگیرید و به سراغ کتاب خواندن نروید. اما برخلاف یادگیری یک زبان برنامه نویسی، برای مبحث الگوریتم و فلوچارت بهتر است با یک یا دو کتاب کاربردی کار را شروع کنید. الگوریتم و فلوچارت نیازمند تمرین بسیار است و مرور این کتابها باعث میشود تا با روشهای مختلف و درست حل مسائل از ساده تا پچیده آشنا شوید. در ادامه سعی کردیم کتابهای مفید و توصیه شده توسط جامعه برنامه نویسان را معرفی کنیم.
این کتاب توسط نشر دانشگاه MIT معرفی شده است و برای آشنایی با ساختمان دادهها نیز میتواند به کار رود. پس از اضافه شدن نویسنده چهارم به جمع نویسندگان در ویراست دوم، این کتاب با نام مخفف CLRS شناخته شد. کتاب CLRS به عنوان مرجع اصلی برای دروس الگوریتم در بسیاری از دانشگاههای ایران و جهان استفاده میشود و یکی از رایجترین منابع برای الگوریتم در مقالات منتشر شده میباشد. کتاب مذکور نیم میلیون نسخه در طول ۲۰ سال اول خود فروش داشته است.
کتاب برنامه نویسی به زبان سی پلاس پلاس یکی از اولین کتبی است که علاقه مندان و دانشجویان درس مبانی کامپیوتر و برنامه نویسی به آن مراجعه میکنند. نویسنده این کتاب معروف، آقای جعفرنژاد قمی است. حتی ممکن است شما هم در هنگام جستجو در سایتها و کتابهای آموزشی زبانهای برنامهنویسی به این نام برخورده باشید.
Clean Code کتابی است که در آن رابرت مارتین مبحثی کاملا نو و انقلابی را در رابطه با کدنویسی ارائه کرده است. این کتاب نکات مورد نیاز برای مسلط شدن بر برنامه نویسی را در اختیار مخاطب قرار میدهد و از سه بخش تشکیل شده است:
کتاب آشنایی با الگوریتم با رویکرد خلاقانه یکی از منابع اصلی المپیادهای کامپیوتر و مسابقات برنامهنویسی برای یادگیری طراحی و تحلیل الگوریتمها است. این کتاب با بررسی و آموزش فرایند توسعه الگوریتمها، بر جنبههای خلاقانه طراحی الگوریتم تأکید دارد و شامل صدها حل مسئله و مثال است که برای بهبود تواناییهای حل مسئله و درک اصول طراحی الگوریتم طراحی شده است. در این کتاب علاوه بر معرفی تکنیکهای مختلف طراحی الگوریتمها و روشهای حل برخی مسائل الگوریتمی، روشهای تحلیل و حل آنها با جزئیات بیشتر و بهصورت گامبهگام بررسی شده است.
این کتاب نوشته استیو مک کانل کتابی است که اولین بار در سال 1993 توسط ماکرروسافت پرس چاپ و منتشر شد. نکته قابل توجه این کتاب این است که مهم نیست چقدر تجربه کدنویسی داشته، به چه زبانی کد میزنید و یا ابعاد پروژه شما چقدر است. این کتاب به خواننده آگاهی داده و او را به فکر کردن و ایدهپردازی ترغیب میکند.
الگوریتمهای کاربردی زیادی در ریاضیات و علوم کامپیوتر وجود دارند که ما بهطور خلاصه به معرفی تعدادی از آنها پرداختیم. تسلط بر الگوریتمها اهمیت زیادی برای برنامه نویسان و بهویژه در بخش بک اند (Back-End) وب سایت یا برنامهها دارد زیرا میتواند نقطه قوتی برای استخدام در شرکتهای برنامه نویسی باشد. فلوچارتها و الگوریتمها ازجمله پیشنیازهای یادگیری برنامهنویسی هستند.