الگوریتم ها نقش مهمی در برنامه نویسی و حوزه‌های کامپیوتری دارند، همانطور که می‌دانید به خردکردن یک مسئله بزرگ به مسئله‌های کوچک‌تر و سبک‌تر و سپس حل‌کردن آنها الگوریتم گفته می‌شود. هر الگوریتم از تعدادی ورودی تشکیل شده است و سپس یکسری از دستورالعمل‌ها بر روی ورودی‌ها انجام می‌شود و در نهایت یک یا چند خروجی حاصل می‌گردد. تاکنون الگوریتم های مختلفی در زمینه‌های گوناگون بوجود آمده است و هرکدام عملکرد ویژه خود را دارند؛ به عنوان مثال تعدادی از الگوریتم ها برای جستجوکردن ایجاد شده‌اند؛ یکسری از آنها برای مسائل بهینه‌سازی ساخته شده‌اند که به آنها الگوریتم های بهینه سازی هم گفته می‌شود و یا در زمینه‌های دیگر مثل رمزنگاری و یادگیری ماشین و...
تعداد الگوریتم هایی که تاکنون ساخته شده و مورد استفاده قرار گرفته است بسیار زیاد است، اما به‌عنوان یک برنامه نویس یا یک فعال در حوزه کامپیوتر، نیاز است تا برخی از معروف‌ترین‌ها و پرکاربردترین الگوریتم ها را بشناسید.
معروف‌ترین الگوریتم های برنامه نویسی
ابتدا دسته‌بندی الگوریتم ها را مشخص می‌کنیم و سپس برای هر مجموعه، معروف‌ترین و پرکاربردترین الگوریتم ها را معرفی می‌کنیم.
الگوریتم های جستجو (Searching Algorithms):
الگوریتم های جستجو برای جستجوکردن و پیداکردن یک اِلمان خاص در یک ساختمان داده خاص استفاده می‌شود. تاکنون تکنیک‌های مختلفی برای بهینه‌کردن فرایند جستجو به وجود آمده است تا بتوان به‌وسیله آنها با تعداد مقایسه کمتری، آیتم موردنظر را پیدا کنیم. مهم‌ترین الگوریتم های جستجو عبارت‌اند از:
- جستجوی خطی (Linear Search): الگوریتم های جستجوی خطی به‌صورت تکراری (Iterative) یک لیست یا آرایه را پیمایش می‌کنند تا به عنصر موردنظر برسند و یا دیتاست مورد جستجو به اتمام برسد.
- جستجوی دودویی (Binary Search): به‌صورت کارآمد عنصر موردنظر را در یک لیست مرتب جستجو میکند. نحوه عملکرد الگوریتم جستجوی باینری به این صورت است که هر بار محدوده مورد جستجو را نصف میکند و این عمل را تا پیداشدن عنصر یا اتمام لیست انجام می‌دهد.
الگوریتم های مرتب‌سازی (Sorting Algorithms):
الگوریتم های مرتب سازی، المان‌ها یا عنصرهای داخل یک ساختمان داده را به ترتیب خاصی مرتب می‌کنند؛ به‌عنوان‌مثال ترتیب قرارگیری عنصرها می‌تواند صعودی یا نزولی باشد. مرتب‌کردن یک لیست و یا هر ساختمان داده دیگری از اهمیت بسیار بالایی برخوردار است؛ چرا که دسترسی و تغییر عناصر سریع‌تر و کاراتر خواهد بود. باتوجه به مهم‌بودن این دسته از الگوریتم ها، تاکنون روش‌های بسیار متعددی برای مرتب‌کردن به وجود آمده است که اکثر آنها معروف هستند و به وفور در طول برنامه نویسی استفاده می‌شوند. از الگوریتم های مهم مرتب سازی می‌توان به موارد زیر اشاره کرد:
- مرتب سازی حبابی (Bubble Sort): به صورت تکراری دو عنصر مجاور یکدیگر را با یکدیگر مقایسه میکند و اگر ترتیب قرارگرفتن آنها اشتباه بود، جایگاهشان را با یکدیگر عوض میکند (Swap)
- مرتب سازی درجی (Insertion Sort): این الگوریتم تک‌تک عناصر را از یک آرایه نامرتب گرفته و آنها را در مکان صحیح قرار می‌دهد.
- مرتب‌سازی انتخابی (Selection Sort): کوچک‌ترین (بزرگ‌ترین) عنصر یک ساختمان داده را پیدا کرده و آن را با اولین (آخرین) عنصر ساختمان داده Swap یا عوض میکند.
- مرتب سازی ادغامی (Merge Sort): ابتدا لیست نامرتب را به قسمت‌های کوچک‌تر تقسیم میکند و سپس آن قسمت‌ها را مرتب میکند، بعد از مرتب‌کردن قسمت‌های کوچک، آنها را با یکدیگر ادغام کرده تا لیست کامل حاصل شود.
- مرتب سازی سریع (Quick Sort): در این الگوریتم ابتدا یک عنصر به عنوان محور یا Pivot انتخاب شده و سپس آرایه به قسمت‌های کوچک‌تر از Pivot و قسمت‌های بزرگ‌تر از Pivot تقسیم می‌شود؛ عناصر باتوجه به ترتیبشان به صورت بازگشتی یا Recursive باتوجه‌به Pivot مرتبط می‌شوند.
الگوریتم های بهینه‌سازی (Optimization Algorithms):
به طور خلاصه هدف از الگوریتم های بهینه‌سازی، پیداکردن بهترین جواب ممکن در بین جواب‌های متعدد یک مسئله است؛ بنابراین الگوریتم های بهینه‌سازی می‌خواهند یک مقدار خاصی را ماکزیمم و یا مینیمم کنند. از مهم‌ترین الگوریتم های بهینه‌سازی می‌توان به موارد زیر اشاره کرد:
- الگوریتم های حریصانه (Greedy Algorithms): در هر مرحله از اجرای این الگوریتم، بهترین جواب یا نقطه بهینه یا Optimal محلی انتخاب می‌شود به امید اینکه به نقطه بهینه سراسری یا Global برسیم. در الگوریتم های هافمن (Huffman) و کراسکال (Kruskal) از این شیوه از الگوریتم استفاده می‌شود.
- الگوریتم ذوب شبیه‌سازی‌شده (Simulated Annealing): ذوب شبیه‌سازی‌شده یک تکنیک بهینه‌سازی احتمالی (Probabilistic) است که با الهام از ذوب کردن در متالورژی برای فرار از بهینه محلی استفاده می‌شود.
- الگوریتم ژنتیک (Genetic Algorithm): الگوریتم ژنتیک که الهام گرفته شده از ژنتیک طبیعی در دنیای واقعی است، به انتخاب طبیعی ژن‌ها، ادغام آنها با یکدیگر و جهش‌های آنها می‌پردازد تا جواب بهینه برای مسائل جستجو را پیدا کند.
- بهینه‌سازی ازدحام ذرات (Particle Swarm Optimization): الگوریتم PSO در واقع رفتار موجودات را در یک گروه برای یافتن راه‌حل‌های بهینه شبیه‌سازی میکند.
- الگوریتم کلونی مورچه‌ها (Ant Colony Optimization): از جمله الگوریتم‌های معروف بهینه‌سازی، می‌توان به الگوریتم کلونی مورچه ها اشاره کرد. در این الگوریتم با الهام از رفتار مورچه‌ها سعی می‌کنیم تا جواب بهینه را پیدا کنیم.
الگوریتم های یادگیری ماشین (Machine Learning Algorithms):
الگوریتم های یادگیری ماشین، کامپیوتر را قادر می‌سازند که در داده‌های موجود یک الگوی خاصی را یاد بگیرد تا بتواند تصمیم‌گیری و یا پیش‌بینی کند. یادگیری ماشین در واقع زیر مجموعه‌ای از حوزه‌های هوش مصنوعی و تحلیل داده‌ها محسوب می‌شود. از الگوریتم های مهم یادگیری ماشین می‌توان به موارد زیر اشاره کرد:
- یادگیری تحت نظارت (Supervised Learning): یادگیری تحت نظارت یا یادگیری با نظارت یکی از الگوریتم های یادگیری ماشین است که در آن، الگوریتم از داده‌های آموزشی برچسب‌گذاری شده برای پیش‌بینی یا تصمیم‌گیری شروع به یادگیری میکند.
- یادگیری بدون نظارت (Unsupervised Learning): در این روش، الگوریتم ها از داده‌های بدون برچسب فرایند یادگیری را انجام می‌دهند؛ در واقع داده‌ها هیچ گروه‌بندی و الگوی مشخصی ندارند و کار دسته‌بندی و پیداکردن ساختارها و الگوهای مخفی بر عهده خود الگوریتم یادگیری است.
- الگوریتم های تقویتی (Reinforcement Learning): الگوریتم ها، حرکت‌های بهینه‌ای را باتوجه‌به بازخورد و فیدبکی که از محیط می‌گیرند اعمال می‌کنند.
الگوریتم های اجماع در بلاکچین (Blockchain Consensus Algorithm):
باتوجه به محبوبیت بسیار زیاد تکنولوژی بلاکچین و غیرمتمرکز بودن آن، الگوریتم های زیادی در 2 دهه اخیر به وجود آمده است که به‌وسیله این الگوریتم ها گره‌ها یا نودها (Node) می‌توانند با یکدیگر به توافق یا اجماع برسند. از مهم‌ترین الگوریتم های اجماع بلاک چینی می‌توان به موارد زیر اشاره کرد:
- الگوریتم اثبات کار (Proof of Work): در الگوریتم PoW، نودها یا گره‌ها تحت عنوان ماینرها (Miners) به حل یک پازل پیچیده برای تصدیق‌کردن تراکنش‌ها و اضافه‌کردن بلوک‌ها به درون زنجیره بلوک‌ها می‌پردازند. اولین ارز دیجیتال یعنی بیت کوین از این الگوریتم برای اجماع استفاده کرده است؛ به همین دلیل الگوریتم اثبات کار از معروف‌ترین الگوریتم های اجماع در بلاکچین به‌حساب می‌آید.
- الگوریتم اثبات سهام (Proof of Stake): در این الگوریتم که توسط رمزارز اتریوم مورداستفاده قرار گرفته است، نودها تحت عنوان تصدیق‌کننده‌ها یا Validatorها به‌اضافه کردن بلوک و تصدیق تراکنش‌ها باتوجه به میزان رمز ارزی که به عنوان وثیقه درون شبکه نگهداری می‌کنند می‌پردازند.
- الگوریتم اثبات صلاحیت (Proof of Authority): در این الگوریتم، تصدیق‌کننده‌ها بر اساس شناسه و شهرتشان احراز هویت می‌شوند.
- الگوریتم اثبات زمان سپری شده (Proof of Elapsed Time): در این الگوریتم نودها یا گره‌ها برای انتخاب‌شدن به‌عنوان سازندگان بلوک درون زنجیره اصلی به رقابت می‌پردازند.
الگوریتم های گراف (Graph Algorithms):
از دسته الگوریتم های مهم دیگر حوزه برنامه نویسی می‌توان به الگوریتم های گراف اشاره کرد. الگوریتم های گراف به تحلیل ارتباط بین نودهایی از گراف که با یکدیگر در ارتباط هستند می‌پردازد؛ به‌عنوان‌مثال، این الگوریتم ها کمک می‌کنند تا بتوانیم کوتاه‌ترین مسیر را پیدا کنیم و موارد بسیار دیگر. از مهم‌ترین الگوریتم های گراف می‌توان به موارد زیر اشاره کرد:
- جستجوی سطح اول (Breadth-First Search): رویکرد الگوریتم BFS به این صورت است که در ابتدا تمامی رئوس یک سطح (ارتفاع) را جستجو میکند و سپس وارد سطوح بعدی می‌شود. الگوریتم های سطح اول بیشتر برای یافتن کوتاه‌ترین مسیر و تحلیل‌های شبکه کاربرد دارد.
- جستجوی عمق اول (Depth-First Search): رویکرد الگوریتم DFS به این صورت است که تمامی رئوس مربوط به یک شاخه یا branch را به‌صورت backtracking یا عقب رو پیمایش میکند تا به راس آخر یا برگ‌ها برسد و همین کار را برای رئوس بعدی انجام می‌دهد. از این الگوریتم برای مرتب‌سازی توپولوژی کال، پیداکردن اجزای به هم متصل و... استفاده می‌شود.
- الگوریتم دایجسترا (Dijkstra Algorithm): برای یافتن کوتاه‌ترین مسیر بین گره‌ها درون یک گراف وزن‌دار از این الگوریتم استفاده می‌شود. یکی از الگوریتم های مهم در مسیریابی شبکه، الگوریتم دایجسترا یا دیکسترا است.
- الگوریتم بلمن فورد (Bellman-Ford Algorithm): همانند الگوریتم دایجسترا هدف الگوریتم بلمن فورد نیز یافتن کوتاه ترین مسیر در گراف های وزن‌دار است با این تفاوت که وزن‌ها می‌توانند مقدار منفی (Negative) هم داشته باشند.
- الگوریتم پریم (Prim Algorithm): هدف الگوریتم پریم پیداکردن مینیمم درخت پوشا در یک گراف بدون جهت است که بیشتر برای طراحی شبکه و تکنیک‌های کلاسترینگ یا خوشه‌بندی مورداستفاده قرار می‌گیرد.
- الگوریتم کراسکال (Kruskal Algorithm): برای ساختن حداقل درخت پوشا داخل یک گراف بدون جهت از الگوریتم کراسکال استفاده می‌شود. این الگوریتم نیز برای طراحی شبکه و کلاسترینگ داده‌ها استفاده می‌شود.
الگوریتم های جستجو در رشته (String Searching Algorithms):
الگوریتم های جستجو در رشته، با توالی‌ای از کاراکترها یا سمبل‌ها که به‌عنوان رشته یا String شناخته می‌شوند سروکار دارند. به‌طورکلی از این الگوریتم ها برای جستجوی یک الگو درون یک رشته، تصدیق‌کردن یک داده و یا تغییر یا دست‌کاری یک متن استفاده می‌شوند. از مهم‌ترین الگوریتم های جستجو در رشته می‌توان به موارد زیر اشاره کرد:
- عبارات منظم (Regular Expressions): عبارات منظم برای تعیین الگوهای متن که در کارهای جستجو و دست‌کاری متون است استفاده می‌شود.
- جستجوی رشته ساده (Naive String Search): یک رویکرد بسیار ساده‌ای است که برای یافتن وقوع یک الگو در متن کاربرد دارد.
- الگوریتم رابین کارپ (Rabin-Karp Algorithm): این الگوریتم از تکنیک درهم‌سازی یا هشینگ (hashing) برای جستجوی بهینه یک الگو درون یک متن استفاده میکند.
جمع بندی
دنیای الگوریتم، دنیای جذاب و البته چالش‌برانگیز دنیای کامپیوتر است. به هر اندازه که مفهوم یک الگوریتم را درک کنید و از آن به‌صورت کاربردی استفاده کنید، به همان اندازه دانش شما در حل مسائل بالاتر رفته و برنامه نویسی برای شما راحت‌تر می‌شود. تعداد الگوریتم های ساخته شده بسیار زیاد است، از بعضی از آنها تنها در حد نوشتن یک مقاله استفاده شده‌اند؛ اما برخی دیگر کاربردهای بسیار گسترده‌ای دارند؛ از استفاده در نرم‌افزارها گرفته تا ایجاد خطوط هواپیمایی و تولید جنگ‌افزارها و... . در این مقاله به معروف ترین و متداول ترین الگوریتم هایی که در دنیای برنامه نویسی استفاده می‌شوند پرداختیم و هرکدام را به‌صورت مختصر توضیح دادیم.
ازمهم‌ترین دسته‌بندی‌های الگوریتم ها کدام‌اند؟
1- الگوریتم های جستجو (Searching Algorithms) 2-الگوریتم های مرتب سازی (Sorting Algorithms) 3-الگوریتم های بهینه سازی (Optimization Algorithms) 4-الگوریتم های یادگیری ماشین (Machine Learning Algorithms) 5-الگوریتم های اجماع در بلاکچین (Blockchain Consensus Algorithm) 6-الگوریتم های گراف (Graph Algorithms) 7-الگوریتم های جستجو در رشته (String Searching Algorithms)
آیا به‌عنوان برنامه نویس حتماً باید با الگوریتم های معروف آشنا باشیم؟
بستگی به حیطه کاری‌تان دارد. سؤال در مورد الگوریتم و حل مسئله از مهم‌ترین پرسش‌هایی است که در مصاحبه استخدامی پرسیده می‌شود؛ همچنین برای توانایی حل مسائل نیاز به دانستن الگوریتم های متفاوت دارید؛ بنابراین پیشنهاد می‌شود تا در مورد الگوریتم های معروف برنامه نویسی اطلاعات لازم و کافی را داشته باشید.
مطالب مرتبط
همه مقالات
