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

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

1. روش اجرا
2. روش طراحی
3. رویکردهای طراحی
4. سایر طبقه بندی ها

در این مقاله، الگوریتم های مختلف در هر روش طبقه بندی مورد بحث قرار می گیرد. 

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

1. بازگشت یا تکرار: یک الگوریتم بازگشتی الگوریتمی است که بارها و بارها خود را فراخوانی می‌کند تا زمانی که یک شرط پایه به دست آید، در حالی که الگوریتم‌های تکراری از حلقه‌ها و/یا ساختارهای داده مانند پشته‌ها ، صف‌ها برای حل هر مشکلی استفاده می‌کنند. هر راه حل بازگشتی را می توان به عنوان یک راه حل تکراری پیاده سازی کرد و بالعکس. 
   مثال: برج هانوی به صورت بازگشتی پیاده سازی شده است در حالی که مسئله Stock Span به صورت تکراری اجرا می شود.
2. دقیق یا تقریبی: الگوریتم هایی که قادر به یافتن راه حل بهینه برای هر مسئله ای هستند به الگوریتم دقیق معروف هستند. برای تمام آن مسائلی که یافتن بهینه ترین راه حل ممکن نیست، از یک الگوریتم تقریب استفاده می شود. الگوریتم‌های تقریبی، آن دسته از الگوریتم‌هایی هستند که نتیجه را به‌عنوان میانگین پیامدهای فرعی یک مسئله پیدا می‌کنند. 
   مثال: برای مسائل NP-Hard ، از الگوریتم های تقریب استفاده می شود. الگوریتم های مرتب سازی، الگوریتم های دقیق هستند.
3. الگوریتم های سریالی یا موازی یا توزیع شده: در الگوریتم های سریال، یک دستور در یک زمان اجرا می شود در حالی که الگوریتم های موازی آنهایی هستند که در آنها مسئله را به زیرمسائل تقسیم کرده و روی پردازنده های مختلف اجرا می کنیم. اگر الگوریتم های موازی بر روی ماشین های مختلف توزیع شوند، به آنها الگوریتم های توزیع شده می گویند.

طبقه بندی بر اساس روش طراحی: اساساً سه دسته اصلی وجود دارد که یک الگوریتم را می توان در این نوع طبقه بندی نام برد. آن ها هستند: 

1. روش حریص: در روش حریصانه ، در هر مرحله ، بدون فکر کردن به عواقب آتی  ، تصمیم به انتخاب بهینه محلی گرفته می شود.
   مثال: کوله پشتی کسری ، انتخاب فعالیت .
2. Divide and Conquer: استراتژی Divide and Conquer شامل تقسیم مسئله به زیرمسئله، حل بازگشتی آنها و سپس ترکیب مجدد آنها برای پاسخ نهایی است. 
   مثال: ادغام مرتب‌سازی ، مرتب‌سازی سریع .
3. برنامه نویسی پویا: رویکرد برنامه نویسی پویا شبیه به تفرقه بیانداز و حکومت کن . با این تفاوت که هرگاه فراخوانی های تابع بازگشتی با نتیجه مشابه داشته باشیم، به جای فراخوانی مجدد، سعی می کنیم نتیجه را در یک ساختار داده به شکل جدول ذخیره کنیم و نتایج را از جدول بازیابی کنیم. بنابراین، پیچیدگی زمانی کلی کاهش می یابد. “Dynamic” به این معنی است که ما به صورت پویا تصمیم می گیریم که آیا یک تابع را فراخوانی کنیم یا مقادیر را از جدول بازیابی کنیم. 
   مثال: 0-1 کوله پشتی ، مسئله جمع زیر مجموعه .
4. برنامه ریزی خطی: در برنامه ریزی خطی، نابرابری هایی از نظر ورودی ها و به حداکثر رساندن یا به حداقل رساندن برخی از توابع خطی ورودی ها وجود دارد. 
   مثال: حداکثر جریان گراف جهت دار
5. Reduction(Transform and Conquer): در این روش یک مسئله دشوار را با تبدیل آن به یک مسئله شناخته شده که راه حل بهینه ای برای آن داریم حل می کنیم. اساساً، هدف یافتن الگوریتم کاهنده‌ای است که بر پیچیدگی آن غالب الگوریتم‌های کاهش‌یافته منتج نباشد. 
   مثال: الگوریتم انتخاب برای یافتن میانه در لیست شامل مرتب سازی لیست و سپس یافتن عنصر میانی در لیست مرتب شده است. به این تکنیک ها تبدیل و تسخیر نیز می گویند.

طبقه بندی بر اساس رویکردهای طراحی: دو رویکرد برای طراحی یک الگوریتم وجود دارد. این رویکردها شامل 

1. رویکرد بالا به پایین :
2. رویکرد پایین به بالا

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

سایر طبقه بندی ها: به غیر از طبقه بندی الگوریتم ها به دسته های گسترده فوق، الگوریتم را می توان به دسته های گسترده دیگری مانند: 

1. الگوریتم‌های تصادفی: الگوریتم‌هایی که انتخاب‌های تصادفی برای راه‌حل‌های سریع‌تر انجام می‌دهند، به عنوان الگوریتم‌های تصادفی شناخته می‌شوند . 
   مثال: الگوریتم مرتب سازی سریع تصادفی .
2. طبقه بندی بر اساس پیچیدگی: الگوریتم هایی که بر اساس زمان صرف شده برای دستیابی به راه حل برای هر مشکلی برای اندازه ورودی طبقه بندی می شوند. این تحلیل به عنوان تحلیل پیچیدگی زمانی شناخته می شود . 
   مثال: برخی از الگوریتم‌ها O(n) می‌گیرند، در حالی که برخی زمان نمایی می‌گیرند.
3. طبقه بندی بر اساس حوزه تحقیق: در CS هر رشته مشکلات خاص خود را دارد و نیاز به الگوریتم های کارآمد دارد. 
   مثال: الگوریتم مرتب سازی، الگوریتم جستجو، یادگیری ماشین و غیره.
4. Enumeration و Backtracking Branch and Bound: اینها بیشتر در هوش مصنوعی استفاده می شوند.