الگوریتم در برنامه نویسی چیست؟ — به زبان ساده

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

الگوریتم در برنامه نویسی چیست ؟

قبلاً توضیح داده‌ایم که برنامه نویسی چیست و برنامه نویس کیست ، اما اگر تازه وارد دنیای برنامه نویسی شده‌اید لازم است با مفهوم الگوریتم آشنا شوید و درک صحیحی از نقش الگوریتم در برنامه نویسی به دست بیاورید. الگوریتم در برنامه نویسی دستورالعملی برای توصیف دقیق همه مراحل و گام‌های اجرایی در برنامه‌های کامپیوتری به حساب می‌آید که جهت حل برنامه و رسیدن به هدف اصلی آن مورد استفاده قرار می‌گیرند. برای مثال در دنیای واقعی و روزمره، دستور آشپزی یک غذا شامل مواد غذایی موردنیاز و مجموعه‌ای از مراحل برای درست کردن غذای مورد نظر است. در دنیای برنامه نویسی نیز الگوریتم دقیقاً همین کار را انجام می‌دهد. در زبان‌های برنامه نویسی کلمه‌ای که به جای دستور آشپزی استفاده می‌شود، «رویه» یا «Procedure» است و مواد غذایی هم نقش «ورودی‌ها» (Input) را ایفا می‌کنند.

برنامه کامپیوتری برای انجام فرآیند خود، مراحل را به وسیله رویه الگوریتم انجام می‌دهد و سپس با استفاده از ورودی‌ها، نتایجی تولید می‌کند که به آن‌ها «خروجی» (Output) گفته می‌شود. به طور کلی الگوریتم در برنامه نویسی توضیح می‌دهد که چطور برنامه‌ها باید اجرا شوند و کامپیوتر در هر بار اجرای برنامه همان روند الگوریتم را انجام خواهد داد. الگوریتم‌ها باید به زبانی تبدیل شوند که برای کامپیوتر قابل فهم باشند. با این حال، باید به این نکته مهم توجه داشت که الگوریتم‌ها در برنامه نویسی کدهای کامپیوتر نیستند. الگوریتم‌ها با زبان با همان زبان محاوره انسان‌ها (زبان‌های طبیعی | Natural Language) نوشته می‌شوند. مثال، الگوریتم‌ها به زبان فارسی یا انگلیسی باشند.

الگوریتم در برنامه نویسی دارای شاخ و برگ زیادی نیست و به طور کلی شامل بخش‌های شروع، میانه و پایان می‌شود. در واقع می‌توان اولین مرحله از آن را شروع یا «Start» و آخرین مرحله را پایان یا «End» نام‌گذاری کرد. این مراحل بستگی به محتوایی دارند که برنامه مورد نظر قرار است در خود جای دهد. تمام مراحل الگوریتم در برنامه نویسی و وظایفی که باید انجام شوند کاملاً واضح و بدون ابهام هستند و هر کسی با خواندن آن می‌تواند دستورالعمل عملکردی برنامه را متوجه شود. استفاده از الگوریتم در برنامه نویسی همیشه به یک راه حل می‌انجامد و تا حد امکان سعی می‌شود کارآمدترین راه حل برای برنامه ارائه شود.

گاهی شماره‌گذاری مراحل انجام کار در الگوریتم روش خوبی است، اما اجباری برای این کار وجود ندارد. برخی از افراد به جای شماره‌گذاری مراحل الگوریتم در برنامه نویسی از تورفتگی و «شبه‌کد» (Pseudocode) استفاده می‌کنند. شبه‌کد یک زبان نیمه برنامه نویسی به حساب می‌آید که برای توصیف مراحل یک الگوریتم یک الگوریتم مورد استفاده قرار می‌گیرد. همچنین، برخی از افراد برای طراحی الگوریتم خود از نمودارهایی به نام «فلوچارت» (Flowchart) استفاده می‌کنند. ادامه مقاله «الگوریتم در برنامه نویسی چیست» به بررسی ویژگی‌های الگوریتم در یک برنامه اختصاص داده شده است.

ویژگی های الگوریتم در برنامه نویسی چیست ؟

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

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

در ادامه این مقاله به بررسی مزایای الگوریتم در برنامه نویسی پرداخته شده است.

مزایای الگوریتم در برنامه نویسی چیست ؟

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

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

در ادامه مقاله «الگوریتم در برنامه نویسی چیست» به بررسی معایب الگوریتم پرداخته شده است.

معایب الگوریتم در برنامه نویسی چیست ؟

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

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

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

چگونه الگوریتم در برنامه نویسی طراحی می شود؟

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

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

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

الگوریتم در برنامه نویسی چگونه کار می کند؟

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

• الگوریتم نوشتاری با مراحل شماره‌گذاری شده (این روش می‌تواند به صورت شبه‌کد نیز نوشته شود.)
• الگوریتم فلوچارتی

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

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

در تصویر زیر حالت فلوچارتی الگوریتم نوشتاری فوق ملاحظه می‌شود.

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

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

