طراحی الگوریتم کامپیوتر را چقدر می‌شناسید؟ الگوریتم دنبال‌کردن مجموعه‌ای از دستورالعمل‌ها برای حل یک مسئله است که اغلب به‌عنوان «فرایند حل مسئله» نیز شناخته می‌شود؛ همچنین این اصطلاح تقریباً همیشه با کامپیوتر مرتبط است؛ زیرا الگوریتم‌های پردازش‌شده توسط کامپیوتر می‌توانند مسائل بسیار بزرگ و پیچیده را با سرعت بیشتری از انسان حل کنند. از آنجا که امروزه محاسبات مدرن از الگوریتم‌ها استفاده می‌کنند، زمینه‌ای برای طراحی، تجزیه‌وتحلیل و اصلاح آن‌ها با عنوان طراحی الگوریتم ایجاد شده است. یک الگوریتم دنباله‌ای از دستورالعمل‌هاست؛ درواقع دستورالعمل خود یک الگوریتم است، حتی فهرستی از دستورالعمل‌های رانندگی هم جزو آن است! طراحی الگوریتم را می‌توان یکی از اصلی‌ترین دروس رشته کامپیوتر و اساس برنامه‌نویسی دانست. در ادامه به‌صورت طراحی الگوریتم کامپیوتر آشنا می‌شوید.
- 1. طراحی الگوریتم کامپیوتر چیست؟
- 2. نحوه طراحی الگوریتم در علوم کامپیوتر
- 3. ویژگی‌های الگوریتم کامپیوتر
-
4.
انواع الگوریتم‌های مورداستفاده در علوم کامپیوتر
- 4.1. الگوریتم بیرحمانه (Brute Force Algorithm)
- 4.2. الگوریتم بازگشتی (Recursive Algorithm)
- 4.3. الگوریتم برنامه‌نویسی پویا (Dynamic Programming Algorithm)
- 4.4. الگوریتم تقسیم و غلبه (Divide and Conquer Algorithm)
- 4.5. الگوریتم حریصانه (Greedy Algorithm)
- 4.6. الگوریتم عقب‌گرد (Backtracking Algorithm)
- 4.7. الگوریتم تصادفی (Randomized Algorithm)
- 5. ساختمان داده و طراحی الگوریتم کامپیوتر در برنامه‌نویسی
- 6. منابع آموزشی برای طراحی الگوریتم کامپیوتر
طراحی الگوریتم کامپیوتر چیست؟
طراحی الگوریتم شاخه‌ای از ریاضیات و علوم کامپیوتر است که به تحقیق، توسعه و پیاده‌سازی الگوریتم‌ها می‌پردازد؛ به‌عبارت دیگر، الگوریتم‌ها الگوهایی صریح و قابل‌اجرا برای تکمیل یک کار به‌روشی کارآمد هستند.
برخی از مسائل بدون پیچیدگی هستند و راه‌حل‌های مشخص و ساده‌ای دارند، درحالی‌که برای برخی دیگر از مسائل راه‌حل‌های مختلف وجود دارد و درنتیجه، الگوریتم‌های متفاوتی می‌توان برای‌شان طراحی کرد. این الگوریتم‌ها کارایی و کیفیت یکسانی ندارند و از جنبه‌های گوناگون می‌توان آن‌ها را با هم مقایسه کرد.
اهمیت طراحی یک الگوریتم خوب برای مسائل پیچیده و مسائلی که محاسبات زیاد و حجیمی دارند به اوج خود می‌رسد. طراحی الگوریتم تا آنجا پیش می‌رود که برای یک مسئله‌ی مشخص یک الگوریتم ممکن است کاملاً کاربردی باشد، حال‌آنکه الگوریتم دیگری که برای حل همان مسئله طراحی شده است کاملاً بی‌مصرف باشد.
مرحله‌های مختلف حل یک مسئله و درواقع نوشتن برنامه به‌این صورت است:
- تبدیل مسئله به یک مدل ریاضی (مدل انتزاعی) حل‌شدنی با کامپیوتر
- طراحی الگوریتمی برای حل آن مسئله
- انتخاب داده ساختار (Data Structure) مناسب برای الگوریتمی که ارائه کرده‌ایم برای ذخیره و دستکاری داده‌های مسئله
مدت‌ها قبل، افراد اغلب فهرستی از اقدامات مهم خود را یادداشت می‌کردند تا خطر فراموشی چیزهای مهم را کاهش دهند؛ این همان چیزی است که یک الگوریتم را شکل می‌دهد. طراحان رویکرد مشابهی را برای توسعه‌ی الگوریتم‌ها برای اهداف محاسباتی اتخاذ می‌کنند:
- اول آن‌ها را به‌صورت یک مسئله نگاه می‌کنند.
- سپس مراحلی را که برای حل آن لازم است تشریح می‌کنند.
- درنهایت، مجموعه‌ای از عملیات ریاضی را برای انجام‌دادن آن مراحل توسعه می‌دهند.
نحوه طراحی الگوریتم در علوم کامپیوتر
دلیل اینکه الگوریتم‌ها اغلب در علوم کامپیوتر استفاده می‌شوند این است که رایانه‌ها را می‌توان طوری برنامه‌ریزی کرد که هر دستورالعملی را به‌صورت متوالی اجرا کنند. طراحی الگوریتم کامپیوتر به برنامه‌نویسان اجازه می‌دهد به رایانه‌ها آموزش دهند که فرضاً چگونه گرافیک‌های سه‌بعدی را ارائه کنند، متن را نمایش دهند و عملیات مختلفی را روی اعداد انجام دهند.
کوچک‌ترین واحد یک برنامه کامپیوتری یک دستورالعمل از عملیات ساده‌ای است که روی بیت‌های موجود در یک ثبات (رجیستر) پردازنده انجام می‌شود (عملیاتی که می‌توان روی بیت‌های داده انجام داد به معماری پردازنده بستگی دارد و معمولاً تغییر بیت‌های خاص از صفر به یک، جابه‌جایی بیت‌ها به چپ یا راست و دیگر تبدیل‌های ساده و مشابه باینری را شامل است؛ برای مثال، برای ضرب یک عدد باینری در ۲ هر یک از بیت‌های یک ثبات به‌اندازه یک بیت به چپ منتقل می‌شوند).
برای آشنایی با بهترین منابع کنکور کارشناسی ارشد مهندسی کامپیوتر و IT این مطلب را بخوانید:
بهترین منابع کنکور کارشناسی ارشد کامپیوتر و IT را بشناسید!
ویژگی‌های الگوریتم کامپیوتر
خصوصیاتی که هر الگوریتم باید از آن‌ها پیروی کند عبارت‌اند از:
- ورودی مشخص: ورودی اطلاعاتی است که در طول محاسبه برای ایجاد خروجی تغییر می‌کند. یک الگوریتم یا باید ورودهای مشخصی داشته باشد یا هیچ ورودی نداشته باشد. دقت ورودی مستلزم آن است که بدانید اطلاعات باید چه نوع اطلاعاتی، چه مقدار و چه ساختاری باشند.
- خروجی مشخص: خروجی اطلاعاتی است که از نتیجه‌ی محاسبه به دست می‌آید. یک الگوریتم باید دست‌کم یک خروجی مشخص داشته باشد. دقت خروجی نیز مستلزم این است که شما بفهمید خروجی چه نوع اطلاعاتی، چه مقدار و چه ساختاری باید داشته باشد.
- واضح و بدون ابهام بودن: الگوریتم‌ها باید هر مرحله را به‌روشنی مشخص کنند (هر یک از مراحل آن باید کاملاً واضح، به‌صورت کمی و نه نسبی و نه ذهنی، باشد) و فقط به یک هدف و منظور هدایت شوند؛ جزئیات هر مرحله نیز باید توضیح داده شود.
- کارآمدی: الگوریتم باید مؤثر باشد؛ به‌این معنی که تمامی ابزارهایی که برای رسیدن به خروجی موردنیاز هستند باید با منابع در دسترس اجرا‌شدنی باشند. این امر نباید هیچ گونه تلاش بیهوده و اضافی را دربرگیرد؛ زیرا می‌تواند یک الگوریتم را ناکارآمد و بی‌اثر کند.
- مستقل و قابل‌توسعه: یک الگوریتم باید فرایندی گام‌به‌گام و مستقل از هر کد برنامه‌نویسی داشته باشد. هدف نهایی باید این باشد که ممکن است تقاضا برای هر یک از گویش‌های برنامه‌نویسی به‌طور ناگهانی افزایش یابد.
- متناهی و توقف‌پذیر: درنهایت الگوریتم باید متوقف شود. توقف ممکن است به‌این معنی باشد که یک خروجی را دریافت می‌کنید. الگوریتم‌ها باید پس از تعداد محدودی از مرحله‌ها به پایان برسند. هیچ دلیلی برای ایجاد الگوریتمی وجود ندارد که نامحدود باشد؛ زیرا برای ما بی‌معنی خواهد بود.
انواع الگوریتم‌های مورداستفاده در علوم کامپیوتر
الگوریتم‌ها انواع زیادی دارند. هفت مورد از پرکاربردترین انواع الگوریتم عبارت‌اند از:
- الگوریتم بیرحمانه
- الگوریتم بازگشتی
- الگوریتم برنامه‌نویسی پویا
- الگوریتم تقسیم و غلبه
- الگوریتم حریصانه
- الگوریتم عقب‌گرد
- الگوریتم تصادفی
در ادامه این هفت نوع از طراحی الگوریتم کامپیوتر را توضیح داده‌ایم.
الگوریتم بیرحمانه (Brute Force Algorithm)
یک الگوریتم بیرحمانه اساساً تمامی شانس‌ها را تا زمانی که یک نتیجه‌ی پذیرفتنی پیدا شود تست می‌کند. Brute Force اساسی‌ترین و ساده‌ترین نوع الگوریتم است. این الگوریتم برای یافتن راه‌حل ایده‌آل یا بهترین راه‌حل استفاده می‌شود؛ زیرا تمامی راه‌حل‌های بالقوه را بررسی می‌کند.
الگوریتم بازگشتی (Recursive Algorithm)
این نوع الگوریتم به بازگشت بستگی دارد. در بازگشت یک مسئله به مسائل فرعی و کوچک‌تر از نوع مشابه شکسته و بازگشت داده می‌شود و سپس با فراخوانی خود تا زمانی که موضوع با کمک یک شرط اولیه حل شود بارها ادامه پیدا می‌کند.
الگوریتم برنامه‌نویسی پویا (Dynamic Programming Algorithm)
به این نوع الگوریتم تکنیک به‌خاطرسپاری نیز می‌گویند. این نام‌گذاری به‌این دلیل است که نتیجه‌ای را که اخیراً محاسبه شده است ذخیره کنیم تا محاسبه‌ی آن را بارها طی فراخوانی‌ها انجام ندهیم!
الگوریتم تقسیم و غلبه (Divide and Conquer Algorithm)
این الگوریتم نیز یک شیوه‌ی حل مسئله است که برای حل مسائل بازگشتی استفاده می‌شود. این الگوریتم به‌این صورت است که مسئله را به اندازه‌های کوچک‌تر تقسیم می‌کنیم و در صورت لزوم تقسیم‌ها را به‌صورت بازگشتی ادامه می‌دهیم تا به مسائل کوچک‌تری برسیم که حل آن‌ها را می دانیم؛ سپس در صورت لزوم مسائل کوچک حل‌شده را با هم ادغام می‌کنیم تا مسئله‌ی بزرگ اصلی حل شود.
الگوریتم حریصانه (Greedy Algorithm)
الگوریتم حریصانه یک روش حل مسئله است که مانند برنامه‌نویسی پویا مسائل بهینه‌سازی را حل می‌کند، اما برخلاف آن حریصانه‌ها ضعیف‌تر هستند و خیلی از مسائل را نمی‌توانند حل کنند. در این الگوریتم یک مجموعه ورودی وجود دارد که هر بار طبق معیار خاصی، مثلاً min یا max، به‌طور کلی عنصری را که تصور می‌شود بهترین انتخاب است انتخاب می‌کند و به آینده توجهی نمی‌کند که آیا این انتخاب درنهایت خوب خواهد بود یا خیر؛ سپس بررسی می‌کند که آیا این عنصر می‌تواند ما را به جواب برساند یا خیر؛ اگر نه، آن عضو را برای همیشه کنار می‌گذارد و اگر جواب بله باشد، آن را به مجموعه‌ی جواب اضافه می‌کند.
الگوریتم عقب‌گرد (Backtracking Algorithm)
فرض کنید می‌خواهید راه خود را از هزارتوی شمشادی بیابید. راهی ندارید جز دنبال‌کردن مسیری بی‌امید تا اینکه به یک بن‌بست برسید. در این حالت بازمی‌گردید و راهی دیگر را انتخاب می‌کنید. اساس کار این الگوریتم چنین است. حال در همان مثال فکر کنید اگر تابلویی وجود داشت که به شما بگوید مسیری که در پیش گرفته‌اید به بن‌بست منتهی می‌شود، چقدر کارها آسان‌تر می‌شود. در روش بازگشت به عقب این تابلوها وجود دارند.
الگوریتم تصادفی (Randomized Algorithm)
در این نوع الگوریتم برای تصمیم گیری یک عدد تصادفی حداقل یک بار در طول محاسبات در نظر گرفته می‌شود.
ساختمان داده و طراحی الگوریتم کامپیوتر در برنامه‌نویسی
زبان‌های برنامه‌نویسی سطح بالا، مانند C++، جاوا و پایتون، به برنامه‌نویسان اجازه می‌دهند تا برنامه‌های بسیار پیچیده را با کد نسبتاً کمی بنویسند.
متداول‌ترین الگوریتم‌ها در برنامه‌نویسی توابع مرتب‌سازی و جست‌وجو هستند و همیشه تلاش‌هایی برای کارآمدترکردن آن‌ها صورت می‌گیرد. به‌گفته‌ی مؤسسه‌ی Clay Mathematics، یکی از مهم‌ترین مفاهیم در علوم کامپیوتر، مسئله‌ی P در مقابل NP است که اگر آن‌ها یکسان باشند، دانشمندان کامپیوتر می‌توانند با استفاده از الگوریتم‌های شناخته‌شده‌ی فعلی، مسائلی را حل کنند که حل آن‌ها میلیون‌ها سال طول می‌کشد.
برای آشنایی با درس ساختمان داده این مطلب را مطالعه کنید:
ساختمان داده چیست و چه انواع، ویژگی‌ها و کاربردهایی دارد؟
منابع آموزشی برای طراحی الگوریتم کامپیوتر
دانشجویان رشته‌های کامپیوتر در پی در‌نظر‌گرفتن کاربردها و ضرورت یادگیری الگوریتم‌ها و به‌کارگیری‌شان با ضرورت آشنایی و آموزش درس طراحی الگوریتم‌ها پی می‌برند و برای یادگیری آن اقدام می‌کنند. ازجمله منابع آموزشی بسیار مفید برای آموزش طراحی الگوریتم کامپیوتر ویدئوهای رایگان و همین‌طور ویدئوی ضبط‌شده کلاس‌های درس‌وتست و همین‌طور نکته‌وتست درس طراحی الگوریتم کامپیوتر است.
با کلیک روی این لینک، علاوه بر آشنایی کامل با وضعیت این درس در کنکور کارشناسی ارشد کامپیوتر و IT، به بهترین منابع یادگیری درس طراحی الگوریتم کامپیوتر آشنا می‌شوید: