آموزش طراحی الگوریتم از پایه — اصول ۷ گانه طراحی الگوریتم

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

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

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

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

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

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

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

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

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

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

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

• مجموعه آموزش ساختمان داده و طراحی الگوریتم فرادرس — کلیک کنید

نکات مهم آموزش طراحی الگوریتم از پایه

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

۱- پیچیدگی زمانی و مرتبه اجرایی الگوریتم

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

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

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

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

مرتبه اجرایی را با O نشان می‌دهند و به‌صورت زیر به‌دست می‌آورند:

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

• آموزش مروری بر پیچیدگی محاسبات Computational Complexity — کلیک کنید

۲- طراحی الگوریتم با روش تقسیم و حل

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

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

باید توجه داشته باشیم که در همه مسائل نمی‌توان از روش حل و تقسیم استفاده کرد و سپس نتایج حاصله را با هم ترکیب کرد. مثلاً در مواردی که نمونه‌ای با اندازه n به دو یا چند قسمت تقریبا هم‌اندازه n تقسیم‌شده باشد یا در مواردی که نمونه‌ای با اندازه n، تقریباً با n نمونه با اندازه n/c تقسیم شود و c یک مقدار ثابت باشد و در نهایت در مسائلی که نمونه‌های کوچک‌تر باهم ارتباط دارند نباید از روش تقسیم و حل استفاده کرد.

• آموزش روش تقسیم و حل در طراحی الگوریتم — کلیک کنید

۳- استفاده از روابط بازگشتی در طراحی الگوریتم

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

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

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

• آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته — کلیک کنید

۴- استفاده از برنامه نویسی پویا برای طراحی الگوریتم

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

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

۵- روش حریصانه در طراحی الگوریتم

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

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

در حالت کلی برای هر مسئله باید ثابت کنیم که آیا الگوریتم حریصانه برای آن جواب بهینه می‌دهد یا نمی‌دهد و این موضوع سخت‌ترین مرحله است.

مراحل روش حریصانه

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

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

۶- استفاده از راهبرد عقب گرد در طراحی الگوریتم

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

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

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

۷- نظریه NP در طراحی الگوریتم

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

1. مسائلی که الگوریتم هایی با پیچیدگی زمانی چندجمله ای برای آنها پیدا شده‌است.
2. مسائلی که کنترل ناپذیری آنها اثبات نشده است.
3. مسائلی که کنترل ناپذیری آنها اثبات نشده است ولی تاکنون هیچ الگوریتم زمانی چندجمله‌ای هم برای آنها پیدا نشده است.

الگوریتم‌هایی که هرگز ابداع نشده‌اند ولی غیرممکن بودن آنها هم هنوز به اثبات نرسیده است را مسائل جالب ” NP ” می‌گویند، به مسائلی هم که نوشتن یک الگوریتم کارآمد برای آنها غیرممکن است، و کامپیوتر در حل آنها با مشکل مواجه می‌شود، کنترل ناپذیر می‌گویند.

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

P مجموعه تمامی مسائل تصمیم‌گیری است که توسط الگوریتم‌های زمانی چندجمله‌ای قابل‌حل هستند. هدف از تعریف P و NP، طبقه‌بندی کردن الگوریتم‌هاست. مسائل P جزء NP هستند چون این مسائل را می‌توان در زمان چندجمله‌ای حل کرد. برای آموزش کامل طراحی الگوریتم پیشنهاد می‌کنیم آموزش طراحی الگوریتم فرادرس تهیه کرده و از آن استفاده کنید. این آموزش توسط دکتر فرشید شیر افکن در ۱۵ ساعت و ۱۲ دقیقه تدریس شده و شامل نکات مهم و کلیدی گفته شده در این آموزش می‌باشد.

• آموزش طراحی الگوریتم — کلیک کنید

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

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

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