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

آموزش الگوریتم پیشرفته

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

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

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

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

الگوریتم در ریاضی

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

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

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

تا به اینجا در این مقاله به صورت کامل به این پرسش پرداختیم که الگوریتم چیست، در این قسمت می‌خواهیم بگوییم الگوریتم چه کاربردی دارد؟ در زیر به برخی از کاربردهای الگوریتم‌ها اشاره می‌کنیم:

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

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

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

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

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

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

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

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

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

چندین الگوریتم در برنامه نویسی وجود دارد که عبارتند از:

• تعریف کردن مسئله
• جمع‌آوری اطلاعات (داده)
• پردازش اطلاعات (داده)
• استفاده از رویکرد منطقی
• حل مسئله (راه‌حل)

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

ساختار الگوریتم‌ها

الگوریتم‌ها با توجه به ساختار منطقی که دارند در 3 دسته جا می‌گیرند:

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

انواع الگوریتم‌ها از نظر نوع مسئله

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

الگوریتم بازگشتی  (Recursive)

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

الگوریتم دینامیک  (Dynamic)

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

الگوریتم برگشت به عقب  (Backtracking)

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

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

الگوریتم تقسیم و حل (Divide and conquer )

الگوریتم‌های تقسیم و حل ابتدا مسئله را با توجه به نوع آن، چند بخش کوچک‌تر تقسیم کرده و به حل آن‌ها می‌پردازند. سپس از ترکیب پاسخ بخش‌های کوچک‌تر، پاسخ کلی مسئله به‌دست می‌آید. برخی از روش‌های مرتب‌سازی مانند مرتب‌سازی ادغامی (Merge Sort) و مرتب‌سازی سریع (Quick Sort) نیز از این دسته الگوریتم‌ها محسوب می‌شوند.

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

الگوریتم حریصانه (Greedy)

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

مسئله خرد کردن سکه‌ها یکی از مثال‌های معروف در به‌کارگیری الگوریتم حریصانه است. این مسئله می‌گوید فرض کنید که شما باید مبلغی مثلا 36 تومان را با سکه‌های 20 تومانی، 10 تومانی، 5 تومانی و 1 تومانی پرداخت کنید به طوری که کمترین تعداد سکه را بپردازید. کمترین تعدادی که بتوان با آن 36 تومان را پرداخت کرد پاسخی بهینه برای مسئله ما خواهد بود که در اینجا، برداشتن یک سکه از هر 4 مدل است.

الگوریتم بروت فورس (Brute force)

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