الگوریتمستان

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

الگوریتم‌های ریشه‌یابی #محاسبات-ریاضی

منظور از ریشه‌ها یک تابع مقادیری برای متغیرهای ورودی آن هستند که به ازای آنها خروجی تابع صفر شود. به عنوان مثال خروجی تابع $f(x)=2x-4$ به ازای $x=2$ صفر یا مقدار $2$ ریشه معادله $2x-4=0$ است. به همین ترتیب در مورد معادلات درجه دوم نیز می‌دانیم چطور می‌توانیم به ریشه یا ریشه‌ها در صورت موجود بودن دست پیدا کنیم. البته لزومی ندارد پاسخ معادله یک عدد صحیح یا گویای متناهی باشد. به عنوان مثل جواب معادله‌های $x^2 - 2 = 0$ و $sin(\frac{x}{2}) = 1$ به ترتیب اعداد گنگ $\sqrt{2}$ و $\pi$ هستند که در عمل امکان ذخیره‌سازی تک تک ارقام اعشاری در کامپیوتر وجود ندارد.

سینوس و کسینوس را قورت بده #محاسبات-ریاضی

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

برج هانوی #مسئله-الگوریتمی

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

معمای هشت وزیر #مسئله-الگوریتمی

معمای هشت وزیر از جمله مسائل کلاسیک مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n وزیر یا معمای چند وزیر مطرح می‌شود.

  

برای افرادی که با بازی شطرنج آشنایی ندارند

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

دنباله اعداد فیبوناچی #الگوریتم

بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن موجودات زنده نظم مشخصی دارند و از دنباله اعدادی تبعیت می‌کنند که امروزه با نام دنباله اعداد فیبوناچی (فیبوناتچی - Fibonacci) شناخته می‌شود. مشهورترین خاصیت این اعداد نسبت دو جمله متوالی آنها به ازای جملات بزرگ دنباله است که به عدد طلایی مشهور است.

الگوریتم‌های تقسیم و حل #الگوریتم

یکی از روش‌های پرکاربرد و محبوب برای طراحی الگوریتم‌ها روش Divide and Conquer است که در زبان فارسی به صورت الگوریتم‌های تقسیم و حل یا تقسیم و غلبه ترجمه شده است.

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

مسئله کاشیکاری #مسئله-الگوریتمی

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

الگوریتم مرتب‌سازی ادغامی #الگوریتم

روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:

1- آرایه را به دو زیرآرایه با اندازه تقریبا یکسان تقسیم کن.

پیچیدگی زمانی اجرای الگوریتم #الگوریتم

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

الگوریتم جستجوی اول سطح (BFS) #الگوریتم

الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search - BFS) از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده می‌کند.

  

درخت Heap #ساختمان-داده

درخت دودویی کامل

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

  

به یک مثال دقت کنید:

  

حلقه‌های تکرار در ++C #برنامه-نویسی

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

هر زبانی عموما شامل چندین نوع حلقه تکرار است که هر کدام به نحوی به برنامه‌نویس در نوشتن کدهای مختصر و با مفهوم کمک می‌کنند. در این فرصت با انواع حلقه‌های تکرار در زبان برنامه‌نویسی ++C آشنا می‌شویم.

الگوریتم جستجوی اول عمق (DFS) #الگوریتم

الگوریتم جستجوی اول عمق (Depth First Search - DFS) یا نام‌های دیگری همچون جستجو در عمق، پیمایش اول عمق، پیمایش عمق اول الگوریتمی مشابه الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف است. این دو الگوریتم خواص و کاربردهای مشترک بسیاری دارند و تفاوت اصلی در این است که در هر تکرار الگوریتم DFS تنها یکی از گره‌های مجاور گره پردازش شده برای مرحله بعد انتخاب می‌شود. به این ترتیب، الگوریتم DFS به جای صف از یک پشته برای مشخص کردن مسیر پیمایش استفاده می‌کند.

الگوریتم مرتب‌سازی سریع #الگوریتم

روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

1- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود.

کتاب Competetive Programming #منبع-آموزشی

ویراست سوم کتاب برنامه‌نویسی رقابتی با نام کامل Competitive Programming 3: The New Lower Bound of Programming Contests با تلاش Steven Halim و Felix Halim از مربیان تیم‌های برنامه‌نویسی ACM-ICPC سنگاپور تالیف و در سال ۲۰۱۳ منتشر شده است که امروزه به عنوان یکی از منابع مناسب برای آمادگی تیم‌های شرکت‌کننده در مسابقات برنامه‌نویسی الگوریتمی بویژه مسابقات برنامه‌نویسی ACM-ICPC توصیه می‌شود.

الگوریتم مرتب‌سازی انتخابی #الگوریتم

روش مرتب‌سازی انتخابی (Selection Sort) یکی از روش‌های اولیه مرتب‌سازی بر اساس مقایسه عناصر است. این الگوریتم طی چند مرحله عناصر لیست را به صورت صعودی یا نزولی مرتب می‌کند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده و به انتهای لیست منتقل می‌کند.