در بخش بعدی مقاله «الگوریتم در برنامه نویسی چیست» به مبحث تجزیه و تحلیل الگوریتم در برنامه نویسی پرداخته شده است.

تجزیه و تحلیل الگوریتم در برنامه نویسی چگونه است؟

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

• «تجزیه و تحلیل پیشین» (Priori Analysis): این مرحله به صورت تجزیه و تحلیلی تئوری روی الگوریتم طراحی شده، انجام می‌شود. در این مرحله، کارایی یک الگوریتم با این فرض اندازه‌گیری شده است که عوامل جانبی از جمله سرعت پردازنده ثابت هستند و تأثیری روی پیاده‌سازی برنامه ندارند.
• «تجزیه و تحلیل پسین» (Posterior Analysis): در این مرحله تجزیه و تحلیلی تجربی روی الگوریتم طراحی شده صورت می‌گیرد. قبل از رسیدن به این مرحله، الگوریتم طراحی شده پیاده‌سازی شده است و سپس روی کامپیوتر مورد نظر اجرا می‌شود. در این مرحله از تجزیه و تحلیل الگوریتم، آمار واقعی مانند زمان اجرا و فضای مورد نیاز جمع‌آوری می‌شوند.

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

معرفی فیلم های آموزش برنامه نویسی تم آف

دوره‌های آموزشی وب سایت تم آف بر اساس موضوع آن‌ها به صورت مجموعه‌های آموزشی متفاوتی دسته‌بندی می‌شوند. یکی از این مجموعه‌های جامع مربوط به آموزش‌های انواع زبان‌های برنامه نویسی گوناگون است. علاقه‌مندان و دانشجویان می‌توانند برای یادگیری بیشتر الگوریتم در برنامه نویسی و همچنین زبان‌های گوناگونی که از الگوریتم‌ها استفاده می‌کنند، این مجموعه آموزشی را مورد استفاده قرار دهند. در زمان تدوین این مقاله، مجموعه دوره‌های برنامه نویسی تم آف حاوی بیش از ۴۸۹ ساعت محتوای ویدیویی و حدود ۵۸ عنوان آموزشی مختلف است. در ادامه، برخی از دوره‌های این مجموعه به طور خلاصه معرفی شده‌اند:

• فیلم آموزش برنامه نویسی پایتون Python – مقدماتی (طول مدت: ۱۹ ساعت و ۵۳ دقیقه، مدرس: پژمان اقبالی شمس آبادی): در این دوره آموزشی، زبان برنامه نویسی پایتون از پایه‌ترین مفاهیم تا اصول پیشرفته آن آموزش داده می‌شود و سعی شده است که همه مباحث مقدماتی مورد نیاز آن ارائه شود. برای مشاهده فیلم آموزش برنامه نویسی پایتون Python – مقدماتی + کلیک کنید.
• فیلم آموزش برنامه نویسی C++‎ سی پلاس پلاس (طول مدت: ۲۰ ساعت و ۱۴ دقیقه، مدرس: دکتر فرشید شیرافکن): در این تم آف، زبان برنامه نویسیC++ ‎ در دو بخش آموزش داده شده است. برای مشاهده فیلم آموزش برنامه نویسی C++‎ سی پلاس پلاس + کلیک کنید.
• فیلم آموزش برنامه نویسی جاوا Java (طول مدت: 19 ساعت و 19 دقیقه، مدرس: دکتر سید مصطفی کلامی هریس): این دوره آموزشی به دانشجویان و علاقه‌مندانی پیشنهاد شده است که قصد یادگیری زبان برنامه نویسی جاوا را به صورت جامع دارند. برای مشاهده فیلم آموزش برنامه نویسی جاوا Java + کلیک کنید.
• فیلم آموزش برنامه نویسی C (طول مدت: ۱۳ ساعت و ۳۰ دقیقه، مدرس: دکتر سید مصطفی کلامی هریس): در این تم آف، زبان برنامه نویسی C همراه با مفاهیم کاربردی آن به همراه مثال‌های عملی آموزش داده می‌شود. برای مشاهده فیلم آموزش برنامه نویسی C + کلیک کنید.
• فیلم آموزش کاربردی برنامه نویسی سی شارپ #C (طول مدت: ۱۳ ساعت و ۵۸ دقیقه، مدرس: مهندس رشید شجاعی): در این دوره آموزشی، آموزندگان به صورت کاربردی و عملی با زبان سی شارپ و محیط‌های Visual Studio و دات‌نت آشنا می‌شوند. برای مشاهده فیلم آموزش کاربردی برنامه نویسی سی شارپ #C + کلیک کنید.
• فیلم آموزش برنامه نویسی تایپ اسکریپت TypeScript (طول مدت: ۸ ساعت و ۴۵ دقیقه، مدرس: پوریا کهریزی): این دوره آموزشی به آموزندگانی پیشنهاد شده است که قصد یادگیری زبان برنامه نویسی تایپ اسکریپت را از پایه‌ترین مفاهیم آن دارند. تایپ اسکریپت دارای شباهت‌های بسیاری با زبان‌های سی شارپ و جاوا اسکریپت است. برای مشاهده فیلم آموزش برنامه نویسی تایپ اسکریپت TypeScript + کلیک کنید.

