سون لرن بزرگترین مجموعه آموزش برنامه نویسی در کشور
الگوریتم در برنامه نویسی چیست و چه کاربردی دارد؟
بشر در طول زندگی خود با مشکلات بسیاری مواجه می‌شود که ممکن است بسیاری از آنها بارها تکرار شوند. برای حل کردن مشکلاتی که چندین بار با آنها مواجه شده‌ایم، ثبت و دسته‌بندی راه حل‌های مشخص کمک می‌کند که بتوانیم سریع‌تر و مطمئن‌تر با مسائل تکراری برخورد کنیم. ما به این راه حل‌های تست‌شده و مطمئن، الگوریتم می‌گوییم. در این مطلب یاد می‌گیریم که الگوریتم چیست و در برنامه نویسی چه مفهومی دارد و با انواع آن آشنا می‌شویم.
معنی و تعریف الگوریتم چیست؟
ما معمولاً برای حل مشکلات به دنبال ساده‌ترین و سریع‌ترین راه‌حل‌ها هستیم. سال‌ها است که علم با یافتن پاسخ سؤالات خود و استفاده از آنها در پیشامدهایی که الگوی تکراری دارند، اهداف خود را پیش می‌برد و سریع‌تر از انتظار ما رازهای طبیعت را از دل آن بیرون می‌کشد. راه‌حل‌هایی که تست‌شده و مطمئن هستند و می‌توانند سوالاتی با مفاهیم یکسان را حل کنند، الگوریتم نامیده می‌شوند. ریشه کلمه الگوریتم از نام خوارزمی دانشمند ایرانی به دست آمده است.
اگر بخواهیم معنی الگوریتم را در زمینه ریاضیات و علوم کامپیوتر بررسی کنیم، می‌توان گفت الگوریتم‌ها مجموعه فرایندهایی هستند که به کمک آنها می‌توان بسیاری از مسائل برنامه‌نویسی را به‌راحتی حل کرد. به‌عنوان‌مثال الگوریتم یک موتور جستجو را در نظر بگیرید. الگوریتم موتور جستجو گوگل به‌طور ساده این‌گونه ست که عبارت تایپ شده شما را دریافت کرده و آن را در پایگاه داده‌های خود جستجو می‌کند.
سپس صفحات وب مربوطه را پیداکرده و به شما نشان می‌دهد. این روند کلی از ایجاد سؤال تا رسیدن به پاسخ یک الگوریتم محسوب می‌شود. استفاده از الگوریتم‌ها در کاهش هزینه‌های مالی و زمانی یک پروژه اهمیت زیادی دارد. الگوریتم‌ها با انجام سلسله اقدامات مشخصی و در ازای گرفتن ورودی تعریف‌شده، نتیجه‌ای مطابق انتظار به ما خواهند داد.
یک الگوریتم چگونه کار می‌کند؟
دنیای کامپیوتر پر از کلمات کلیدی مانند هوش مصنوعی، ابررایانه، یادگیری ماشین، محاسبات کوانتومی و خیلی از لغات دیگر است اما شاید در این میان، کلمه الگوریتم جزو یکی از واژگان پرتکرار و معروف در علم کامپیوتر است.
در کلی‌ترین مفهوم، یک الگوریتم مجموعه‌ای از دستورالعمل‌ها است که به رایانه می‌گوید، چگونه مجموعه‌ای از حقایق جهان را به اطلاعات مفید تبدیل کند. مرتب‌سازی مجموعه اعداد گرفته شده، یافتن مسیرها از طریق نقشه و حتی نمایش اطلاعات بر روی صفحه نمایش نمونه‌هایی از اجرای یک الگوریتم خاص هستند.
پوشیدن لباس در هنگام صبح و آماده شدن برای رفتن به محل کار و یا دانشگاه یکی از مثال‌هایی است که از اجرای یک الگوریتم ساده در مغز انسان نشأت می‌گیرد. اما اگر قرار باشد این روند را یادداشت کنید و به یک کودک 5 ساله آموزش دهید، چگونه آن را انجام می‌دادید؟ پاسخ این سوال به روشی دقیق، ساختار الگوریتم را تشکیل می‌دهد.
اگر به مباحث الگوریتم نویسی و برنامه نویسی علاقه مندید پیشنهاد میکنیم به صفحه دوره الفبای برنامه نویسی سر بزنید و از این دوره شروع به یادگیری برنامه نویسی کنید.
ویژگی های الگوریتم
- ورودی‌ها به خوبی تعریف شده باشند : ورودی داده‌ای است که در طول محاسبات برای تولید خروجی توسط کدهای دستوری مصرف می‌شود. یک الگوریتم باید دارای ورودی‌های کاملاً تعریف شده باشد که در آن نوع داده، میزان دریافتی و نحوه ورود آنها توسط الگوریتم به طور واضح مشخص است.
- خروجی‌ها به خوبی تعریف شده باشند : خروجی داده‌های حاصل از محاسبه (نتیجه مورد نظر شما) است. یک الگوریتم باید یک یا چند خروجی کاملاً تعریف شده داشته باشد و با خروجی مورد نظر مطابقت داشته باشد. میزان سنجش دقت خروجی مستلزم داشتن اطلاعاتی نظیر نوع داده، مقدار و نحوه نمایش آن است. (اگر الگوریتم دارای چند خروجی باشد باید خصوصیات هریک از آنها به طور کاملاُ مشخص تعیین شده باشد.)
- واضح و بدون ابهام : الگوریتم باید دارای قطعیت باشد و هر یک از مراحل آن از همه جهات روشن و جزئیات هر مرحله مشخص شود (از جمله نحوه رسیدگی به خطاها). قطعیت یعنی مشخص کردن توالی عملیات برای تبدیل ورودی به خروجی. این الگوریتم باید شامل همه چیزهای کمی باشد و نه کیفی. اگر خودتان در مورد آن ابهام دارید، نمی توانید انتظار داشته باشید که کامپیوتر چیزی را بفهمد!
- امکان‌پذیر : الگوریتم باید ساده، عمومی و کاربردی باشد تا بتوان با منابع موجود آن را اجرا کرد. اگر الگوریتم دارای مراحل زائد و غیرضروری باشد آن را عملاً بی‌اثر و ناکارآمد خواهد کرد. درحال پختن غذا هستید و سبزیجاتی را که در دستور غذا استفاده نشده‌اند، خرد می‌کنید و این کار عملاً اتلاف وقت است.
- متناهی بودن : هر الگوریتمی باید در نهایت متوقف شود و توقف به این معناست که یا الگوریتم خروجی مورد انتظار را تولید کرده و یا جوابی برای آن مسئله پیدا نکرده است. بهرحال الگوریتم ها بایستی پس از طی تعداد محدودی از مراحل خاتمه پیدا کنند و زمان اجرای آنها محدود باشد و پس از گذشت زمانی معقول خاتمه یابد.
- مستقل از زبان : الگوریتم طراحی‌شده باید مستقل از زبان باشد، یعنی بصورت مجموعه‌ای از دستورالعمل‌های ساده‌ای باشد که قابلیت پیاده‌سازی در هر زبان برنامه‌نویسی را داشته باشد و در عین حال خروجی یکسانی را بدهد.
- پیچیدگی زمانی و مکانی
ساختار منطقی الگوریتم‌ها چیست؟
الگوریتم‌ها با توجه به ساختار منطقی که دارند در 3 دسته جا می‌گیرند:
- دنباله ای (Sequence): ساختاری مرحله به مرحله، که ترتیب گام‌ها برای رسیدن به پاسخ در آن مشحص است.
- شاخه ای(Branching): این الگوریتم‌ها طبق قانون اگر-آنگاه در ریاضیات کار می‌کنند. به این صورت که پس از تعیین شرط، پاسخ با توجه به نتیجه شرط تعیین می‌شود.
- حلقه ای (Loop): الگوریتم‌های حلقه ای یا تکراری، در تعداد دفعات مشخصی شرطی را در پروژه اعمال می‌کنند و پس از تمام شدن فرایند، برنامه را پایان می‌دهند.
انواع الگوریتم‌ها از نظر نوع مسئله
الگوریتم‌ها دارای نقش مهمی در برنامه‌نویسی و حل مسئله هستند و از لحاظ کارایی و با توجه به نوع مسئله انواع مختلفی دارند که ما در این بخش به بررسی تعدادی از آنها می‌پردازیم.
الگوریتم بازگشتی (Recursive)
الگوریتم‌های بازگشتی حالت پایه یا به اصطلاح base case مسئله را حل کرده و سپس با استفاده از این جواب، به حل مسائل تودرتو می‌پردازند. درواقع مسئله به چند بخش کوچک شکسته می‌شود که با استفاده از پاسخ مرحله قبل، مسئله بعدی قابل‌حل است. یکی از معروف‌ترین مسائل بازگشتی، تابع فاکتوریل (factorial) است. در کد زیر عبارت If x is 0 حالت پایه محسوب می‌شود:
Fact(x)
If x is 0
return 1
return (x*Fact(x-1))
الگوریتم دینامیک (Dynamic)
از الگوریتم‌های پویا یا دینامیک می‌توان برای محاسبه بخشی از برنامه و استفاده از پاسخ آن، در مسائل آینده استفاده کرد. یعنی از پاسخ‌های یک بخش، می‌توانید برای حل مسائل دیگر نیز بهره برد. دنباله فیبوناچی از الگوریتم‌های دینامیک استفاده می‌کند:
Fib(n)
if n=0
return 0
else
prev_Fib=0,curr_Fib=1
repeat n-1 times /*if n=0 it will skip*/
next_Fib=prev_Fib+curr_Fib
prev_Fib=curr_Fib
curr_Fib=new_Fib
return curr_Fib
الگوریتم برگشت به عقب (Backtracking)
الگوریتم عقب‌گرد به دنبال پیدا کردن سرنخ‌های امیدبخشی است تا بهینه‌ترین جواب را پیدا کند. این شیوه برای حل مسائل درخت فضای آن مسئله را ایجاد کرده و تعیین می‌کند کدام گره امیدبخش است. الگوریتم‌های عقب‌گرد از علامت‌هایی برای بیان اینکه یک راه‌حل کاندید به حل مسئله نمی‌انجامد استفاده می‌کنند.
مثلاً در ساخت درخت فضای حالت یک سؤال، اگر شاخه‌ای از درخت جواب بهینه‌ای در پی نداشته باشد، علامت‌گذاری می‌شود تا در عمق زیاد بررسی نشود و به جای آن، شاخه امیدبخش‌تر بررسی می‌شود. البته شاخه اول به‌طورکلی هرس نمی‌شود بلکه موقتاً کنار گذاشته می‌شود تا در صورت پیدا نکردن بهینه‌ترین جواب در شاخه دیگر، مجدداً به آن بازگردیم.
الگوریتم تقسیم و حل (Divide and conquer )
الگوریتم‌های تقسیم و حل ابتدا مسئله را با توجه به نوع آن، چند بخش کوچک‌تر تقسیم کرده و به حل آنها می‌پردازند. سپس از ترکیب پاسخ بخش‌های کوچک‌تر، پاسخ کلی مسئله به‌دست می‌آید. برخی از روش‌های مرتب‌سازی مانند مرتب‌سازی ادغامی (Merge Sort) و مرتب‌سازی سریع (Quick Sort) نیز از این دسته الگوریتم‌ها محسوب می‌شوند.
به‌عنوان مثال مرتب‌سازی ادغامی ابتدا آرایه‌ای از مقادیر ورودی را دو قسمت کرده و به‌صورت بازگشتی، دوباره هر قسمت را دو قسمت می‌کند. این روند آن‌قدر ادامه پیدا می‌کند تا اعداد در دسته‌های کوچک‌تر صعودی یا نزولی مرتب شوند. سپس از ادغام زیر بخش های کوچک، آرایه مرتب‌شده‌ی بخش‌های بزرگ‌تر به دست می‌آید.
الگوریتم حریصانه (Greedy)
الگوریتم‌های حریصانه به دنبال جستجوی بهینه‌ترین پاسخ ممکن هستند اما لزوماً در هر مسئله‌ای، نمی‌توانند بهینه‌ترین پاسخ را پیدا کنند اما یکی از جواب‌های بهینه را به شما معرفی خواهند کرد. البته برخی مسائل هم به‌طورکلی پاسخ بهینه ندارند که به آنها مسائل NP complete می‌گویند. در شیوه حریصانه در هر مرحله عنصری که بر مبنای معیارها بهترین به نظر می‌رسد، بدون توجه به انتخاب‌هایی که قبلاً انجام شده یا در آینده انجام خواهد شد، انتخاب می‌شود.
مسئله خرد کردن سکه‌ها یکی از مثال‌های معروف در به‌کارگیری الگوریتم حریصانه است. این مسئله می‌گوید فرض کنید که شما باید مبلغی مثلاً 36 تومان را با سکه‌های 20 تومانی، 10 تومانی، 5 تومانی و 1 تومانی پرداخت کنید به طوری که کمترین تعداد سکه را بپردازید. کمترین تعدادی که بتوان با آن 36 تومان را پرداخت کرد پاسخی بهینه برای مسئله ما خواهد بود که در اینجا، برداشتن یک سکه از هر 4 مدل است.
الگوریتم بروت فورس (Brute force)
الگوریتم جستجوی جامع یا بروت فورس تمامی راه‌حل‌های احتمالی را بررسی می‌کند تا بتواند بهینه‌ترین پاسخ را پیدا کند. در این الگوریتم بهینه‌ترین پاسخ با ویژگی “ارضا کردن شرط مسئله” سنجیده می‌شود و به همین دلیل بیشتر برای مسائل کوچک کاربرد دارد. این الگوریتم در رمزگشایی نیز کاربرد زیادی دارد و عملکرد آن به‌گونه‌ای است که تمامی کلیدها را چک می‌کند تا به جواب برسد. داده‌کاوی نیز زمینه دیگری برای استفاده از این نوع الگوریتم‌ها است.
کاربرد الگوریتم چیست ؟
در این مقاله به صورت کامل به این پرسش پرداختیم که الگوریتم چیست و به معرفی انواع الگوریتم‌ها پرداختیم ، در این قسمت می‌خواهیم بگوییم الگوریتم چه کاربردی دارد ؟ در زیر به برخی از کاربردهای الگوریتم‌ها اشاره میکنیم:
- ساده سازی و نظم دهی : یکی از مهم‌ترین کاربردهای الگوریتم‌ها ساده سازی و نظم دهی به فرامینی است که ما قرار است به کامپیوتر بدهیم و برنامه نویسی کنیم.
- سرعت در پیاده سازی : الگوریتم‌ها چون از قبل فرایند تولیدشان مشخص است بنابرین سرعت پیاده سازی آنها بسیار بالا است.
- فهم بهتر از کد نویسی: ما الگوریتم‌ها را ایجاد میکنیم تا بهتر بتوانیم کدنویسی را فهم کنیم.
جمع بندی
الگوریتم‌های کاربردی زیادی در ریاضیات و علوم کامپیوتر وجود دارند که ما به‌طور خلاصه به معرفی تعدادی از آنها پرداختیم. تسلط بر الگوریتم ها اهمیت زیادی برای برنامه نویسان و به‌ویژه Back-End کارها دارد زیرا می‌تواند نقطه قوتی برای استخدام در شرکت‌های معتبر باشد. فلوچارت‌ها و الگوریتم‌ها ازجمله پیش‌نیازهای یادگیری برنامه‌نویسی هستند.
منابع :
مطلبی دیگر از این انتشارات
مارک زاکربرگ چگونه به ثروتمندترین برنامه نویس دنیا تبدیل شد؟
مطلبی دیگر از این انتشارات
چرا باید برنامه نویسی پایتون وب یاد بگیریم؟
مطلبی دیگر از این انتشارات
پردرآمدترین زبانهای برنامه نویسی در ایران کدامند؟