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

نحوه طراحی الگوریتم

برای نوشتن الگوریتم، موارد زیر به‌عنوان پیش‌نیاز موردنیاز است:

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

چرا از الگوریتم استفاده می‌کنیم؟

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

بنابراین زمان موردنیاز برای حل یک مشکل با رویه الگوریتم بسیار مؤثرتر از زمانی است که بدون هیچ روشی یک مسئله را حل کرد. ازاین‌رو نیاز به الگوریتم ضروری است.

تجزیه‌ و تحلیل الگوریتم

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

چرا تجزیه‌وتحلیل الگوریتم‌ها مهم است؟

دلایل زیر همگی نیاز به تجزیه‌وتحلیل الگوریتم را بیان خواهند کرد:

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

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

انواع روش ارزیابی برای الگوریتم به صورت موارد زیر است:

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

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

دوره آموزش طراحی الگوریتم

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

الگوریتم هش

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

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

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

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

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

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

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