اکنون در این بخش مقاله «الگوریتم در برنامه نویسی چیست» و پس از معرفی برخی از دوره‌های آموزشی ویدیویی برنامه نویسی تم آف، در بخش بعدی این مقاله به بررسی پیچیدگی الگوریتم در برنامه نویسی پرداخته می‌شود.

پیچیدگی الگوریتم در برنامه نویسی چیست ؟

برای شرح پیچیدگی الگوریتم از یک مثال ساده استفاده شده است. فرض می‌شود که X یک الگوریتم در برنامه نویسی به حساب بیاید و n «اندازه» (Size) اطلاعات ورودی آن باشد. زمان و فضای استفاده شده برای الگوریتم X دو عامل اصلی است که کارایی X را تعیین می‌کنند و در ادامه مورد بررسی قرار گرفته‌اند:

• «عامل زمان» (Time Factor): زمان با استفاده از شمارش تعداد عملیات کلیدی مورد بررسی قرار می‌گیرد.
• «عامل فضا» (Space Factor): فضا به وسیله شمارش بیشترین فضای حافظه مورد نیاز در الگوریتم اندازه‌گیری می‌شود.

به طور کلی می‌توان گفت که پیچیدگی الگوریتم (n)f، زمان اجرا یا فضای مورد نیاز الگوریتم را بر حسب اندازه داده‌های ورودی یعنی n ارائه می‌دهد. در بخش بعدی این مقاله به بررسی «پیچیدگی فضایی» (Space Complexity) در الگوریتم پرداخته شده است.

پیچیدگی فضایی الگوریتم در برنامه نویسی چیست ؟

پیچیدگی فضایی الگوریتم در برنامه نویسی نشان دهنده فضای حافظه مورد نیاز آن در یک «چرخه حیات» (Life Cycle) الگوریتم است. فضایی که یک الگوریتم در برنامه نویسی به آن احتیاج دارد، شامل اجتماع دو مؤلفه زیر می‌شود:

• بخش ثابتی که فضای مورد نیاز برای ذخیره متغیرها و داده‌های خاص به حساب می‌آید. همچنین این بخش مستقل از اندازه مسئله است. برای مثال، در این بخش متغیرهای ساده، مقادیر ثابت استفاده شده در برنامه، اندازه برنامه و سایر موارد وجود دارند.
• بخش متغیر، فضای مورد نیاز متغیرها است که اندازه آن به اندازه مسئله بستگی دارد. به عنوان مثال برای این بخش می‌توان به «تخصیص حافظه پویا» (Dynamic Memory Allocation)، «فضای پشته بازگشتی» (Recursion Stack Space) و سایر موارد اشاره کرد.

به طور کلی پیچیدگی فضایی که با (P)S نشان داده می‌شود؛ در همه الگوریتم‌ها با نام P، دارای معادله $$S(P) = C + SP(I)$$ است. در این معادله C بخش ثابت پیچیدگی فضایی و SP(I) بخش متغیر الگوریتم را نشان می‌دهد، این عبارت بستگی به ویژگی نمونه (Instance) برنامه دارد. در ادامه مثالی ساده برای درک بهتر مفهوم پیچیدگی فضایی ارائه شده است:

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

در مثال فوق، سه متغیر B ،A و C و یک متغیر ثابت وجود دارند. از این رو عبارت S(P) = 1 + 3 به این صورت نوشته شده است. به دلیل اینکه، فضای پیچیدگی به نوع داده متغیرها و مقادیر ثابت بستگی دارد و بر این اساس با هم ضرب خواهند شد. در ادامه مقاله «الگوریتم در برنامه نویسی چیست» به بررسی مفهوم «پیچیدگی زمانی» (Time Complexity) پرداخته شده است.

پیچیدگی زمانی چیست؟

پیچیدگی زمانی یک الگوریتم نشان دهنده مقدار زمان مورد نیاز الگوریتم از زمان ایجاد تا پیاده‌سازی آن است. زمان مورد نیاز را می‌توان به عنوان یک تابع عددی به صورت T(n) در نظر گرفت و n تعداد مراحل الگوریتم را نشان می‌دهد. شرط این تابع این است که هر مرحله زمان ثابتی را مصرف می‌کند. برای مثال، جمع دو عدد صحیح (Integer) n بیتی، دارای n مرحله است.

در نتیجه، همه محاسبات زمانی به صورت $$T(n) = c ∗ n$$ نشان داده می‌شوند که c در این رابطه زمان صرف شده برای جمع شدن دو بیت به حساب می‌آید. در این مثال مشاهده می‌شود که با افزایش اندازه، ورودی به صورت خطی افزایش پیدا می‌کند. در بخش بعدی مقاله «الگوریتم در برنامه نویسی چیست» به بررسی و معرفی انواع دسته‌بندی‌ها الگوریتم در برنامه نویسی پرداخته شده است.

انواع دسته بندی های الگوریتم در برنامه نویسی

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

