مراحل نوشتن الگوریتم و انواع آن

مراحل نوشتن الگوریتم

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

مرحله اول - تعریف ورودی های الگوریتم

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

مرحله دوم - تعریف متغیرها

در بسیاری از اوقات بر اساس مقادیری که با آن ها کار می کنید، امکان ایجاد یک متغیر وجود دارد. متغیرها به شما اجازه می دهند که از یک مقدار در چندین محل مختلف استفاده کنید. در همان مثال قبلی برای محاسبه مساحت مستطیل، دو مقدار طول و عرض را داریم، بنابراین می توانیم دو متغیر به نام های WIDTH و HEIGHT را تعریف کنیم تا این مقادیر را در خود داشته باشند. یادتان باشد که همیشه باید از نام های واضح برای متغیرها استفاده کنید و از نوشتن نام ها به صورت رمزنگاری شده (مثلا W و H به جای WIDTH و HEIGHT) خودداری کنید.

مرحله سوم - پیاده سازی عملیات اصلی

از متغیرهای ایجاد شده در قسمت قبل برای مقاصد پردازشی استفاده کنید. به طور مثال با ضرب کردن WIDTH و HEIGHT یک مقدار جدید به دست می آید که همان مساحت مستطیل است و می توانیم آن را در یک متغیر جدید به نام AREA بگذاریم. الگوریتم شما ممکن است بسته به هدف شما پیچیده تر باشد و شامل branch ها نیز بشود.

مرحله چهارم - گرفتن خروجی از نتیجه الگوریتم

در مثال مساحت مستطیل، مقدار مساحت را در متغیری به نام AREA ذخیره کرده ایم، بنابراین خروجی ما همان AREA است. پس اگر فرض کنیم که طول و عرض مستطیل به ترتیب 3 و 6 باشد، خروجی ما 18 می شود.

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

الگوریتم ها در تمام زیر شاخه های علوم کامیپوتر و حتی در زندگی روزمره استفاده می شوند! حتی زمانی که در دبستان در حال حل کردن سوالات ریاضی بودید، احتمالا از الگوریتم ها استفاده کرده اید اما معمولا افراد می خواهند بدانند چند نوع الگوریتم داریم؟ قبلا هم گفته بودم که صفحه https://en.wikipedia.org/wiki/List_of_algorithms در ویکی پدیا لیستی از بسیاری از الگوریتم های موجود را جمع آوری کرده است اما اگر شما به آن ها نگاه کنید احتمالا چیز زیادی نمی فهمید. چرا؟ به دلیل اینکه این الگوریتم ها از پیش آماده شده و پیشرفته هستند و ما در دوره مبتدی هستیم. البته بررسی بسیاری از این الگوریتم ها در دوره «الگوریتم و داده ساختار» در روکسو انجام می شود اما ما در این دوره می خواهیم روی کلیت آن ها تمرکز کنیم و ورود به جزئیات را به همان دوره «الگوریتم و داده ساختار» موکول می کنیم. البته باید بدانید که الگوریتم ها پایانی ندارند و هر روزه به تعدادشان اضافه می شوند. همانطور که گفتم الگوریتم یک فرآیند ترتیبی برای حل مسئله است و از طرفی می توانیم برای حل یک مشکل هزاران راه حل مختلف داشته باشیم بنابراین تعداد الگوریتم ها بسیار زیاد است.

با این همه دکتر Christoph Koutschan، یکی از دانشمندان رایانه در موسسه تحقیقاتی Research Institute for Symbolic Computation یا به اختصار RISC در استرالیا، نتایج تحقیقات و نظرسنجی های خود اعلام کرده بود که در آن 32 الگوریتم به عنوان مهم ترین الگوریتم های علوم کامپیوتری شناخته شده بودند. با اینکه الگوریتم ها پیچیدگی های منحصر به فرد خودشان را دارند اما از نظر ماهیت معمولا به یکی از شش دسته اصلی زیر تعلق دارند.

دسته اول - Recursive Algorithm

به معنی «الگوریتم های بازگشتی» می باشد. در این الگوریتم، مشکل مورد نظر مرتبا به مشکلات کوچک تری (زیرمسئله) تقسیم می شود تا زمانی که به جواب برسیم. یکی از مشهور ترین مثال ها برای این الگوریتم مسئله «برج هانویْ» است. اگر در مورد آن چیزی نشنیده اید می توانید به صفحه «برج هانویْ» در ویکی پدیا مراجعه کنید. یکی دیگر از مثال های این الگوریتم حل کردن تابع فاکتوریل یا توان می باشد.

دسته دوم - Divide and Conquer

در فارسی به الگوریتم «تقسیم و حل» مشهور است. این الگوریتم از دو قسمت اصلی ساخته شده است؛ اول: تقسیم کردن مسئله به مسئله های کوچک تر (زیرمسئله) از همان نوع و البته مستقل از مسئله اصلی. دوم: رسیدن به راه حل اصلی بر اساس حل کردن مسائل کوچک تر به صورت جداگانه. این الگوریتم سه نکته اصلی دارد:

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

دسته سوم - Dynamic Programming

در فارسی به الگوریتم «برنامه نویسی پویا» مشهور می باشد. این الگوریتم توسط آقای Richard Bellman در سال 1950 ارائه شد. این نوع الگوریتم معمولا برای بهینه سازی استفاده می شود. در این نوع الگوریتم نتایج قبلی برای استفاده در آینده ذخیره می شوند. روش حل مسئله در این الگوریتم نیز بسیار شبیه به الگوریتم «تقسیم و حل» است چرا که یک مسئله به زیر مسئله های ریز تر شکسته می شود اما تفاوت اینجاست که در «برنامه نویسی پویا» باید بین مسئله اصلی و زیر مسئله ها همپوشانی (Overlap) وجود داشته باشد در حالی که در الگوریتم «تقسیم و حل» به آن نیازی نداریم.

دسته چهارم - Greedy Algorithm

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

دسته پنجم - Brute Force

این الگوریتم در فارسی و در انگلیسی نام های مختلفی دارد. به طور مثال در انگلیسی نام هایی مانند brute-force و exhaustive و generate and test و در فارسی نام هایی مانند الگوریتم «غیر مطلع» یا «کور» یا «ناآگاهانه» یا «خام و بی‌خردانه» یا «فراگیر» یا «تولید و تِست» به آن نسبت داده شده اند. این الگوریتم یکی از ساده ترین الگوریتم های موجود می باشد چرا که یک روش آزمون و خطا است. این الگوریتم بین راه حل های ممکن گردش می کند تا زمانی که به نتیجه مطلوب برسد.

دسته ششم - Backtracking

معمولا در فارسی با نام «روش پس‌گرد» شناخته شده و بر اساس جست و جوی بازگشتی (جستجوی عمق اول) طراحی شده است. جست و جوی «اول‌عمق» یا depth-first چیست؟ این نوع از الگوریتم از ریشه مسئله شروع کرده و وارد تک تک شاخه ها می شود و هر شاخه را تا انتها بررسی می کند. در واقع تا زمانی که به انتهای یک شاخه نرسیده است به شاخه بعدی نمی رود به همین دلیل است که به «اول‌عمق» نامگذاری شده است. مشهور ترین مثال برای این الگوریتم «معمای هشت وزیر» است. اگر در مورد این معما نشنیده اید می توایند به صفحه «مسئله چند وزیر» در ویکی پدیا مراجعه کنید.

در جلسه بعد وارد مبحث فلوچارت می شویم.