مقدمه‌ای بر الگوریتم

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

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

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

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

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

ویژگی‌های الگوریتم

برای اینکه برخی دستورالعمل‌ها الگوریتم به‌حساب آیند، باید ویژگی‌های زیر را داشته باشند:

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

انواع الگوریتم

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

 الگوریتم بازگشتی

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

الگوریتم تقسیم و حل

در الگوریتم‌های Divide and Conquer، ایده این است که مسئله را در دو بخش حل کنیم، بخش اول مسئله را به مسائل فرعی از همان نوع تقسیم می‌کند. بخش دوم این است که مسئله کوچک‌تر را به‌طور مستقل حل کنید و سپس نتیجه ترکیبی را برای ایجاد پاسخ نهایی به مسئله اضافه کنید. برخی از مشکلات رایج که با استفاده از الگوریتم‌های تقسیم و غلبه حل می‌شوند عبارت‌اند از جستجوی دودویی، مرتب‌سازی ادغامی، مرتب‌سازی سریع، ضرب ماتریس استراسن و غیره.

الگوریتم‌های برنامه‌نویسی پویا

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

مشکلات زیر را می‌توان با استفاده از الگوریتم برنامه‌نویسی پویا حل کرد:

• مسئله کوله‌پشتی
• زمان‌بندی کار وزن‌دار
• الگوریتم فلوید وارشال و غیره

الگوریتم‌های حریصانه

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

برخی از مشکلات رایجی که می‌توان از طریق الگوریتم حریصانه حل کرد عبارت‌اند از: الگوریتم کوتاه‌ترین مسیر Dijkstra، الگوریتم Prim، الگوریتم Kruskal، کدگذاری هافمن و غیره، در دوره آموزش طراحی الگوریتم به مسائل الگوریتم حریصانه پرداخته‌شده است.

الگوریتم عقب‌گرد

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

الگوریتم تصادفی

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

 الگوریتم مرتب‌سازی

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

الگوریتم جستجو

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

الگوریتم هش

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

مزایا و معایب الگوریتم‌ها

مزایای الگوریتم:

• درک آن آسان است.
• یک الگوریتم نمایش مرحله‌ای از یک راه‌حل برای یک مسئله معین است.
• در الگوریتم، مسئله به قطعات یا مراحل کوچک‌تر تقسیم می‌شود، بنابراین، برای برنامه‌نویس آسان‌تر است که آن را به یک برنامه واقعی تبدیل کند.

معایب الگوریتم‌ها:

• نوشتن الگوریتم زمان زیادی می‌برد، مخصوصاً اگر کار پیچیده باشد.
• درک منطق پیچیده از طریق الگوریتم‌ها می‌تواند بسیار دشوار باشد.
• کار با فرایندهای Branching و Looping در الگوریتم‌ها دشوار است.

درە دوره آموزش طراحی الگوریتم با نقاط قوت و ضعف الگوریتم‌ها بیشتر آشنا خواهیم شد.