• «الگوریتم مرتب‌سازی» (Sorting Algorithm)
• «الگوریتم جستجو» (Searching Algorithm)
• «الگوریتم درهم‌سازی یا هشینگ» (Hashing Algorithm)
• «الگوریتم برنامه نویسی پویا» (Dynamic Programming Algorithm | DP)
• الگوریتم «نمایی مربعی» (Exponential By Squaring)
• الگوریتم «تجزیه و تطبیق رشته» (String Matching And Parsing)
• «الگوریتم تست عدد اول» (Primality Testing Algorithm)

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

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

مرتب‌سازی یکی از مفاهیم علوم کامپیوتر است که امروزه در زمینه‌های گوناگون به میزان زیادی مورد مطالعه قرار می‌گیرد. ایده این الگوریتم، مرتب کردن مؤلفه‌ها در فهرستی با ترتیب خاص است. البته اکثر زبان‌های برنامه نویسی دارای کتابخانه‌های داخلی (Built-In) هستند که وظایف مرتب‌سازی را انجام می‌دهند ولی دانستن روش کار این الگوریتم‌ها برای برنامه نویسان می‌تواند مفید باشد. الگوریتم‌های مرتب‌سازی انواع گوناگونی دارند و نسبت به نیاز برنامه می‌توان هر یک از موارد زیر را استفاده کرد:

• «مرتب‌سازی ادغامی» (Merge Sort)
• «مرتب‌سازی سریع» (Quick Sort)
• «مرتب‌سازی سطلی» (Bucket Sort)
• «مرتب سازی هرمی» (Heap Sort)
• «مرتب‌سازی شمارشی» (Counting Sort)

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

• مقاله‌های پیشنهادی:
  • پیچیدگی زمانی الگوریتم های مرتب سازی با نماد O بزرگ — به زبان ساده
  • ۵ الگوریتم مرتب سازی در پایتون — راهنمای کاربردی
  • الگوریتم های مرتب سازی در سوئیفت (Swift) — به زبان ساده
  • مرتب سازی ادغامی (Merge Sort) در جاوا — به زبان ساده

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

این نوع از الگوریتم‌ها کاربرد فراوانی در برنامه نویسی دارند و از اهمیت بالایی برخوردار هستند. آن‌ها به دو دسته الگوریتم «جستجو دودویی یا باینری» (Binary Search) و «جستجوی عمق اول» (Depth First Search | DFS) یا «جستجوی سطح اول» (Breadth First Search | BFS) در ساختمان داده «گراف» (Graph) تقسیم می‌شوند. در ادامه به بررسی این دسته از الگوریتم‌ها پرداخته شده است. ابتدا الگوریتم جستجوی باینری یا دودویی شرح داده می‌شود.

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

الگوریتم «جستجو دودویی یا باینری» در ساختمان داده‌های خطی مورد استفاده قرار می‌گیرد. این الگوریتم برای به دست آوردن یک جستجو با کارایی بالا در مجموعه داده‌های مرتب شده کاربرد دارد. پیچیدگی زمانی این نوع از الگوریتم‌ها $$Olog _{2} N$$ است. ایده الگوریتم جستجوی دودویی به این صورت انجام شده است که داده‌ها به طور پیاپی به دو دسته تقسیم می‌شوند و این کار تا جایی ادامه پیدا می‌کند که در هر دسته فقط یک مؤلفه وجود داشته باشد و تقسیم مجددی امکان‌پذیر نباشد. برخی از کاربردهای این الگوریتم به صورت زیر هستند:

• زمانی که در فهرستی مرتب از آهنگ‌ها، نام آهنگ خاصی جستجو می‌شود، می‌توان از جستجوی دودویی و «تطبیق رشته» (String Matching) برای سریع‌تر رسیدن به جواب مورد نظر استفاده کرد.
• می‌توان از الگوریتم‌های جستجو دودویی برای «خطایابی» (Debuging) کدها در وب سایت «سیستم کنترل نسخه گیت» (Git) استفاده کرد. یکی از این ابزارهای جستجوی دودویی در این وب سایت «git bisect» است.

در ادامه این بخش به شرح الگوریتم جستجوی عمق اول و همچنین الگوریتم جستجوی سطح اول پرداخته شده است.

الگوریتم جستجوی عمق و سطح اول چیست؟

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

• این الگوریتم‌ها در موتورهای جستجو برای کارایی بهتر «خزنده‌های وب» (Web Crawler) مورد استفاده قرار می‌گیرند.
• الگوریتم‌های جستجوی عمق و سطح در حوزه «هوش مصنوعی» (Artificial Intelligence) برای ساخت ربات‌ها استفاده می‌شوند. برای مثال در یک ربات شطرنج از این نوع الگوریتم‌های جستجو استفاده شده است.
• برای پیدا کردن کوتاه‌ترین مسیر بین دو «نقشه سایت» (Sitemap) از این الگوریتم‌ها استفاده می‌شود.

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

الگوریتم درهم سازی چیست؟

الگوریتم درهم‌سازی یا هشینگ به عنوان پرکاربردترین روش برای یافتن داده‌های مناسب به همراه کلید در نظر گرفته می‌شود. در این الگوریتم با استفاده از «اندیس» (Index) داده‌ها می‌توان به آن‌ها دسترسی داشت. پیش از این برای یافتن داده‌های همراه با کلید از روش‌های مرتب‌سازی و جستجوی باینری استفاده می‌شد، اما در حال حاضر استفاده از روش‌های هشینگ بسیار مناسب‌تر است.

ساختمان داده‌های «نقشه هش» (Hash Map)، «جدول هش یا درهم‌سازی» (Hash Table) و «دیکشنری» (Dictionary) مقادیر را به کلیدهایشان به طور کارآمدی نگاشت می‌کنند. می‌توان با استفاده از کلیدها، بین مقادیر جستجو انجام داد. انتخاب «تابع هش» (Hash Function) مناسب برای نگاشت مقادیر به کلیدهایشان کاملاً به چیستی مسئله بستگی دارد. برخی از کاربردهای این الگوریتم در ادامه ارائه شده‌اند:

• در «مسیریاب‌ها» (Router) برای ذخیره آدرس IP از الگوریتم درهم‌سازی استفاده می‌شود.
• برای بررسی وجود مقادیر قبلی در یک فهرست یا لیست از این الگوریتم استفاده شده است. جستجوی خطی از جهات گوناگون هزینه بالایی برای این بررسی دارد. همچنین برای انجام این عملیات می‌توان از «ساختمان داده مجموعه» نیز استفاده کرد.

در بخش بعدی دسته‌بندی‌های الگوریتم در برنامه نویسی به شرح مختصری از برنامه نویسی پویا پرداخته شده است.

• مقاله‌های پیشنهادی:
  • انواع الگوریتم های جستجو و Hash Table — راهنمای جامع
  • Hashable در سوئیفت چیست؟ — از صفر تا صد
  • درهم‌سازی (Hashing) در عصر یادگیری ماشین — معرفی جدیدترین تحولات این رشته
  • پیاده سازی جدول هش (Hash Table) در جاوا اسکریپت — راهنمای مقدماتی

برنامه نویسی پویا چیست؟

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

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

• «زیر ساخت بهینه» (Optimal Substructure): راه حل بهینه مسئله شامل راه حل‌های بهینه‌ای برای زیر مسائل آن است.
• «زیرمسئله‌های همراه با هم‌پوشانی» (Overlapping Subproblem): راه حل بازگشتی شامل تعداد کمی زیر مسئله کوچک متمایز است.

همچنین این الگوریتم دارای دو نسخه است که در ادامه به بررسی آن‌ها پرداخته می‌شود:

• «رویکرد پایین به بالا» (Bottom-Up Approach): در این رویکرد، برنامه از پایین‌ترین بخش شروع به حل می‌کند به عبارتی دیگر ابتدا آخرین زیر مسئله موجود حل می‌شود و نتایج آن در زیر مسائل بالاتر مورد استفاده قرار می‌گیرند.
• «رویکرد بالا به پایین» (Top-Down Approach): در این رویکرد، شروع به حل مسئله از اولین زیر مسئله آغاز می‌شود و با استفاده از آن زیر مسئله‌های بعدی حل خواهند شد.

«مسئله کوله پشتی» (Knapsack Problem)، «زمان‌بندی کار وزنی» (Weighted Job Scheduling)، «الگوریتم فلوید وارشال» (Floyd Warshall Algorithm) نمونه‌هایی از الگوریتم‌هایی هستند که با استفاده از برنامه نویسی پویا می‌توان آن‌ها را حل کرد. در بخش بعدی از مقاله «الگوریتم در برنامه نویسی چیست» به بررسی الگوریتم نمایی مربعی پرداخته شده است.

الگوریتم نمایی مربعی چیست؟

برای توضیح این نوع از الگوریتم‌ها فرض می‌‌شود که قرار است $$۲^{۳۲}$$ محاسبه شود. برای این محاسبه باید فرآیندی ۳۲ بار تکرار شود تا جواب نهایی مسئله به دست بیاید. اما می‌توان با روش دیگری در ۵ تکرار نیز به پاسخ نهایی آن رسید. الگوریتم نهایی مربعی یا همان نمایی دودویی یک روش کلی برای محاسبه سریع توان‌های بزرگ اعداد صحیح مثبت یک عدد با پیچیدگی زمانی $$Olog _{2} N$$ به حساب می‌آید.

همچنین این روش برای محاسبه توان‌های «چندجمله‌ای‌ها» (Polynomial) و «ماتریس‌های مربعی» (Square Matrice) نیز استفاده می‌شود. از جمله کاربردهای این الگوریتم می‌توان به محاسبه توان‌های بزرگ عددهایی اشاره کرد که در رمزگذاری (Encryption) «RSA» استفاده شده‌اند. همچنین RSA از محاسبات ماژولار همراه با توان باینری استفاده می‌کند. بخش بعدی به بررسی الگوریتم تجزیه و تطبیق رشته اختصاص داده شده است.

الگوریتم تجزیه و تطبیق رشته چیست؟

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

• الگوریتم KPM: این الگوریتم سرنامی برای عبارت «Knuth Morris Pratt» است و وظیفه تطبیق رشته را بر عهده دارد. این الگوریتم در زمانی استفاده می‌شود که نیاز است یک الگو کوتاه را در یک رشته طولانی قرار داد. برای نمونه، زمانی که جهت جستجو کلمه یا عبارتی در صفحه کلید از کلیدهای میانبر «Ctrl+F» استفاده می‌شود، یعنی یک تطبیق الگو در کل یک سند انجام شده است.
• عبارت منظم (Regular Expression | Regex): در بسیاری از مواقع نیاز است که یک رشته با تجزیه روی یک محدودیت از پیش تعریف شده اعتبارسنجی شود. این روش در طیف وسیعی برای توسعه وب جهت تجزیه و تطبیق URL استفاده شده است.

بخش بعدی از مقاله «الگوریتم در برنامه نویسی چیست» به شرح الگوریتم تست عدد اول اختصاص دارد.

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

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

• الگوریتم «غربال اراتوستن» (Sieve of Eratosthenes): این روش به صورت قطعی کار خود را انجام می‌دهد. اگر در مسئله مورد نظر محدودیت خاصی وجود داشته باشد، مانند تعیین کردن همه اعداد اول در محدوده‌ای بین ۱۰۰ تا ۱۰۰۰، این رویکرد، روش مناسبی را برای حل این مسائل ارائه می‌دهد. در این مسائل طول محدوده عامل مهمی در نظر گرفته می‌شود، زیرا باید مقدار معینی از حافظه با توجه به محدوده به مسئله تخصیص داده شود.
• برای هر عدد n، تست تدریجی تا sqrt(n) انجام می‌شود: در مواردی که نیاز است تعداد اعداد کمی بررسی شوند و این اعداد به صورت جداگانه در محدوده بزرگی مانند محدوده اعداد $$۱$$ تا $$۲^{۱۲}$$ وجود دارند، روش غربال اراتوستن نمی‌تواند حافظه کافی به این مسئله اختصاص دهد. در روش ارائه شده این بخش می‌توان هر عدد n را با پیمایش فقط تا sqrt(n) بررسی کرد و همچنین یک بررسی تقسیم‌پذیری روی n انجام داد. این الگوریتم در دسته الگوریتم‌های قطعی قرار می‌گیرد.
• الگوریتم تست عدد اول بودن «فِرمت» (Fermat) و «میلر رابین» (Miller Rabin): این دو الگوریتم غیرقطعی، احتمالی و ترکیبی هستند. در این الگوریتم‌ها اگر ثابت شود که عددی مرکب است، پس می‌توان گفت که اول نیست. الگوریتم Miller Rabin بسیار پیچیده‌تر از Fermat است. در حقیقت، Miller Rabin یک رویکرد قطعی نیز دارد، اما روش کار آن مانند یک بازی تجاری بین پیچیدگی زمانی و دقت الگوریتم است.

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

• مهم‌ترین کاربرد استفاده از اعداد اول در زمینه «رمزنگاری» (Cryptography) است. این الگوریتم‌ها در رمزگذاری و «رمزگشایی» (Decryption) الگوریتم RSA استفاده می‌شوند و آن‌ها اولین پیاده‌سازی «سیستم‌های رمزنگاری» (Cryptosystem) «کلید عمومی» (Public Key) را انجام داده‌اند.
• کاربرد دیگر الگوریتم‌های تست عدد اول در «توابع درهم‌سازی» (Hash Function) جدول‌های درهم‌سازی است.

در ادامه مقاله «الگوریتم در برنامه نویسی چیست» به بررسی انواع گوناگون الگوریتم در برنامه نویسی پرداخته شده است.

• مقاله‌های پیشنهادی:
  • الگوریتم تشخیص عدد اول در پایتون — به زبان ساده
  • برنامه تشخیص اعداد اول در پایتون — به زبان ساده
  • الگوریتم شمارش اعداد اول در جاوا اسکریپت — از صفر تا صد

آشنایی با انواع الگوریتم با توجه به نوع مسئله

الگوریتم‌ها از نظر نوع مسئله به ۷ گروه گوناگون تقسیم می‌شوند. ممکن است برخی از گروه‌های این دسته‌بندی با دسته‌بندی بخش قبل نیز یکسان باشد. در این بخش از مقاله سعی شده است که به صورت جامع‌تری انواع الگوریتم‌ها مورد بررسی قرار بگیرند. این الگوریتم‌ها در ادامه نام برده شده‌اند:

• «الگوریتم بروت فورس» (Brute Force Algorithm)
• «الگوریتم بازگشتی» (Recursive Algorithm)
• «الگوریتم برنامه نویسی پویا»
• «الگوریتم تقسیم و حل» (Divide and Conquer Algorithm)
• «الگوریتم حریصانه» (Greedy Algorithm)
• «الگوریتم عقبگرد» (Backtracking Algorithm)
• «الگوریتم تصادفی» (Randomized Algorithm)

در ادامه این بخش از مقاله «الگوریتم در برنامه نویسی چیست» به بررسی الگوریتم‌های فوق پرداخته شده است. ابتدا، بخش بعدی به شرح الگوریتم بروت فورس اختصاص داده شده است.

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

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

این الگوریتم پیچیدگی زمانی و فضایی قابل توجهی ندارد. برای مثال فرض می‌شود که قفلی با رمز عبور ۴ رقمی وجود دارد. اعداد این رمز عبور می‌توانند بین ۰ تا ۹ باشند، بنابراین الگوریتم بروت فورس همه ترکیب‌های ممکن را برای رسیدن به جواب مانند ۰۰۰۱، ۰۰۰۲، ۰۰۰۳، ۰۰۰۴ و سایر اعداد امتحان می‌کند. در بدترین حالت ممکن است این مثال دارای ۱۰۰۰۰ تلاش برای رسیدن به پاسخ صحیح باشد. در بخش بعدی مقاله به بررسی الگوریتم‌های بازگشتی پرداخته می‌شود.

الگوریتم بازگشتی چیست؟

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

از این الگوریتم زمانی استفاده می‌شود که بتوان برنامه‌ها را به چند زیر برنامه تقسیم کرد. به عنوان برخی از مثال‌هایی که با استفاده از الگوریتم بازگشتی حل می‌شوند، می‌توان به حل فاکتوریل یک عدد، «دنباله فیبوناچی» (Fibonacci Seri)، «برج هانوی» (Tower of Hanoi)، «جستجوی عمق اول» در گراف و سایر موارد اشاره کرد. در ادامه این بخش از مقاله «الگوریتم در برنامه نویسی چیست» به شرح الگوریتم تقسیم و حل پرداخته شده است.

• مقاله‌های پیشنهادی:
  • رویه های بازگشتی (Recursive Procedures) — ساختار داده و الگوریتم ها
  • تابع بازگشتی در ++C — راهنمای جامع (+ دانلود فیلم آموزش گام به گام)
  • ساخت الگوریتم بازگشتی در سوئیفت — از صفر تا صد
  • رابطه بازگشتی — از صفر تا صد (+ دانلود فیلم آموزش رایگان)
  • تابع بازگشتی در پایتون — به زبان ساده

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

با استفاده از الگوریتم تقسیم و حل، برنامه‌ها برای رسیدن به پاسخ نهایی به دو بخش تقسیم می‌شوند. ابتدا، برنامه‌ها به بخش‌هایی با رویکردهای مشابه شکسته شده‌اند و سپس در بخش بعدی به طور مستقل هر کدام از بخش‌ها حل می‌شوند و در نهایت همه پاسخ‌ها با یکدیگر ترکیب خواهند شد. برای مثال الگوریتم «جستجوی باینری یا دودویی»، «مرتب‌سازی ادغامی»، «مرتب‌سازی سریع»، «ضرب ماتریس استراسن» (Strassen’s Matrix Multiplication) و سایر موارد می‌توانند با استفاده از این روش حل شوند. در بخش بعدی به بررسی روش الگوریتم حریصانه پرداخته شده است.

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

الگوریتم حریصانه چیست؟

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

• اولین مؤلفه یک مجموعه پیشنهادی است که سعی می‌شود راه حل مورد نظر با استفاده از آن یافت شود.
• در این الگوریتم «تابع انتخاب» (Selection Function) وجود دارد که به انتخاب بهترین پیشنهاد ممکن کمک می‌کند.
• این الگوریتم «تابع امکان‌سنجی» (Feasibility Function) دارد که به تصمیم‌گیری درباره پیشنهادات برای یافتن راه حل کمک می‌کند.
• یک «تابع هدف» (Objective Function) نیز در این الگوریتم وجود دارد که به یک راه حل جزئی یا کلی مقدار می‌دهد.
• آخرین تابع موجود در الگوریتم حریصانه، «تابع راه حل» (Solution Function) است و زمانی را اعلام می‌کند که راه حلی برای مسئله یافت شده است.

به عنوان مثال‌هایی برای این نوع از الگوریتم‌ها می‌توان «الگوریتم کد گذاری هافمن» (Huffman Coding) و «الگوریتم کوتاه‌ترین مسیر دایجسترا» (Dijkstra’s Shortest Path Algorithm)، «الگوریتم پریم» (Prim’s Algorithm)، «الگوریتم کروسال» (Kruskal’s Algorithm) را نام برد. در کدنویسی هافمن، الگوریتم با استفاده از پیامی و فرکانس‌هایی که برای کاراکترهای آن در بسته وجود دارند، برای هر کاراکتر، کدگذاری (Encoding) با طول متغیر انجام می‌دهد. برای انجام حل برنامه با استفاده از این الگوریتم، ابتدا باید یک درخت هافمن از کاراکترهای ورودی ایجاد شود و سپس درخت را پیمایش کرد تا کدهایی به کاراکترها اختصاص داده شوند. در بخش بعدی مقاله به شرح و بررسی الگوریتم عقبگرد پرداخته شده است.

• مقاله‌های پیشنهادی:
  • درخت پوشا و معرفی الگوریتم های Kruskal و Prim — به زبان ساده
  • الگوریتم کوتاه ترین مسیر دایجسترا در سوئیفت — به زبان ساده
  • الگوریتم پریم در جاوا — راهنمای جامع
  • رنگ آمیزی گراف به روش حریصانه — به زبان ساده

الگوریتم عقبگرد چیست؟

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

مسئله چند وزیر به این صورت است که چندین وزیر در صفحه شطرنج وجود دارند و آن‌ها باید طوری در صفحه قرار بگیرند که هیچ کدام نتوانند به دیگری حمله کنند. به عنوان مثال‌های دیگری می‌توان به مسئله «دور همیلتونی» (Hamiltonian Cycle)، «رنگ‌آمیزی گراف» (M-Coloring Problem)، «موش در مِیز» (Rat in Maze Problem) نیز پرداخت که با استفاده از الگوریتم عقبگرد حل می‌شوند. در بخش بعدی این مقاله، به بررسی الگوریتم تصادفی پرداخته شده است.

مقاله پیشنهادی: الگوریتم حل ماز (Maze) در جاوا — از صفر تا صد

الگوریتم تصادفی چیست؟

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

مثال های الگوریتم در برنامه نویسی

در این بخش، ۶ مثال ساده و کاربردی به وسیله روش نوشتن الگوریتم با شبه‌کد برای درک بهتر عملکرد الگوریتم در برنامه نویسی ارائه شده‌اند. این الگوریتم‌ها را می‌توان با هر زبان برنامه نویسی پیاده‌سازی کرد.

مثال اول الگوریتم در برنامه نویسی

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

Step 1: Start
Step 2: Declare variables num1, num2 and sum. 
Step 3: Read values num1 and num2. 
Step 4: Add num1 and num2 and assign the result to sum.
sum←num1+num2 
Step 5: Display sum 
Step 6: Stop

مثال دوم الگوریتم در برنامه نویسی

الگوریتم پیدا کردن بزرگترین عدد از میان سه عدد موجود به صورت زیر و در ۵ مرحله نمایش داده شده است:

Step 1: Start
Step 2: Declare variables a,b and c.
Step 3: Read variables a,b and c.
Step 4: If a > b
If a > c
Display a is the largest number.
Else
Display c is the largest number.
Else
If b > c
Display b is the largest number.
Else
Display c is the greatest number. 
Step 5: Stop

مثال سوم الگوریتم در برنامه نویسی

الگوریتم پیدا کردن ریشه‌های معادله درجه دوم $$ax^2 + bx + c = 0$$ در ۳ مرحله به صورت زیر نوشته شده است:

Step 1: Start
Step 2: Declare variables a, b, c, D, x1, x2, rp and ip;
Step 3: Calculate discriminant
         D ← b2-4ac
Step 4: If D ≥ 0
              r1 ← (-b+√D)/2a
              r2 ← (-b-√D)/2a 
              Display r1 and r2 as roots.
        Else     
              Calculate real part and imaginary part
              rp ← -b/2a
              ip ← √(-D)/2a
              Display rp+j(ip) and rp-j(ip) as roots
Step 5: Stop

مثال چهارم الگوریتم در برنامه نویسی

الگوریتم محاسبه فاکتوریل یک عدد در ۷ مرحله در ادامه نشان داده شده است:

Step 1: Start
Step 2: Declare variables n, factorial and i.
Step 3: Initialize variables
factorial ← 1
i ← 1
Step 4: Read value of n
Step 5: Repeat the steps until i = n
5.1: factorial ← factorial*i
5.2: i ← i+1
Step 6: Display factorial
Step 7: Stop

مثال پنجم الگوریتم در برنامه نویسی

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

Step 1: Start
Step 2: Declare variables n, i, flag.
Step 3: Initialize variables
flag ← 1
i ← 2 
Step 4: Read n from the user.
Step 5: Repeat the steps until i=(n/2)
5.1 If remainder of n÷i equals 0
flag ← 0
Go to step 6
5.2 i ← i+1
Step 6: If flag = 0
Display n is not prime
else
Display n is prime
Step 7: Stop

مثال ششم الگوریتم در برنامه نویسی

الگوریتم سری فیبوناچی با شبه‌کد زیر نشان داده شده است. این مثال در شش مرحله ارائه می‌شود و برای اعداد کم‌تر از ۱۰۰۰ ارائه شده است.

Step 1: Start 
Step 2: Declare variables first_term,second_term and temp. 
Step 3: Initialize variables first_term ← 0 second_term ← 1 
Step 4: Display first_term and second_term 
Step 5: Repeat the steps until second_term ≤ 1000 
5.1: temp ← second_term 
5.2: second_term ← second_term + first_term 
5.3: first_term ← temp 
5.4: Display second_term 
Step 6: Stop

مقاله پیشنهادی: برنامه محاسبه nامین عدد فیبوناچی — به زبان ساده

جمع‌بندی

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

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