مقدمه

به‌ نام خدا، سلام!

مسیر یادگیری در کوئرا کالج

آنچه خواهید دید!

توضیحاتی در مورد شبه‌کدها

طرح درس، گواهی و  امتیازات

بزن بریم!

۱. ورود به دنیای الگوریتم‌ها

اهداف فصل

خصوصیات الگوریتم

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

مراحل حل مسئله

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

زمان اجرای برنامه

شمارش عملیات‌ها

جست‌وجو در دنباله ۱

جست‌وجو در دنباله ۲

تبدیل به حسابی ۱

میانه صحیح

تبدیل به حسابی ۲

۲. تحلیل زمانی الگوریتم‌ها

عدم اهمیت ضریب‌ها

تعریفِ ابتداییِ اردر

چند مثال از اردر

مقایسه اردر‌ها

بزرگ‌ترین زیربازه ۱

بزرگ‌ترین زیربازه ۲

نیمه مرتب

شمارش مثلث‌ها ۱

شمارش مثلث‌ها ۲

شمارش مثلث‌ها ۳

مرتب‌سازی و تحلیل زمانی

مرتب‌سازی حبابی

۳. الگوریتم‌های استقرایی

استقرای ریاضی

استقرای قوی

مرتب‌سازی انتخابی

مرتب‌سازی درجی

بزرگ‌ترین زیربازه ۳

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

مجموع ارقام

۴. الگوریتم‌های بازگشتی

آشنایی اولیه

چند مثال ساده

پشته فراخوانی

روش‌های تحلیل توابع بازگشتی

مثال‌های تحلیل توابع بازگشتی

دنباله بازگشتی

فرکتال

ب.م.م

برج هانوی

کد گرِی

𝑛تایی مرتب

تناظر زیر مجموعه‌ها با اعداد دودویی

بخش‌بندی

۵. الگوریتم‌های حریصانه

خریدن کتاب

زندگی کارمندی

پمپ بنزین

کاف‌کیک

انرژی خور

تخته

بیشترین تعداد بازه

اشتباهات رایج

آبمیوه فروشی حریصانه

جاسوسی

تمرین‌های دوره‌ای ۱

استارت-آپ باکلاس

پله‌نوردی

علسوپا

پالیندرومینیا

ضرب متناظر دو دنباله

بسته‌های شکر

تعمیر پشت‌بام

شرکت پالایش و پخش نخود در برره

مساوات

۶. برنامه‌نویسی پویا

دومینوار

بزرگترین زیر‌بازه

آجرچینی

بزرگترین زیر جدول

انتخاب

بیشینه مسیر جدول

چالش مسیر‌یابی

مسئله‌ی کوله پشتی

یا همه یا هیچ یا یکی

بهینه‌سازی حافظه کوله پشتی

بزرگ‌ترین زیردنباله مشترک

ضرب ماتریس

بزرگ‌ترین زیردنباله اکیدا صعودی

بریم توچال!

۷. الگوریتم‌های پس‌گرد

مسائل پس‌گرد

تعداد جایگشت

دنباله‌ پس‌گردنی

سودوکو

𝑛 وزیر

یک اسب

۸. روش تقسیم‌ و حل

ادغامات

محاسبهٔ توان

تابع توان‌دار

قلّه

جستجوی دودویی

بشمر!

نابه‌جایی

مرتب‌سازی سریع

pivot کجاست؟

دسته به دسته

تمرین‌های دوره‌ای ۲

مرد مالیاتچی و جاعل

تعداد ۱۱ بخش پذیرها (۲)

مثلث‌ها

خواب پوپک

باقر حال نداره ولی پول داره

تکامل

انتقام از TA‌ سخت‌گیر

رژیم سخت

دنباله تورج‌پسند

سینما، سینما

بازرگانی سوکرات و پسران

شیر

متوازی‌الاضلاع ممنوع!

آجر چینی (۲)

بازار موبایل

منظره‌ای به‌ یاد ماندنی

۹. ساختمان‌داده‌ها

پشته

پرانتز‌گذاری معتبر

هیستوری

صف

الگوی من کیه؟

صف دو‌طرفه

آرایه پویا

لیست پیوندی

پیاده‌سازی ساختمان‌داده‌های قبلی با لیست پیوندی

ویرایشگر متن

درخت هرمی

کافه‌ سالاد

میانه‌روی

درخت دودویی جستجو و ساختار مجموعه‌ای

برنامه‌ریزی فرودگاه

برش کیک

پول یا وجدان؟

۱۰. پیش‌پردازش و بهینه‌سازی

مجموع جزئی

خواستار

مجموع جزئی در ماتریس

مربع

کادوی مشتی

درخواست مینیمم عدد در بازه

کمینه در بازه

مرتب‌سازی درجی رشته‌ها

مجموع جزئی در آرایه متغَیّر

بیشینه در آرایه متغیّر

۱۱. الگوریتم‌های گراف

گراف

دی‌اِف‌اِسِ پیش‌گو

بی‌اِف‌اِسِ مسیر‌یاب

پیدا کردن دور در گراف‌ها

گراف‌های دوبخشی

پیدا کردن کمر گراف

مسافرت

پادشاه

دوست‌یابی

جدول

قطـــر

تمرین‌های دوره‌ای ۳

وسیله کمک آموزشی

زینی

بتایپ

قطار کامیابی

هیچ‌وقت مغرور نشو!

دنباله متوازن

مرتفع

گراف قرمز و آبی

ترور

میان‌ترم هندسه

اسم فامیل

صفا

مساحت محصور

عدد روی تخته

دنباله

کمینه بیشینه اختلاف!

ضمیمه

منابع خوب

نکاتی درباره باقی‌مانده و سرریز کردن (Overflow)

تحلیل الگوریتم‌ها

پیاده‌سازی ساختمان‌‌داده‌ها بخش اول

پیاده‌سازی ساختمان‌‌داده‌ها بخش دوم

مرتب‌سازی در زبان ++C

استفاده از pair در ++C

ساختمان‌های داده در ++C

کتابخانه‌ها و توابع پرکاربرد ++C

روش‌های دیگر خواندن ورودی در ++C

پرکابردهای پایتون بخش اول

پرکابردهای پایتون بخش دوم

خوشحالیم که بتوانیم در راستای طراحی خلاقانه الگوریتم‌ها شما را یاری کنیم! این بخش را حتماً بخوانید تا با قسمت‌های مختلف آموزشی دوره آشنا شوید و تیک «خواندم» آن‌ را بزنید تا بقیه دوره برایتان باز شود!

در این دوره با کاربرد و اهمیت طراحی الگوریتم آشنا می‌شویم و می‌فهمیم تفاوت **الگوریتم خوب** و **الگوریتم بد** واقعاً چیست.

# اهداف دوره
در این دوره انتظار می‌رود شما با مفهوم تحلیل زمانی الگوریتم‌ها، مفاهیم پایه‌ای در طراحی الگوریتم مثل «**بازگشتی**»، «**حریصانه**»، «**برنامه‌نویسی پویا**»، «**گراف‌ها**» و... و همچنین «**ساختمان‌داده‌ها**» آشنا شوید و توانایی حل مسائل الگوریتمی را بدست بیاورید.

# نکاتی در مورد فصل‌ها
این دوره بجز مقدمه شامل ۱۱ فصل آموزشی و ۳ فصل تمرین دوره‌ای است. هر فصل شامل چند «بخش» است به طوری که هر بخش می‌تواند یک «**درسنامه**» یا یک «**تمرین**» با سامانه داوری باشد.  برای ‌آشنایی با فرمت استاندارد مسائل و بخش‌های مختلف در کوئرا به این [پیوند](https://quera.ir/course/assignments/2693/problems) مراجعه کنید.

# جعبه‌های دوره
بخش بزرگی از این دوره به صورت **پنهان** در آمده‌ است تا به شما فرصت تفکر روی مسائل را بدهیم همچنین بخش‌های الگوریتمی از برنامه‌نویسی جدا باشد. این بخش‌ها به صورت زیر با رنگ‌بندی‌های زیر است.

<details class="orange">

<summary>

%align_center_start%
# راهنمایی‌ها
لطفاً راهنمایی‌ها را یکی یکی مطالعه کرده و بعد از مطالعه‌ی هر کدام چند دقیقه فکر کنید!

</summary>

<details class="orange">

<summary>
راهنمایی ۱
</summary>
توضیحات راهنمایی اول
</details>

<details class="orange">

<summary>
راهنمایی ۲
</summary>
توضیحات راهنمایی دوم
</details>

<details class="orange">

<summary>
راهنمایی ۳
</summary>
توضیحات راهنمایی سوم
</details>

ممکن است یک سوال چندین راهنمایی داشته باشد.

</details>

<details class="blue"> 

<summary>

%align_center_start%
# راه‌حل کامل
لطفاً قبل از دیدن راه‌حل مسئله روی سوال بین ۱۵ تا ۳۰ دقیقه فکر کنید!

</summary>

----------
در اینجا راه‌حل سوال به طور کامل توضیح داده می‌شود.

<details class="blue"> 
<summary>
اگر برای فهمیدن راه‌حل سوال به **شبه‌کد** آن نیاز دارید، بر روی این قسمت کلیک کنید!
</summary>

بخش‌ها به صورت **الگوریتمی و مستقل از زبان** هستند و در آن به جای کد از **شِبهِ‌کُد** (PseudoCode) استفاده شده‌است.

شبه‌کد در جعبه‌هایی به صورت زیر ظاهر می‌شوند و معمولاً به شکل زیر هستند.
```
> FunctionName(functionInputs)
functionInput and variable descriptions
----------------------------------------
function goal
----------------------------------------
// Algorithm:
1. operation1
2. operation2
.
.
.
return value
```

برای مثال شبه‌کد زیر جمع اعداد زوج از ۱ تا $n$ را برمی‌گرداند.
```
> sumOfEvenNumbers(n)
n : the upper bound of the numbers we want
------------------------------------------
return the sum of even numbers in [1, n]
------------------------------------------
1. returnValue := 0
2. for i from 1 to n:
3. 	if i is even:
4. 		returnValue := returnValue + i
5. return returnValue
```

توضیحات جامعی درباره شبه‌کد در فصل «ضمیمه» موجود است.

</details>

</details>

<details class="blue">
<summary>
کد *++C*
</summary>
در این بخش‌‌ها می‌توانید توضیحاتی راجع به پیاده‌سازی سؤال مورد نظر یا درسنامه‌ی مورد نظر ببینید. بخش های مربوط به پیاده‌سازی *++C* در این‌جا آمده‌است. برای مثال کد شبه‌کد بالا به صورت زیر خواهد بود:

```cpp
// In the name of God

#include <iostream>

using namespace std;

long long sumOfEvenNumbers(int n) {
	long long returnValue = 0;
	for (int i = 0; i <= n; i++)
		if (i % 2 == 0) {
			returnValue += i;
		}
	return returnValue;
}

int main () {
	int n;
	cin >> n;
	cout << sumOfEvenNumbers(n) << endl;
	return 0;
}
```
</details>

<details class="green">

<summary>
کد *پایتون*
</summary>

در این بخش‌‌ها می‌توانید توضیحاتی راجع به پیاده‌سازی سؤال مورد نظر یا درسنامه‌ی مورد نظر ببینید. بخش های مربوط به پیاده‌سازی *پایتون* در این‌جا آمده ‌است. برای مثال کد شبه‌کد بالا به صورت زیر خواهد بود:

```python
# In the name of God

def sum_of_even_numbers(n):
	return sum([x for x in range(1, n+1) if x % 2 == 0])

n = int(input())
print(sum_of_even_numbers(n))
```

</details>

**نکته مهم‌**: گاهاً درسنامه‌ها و نکات برنامه‌نویسی و الگوریتمی در قالب **راه‌حل یا راهنمایی** سؤال آمده‌ است بنابراین **حتماً** راه‌حل سؤالات را بخوانید تا نکته‌هایی را دریابید. همچنین این بخش‌ها به صورت پنهان‌شده هستند تا بتوانید قبل از خواندن راه‌حل سؤال به خوبی روی سؤال فکر کنید.

درسنامه‌های زبان به زبان *++C* و *پایتون* هستند دلیل اینکه این زبان انتخاب شده‌ است قابلیت‌های زیاد آن است و همه‌ی الگوریتم‌ها و ساختمان‌های داده را می‌توان با آن‌ها پیاده‌سازی کرد.

راه‌حل هر کدام از سؤالات با پرداخت امتیاز به زبان‌های *پایتون* و *++C* موجود است.

بخش تمرینات دوره‌ای برای تمرین بیشتر بخش‌های قبلی و افزایش امتیاز برای درج در گواهی موجود است. این تمرینات ممکن است کمی سخت‌تر از سؤالات بخش‌های دیگر باشند ولی حل آن‌ها حتماً به افزایش قابلیت‌هایتان کمک خواهند کرد.

# پیش‌نیاز‌ها

آشنایی با حداقل یک زبان برنامه‌نویسی برای گذراندن دوره نیاز است. همچنین آشنایی مقدماتی با مفاهیم ریاضی همانند **استقرا**، **گراف‌ها** و مفاهیم **ترکیبیاتی** به شما بسیار کمک می‌کند و کار‌تان را راحت‌تر می‌کند. البته تلاش کرده‌ایم به همه تعاریف به صورت مقدماتی بپردازیم. 

می‌توانید با تمام زبان‌هایی که کوئرا پشتیبانی می‌کند این دوره را بگذرانید. در تمامی بخش‌های کدمحور به‌جای نوشتن کد به زبانی خاص، *شبه‌کد* نوشته شده‌ است. درسنامه‌های زبان اضافه‌تر در ضمیمه برای کاربرد‌ها و کتاب‌خانه‌های الگوریتمی زبان‌ها به دو زبان *++C* و *پایتون* موجود است و اکثر الگوریتم‌ها در کنار شبه‌کد به این دو زبان هم پیاده‌سازی شده‌اند.

# ضمیمه‌ی دوره

در انتهای دوره فصلی تحت عنوان **ضمیمه**‌ موجود است که حاوی اطلاعات خوبی مانند منابع مفید و همچنین نکات برنامه‌نویسی است. اکثر درسنامه‌های زبان‌های برنامه‌نویسی و پیاده‌سازی‌های مهم که در آن‌جا آورده ‌شده است. توصیه می‌کنیم هر جا از نظر برنامه‌نویسی به مشکلی برخورد کردید به این بخش مراجعه کنید.


# پیشنهاد‌ زبان برنامه‌نویسی

برنامه‌هایی که به زبان *++C* نوشته می‌شوند معمولاً در اجرا سریع‌تر هستند اما نوشتن برنامه‌ها به زبان *پایتون* ساده‌تر است. می‌توانید دوره‌ را به هر زبانی که کوئرا پشتیبانی می‌کند بگذرانید اما پیشنهاد ما یکی از این دو زبان است. (یا اگر دوست داشتید هر دو!)

اگر‌چه این دوره تحت عنوان دوره‌ی پیشرفته‌ی الگوریتم آمده‌ است و تمرینات بسیاری دارد اما دنیای طراحی الگوریتم بزرگ‌تر و گسترده‌تر از آن است که در یک دوره بگنجد و این دوره مقدمه‌ای برای آشنایی با مسیر طول و دراز الگوریتم‌ها و بهینه‌سازی است. امیدواریم در این دوره تا حد خوبی بتوانیم شما را با الگوریتم‌ها آشنا کنیم و پیشنهاد می‌کنیم با تمرین بیشتر (از بانک سوالات کوئرا یا منابع دیگر) در راستای رشد و حرفه‌ای‌تر شدن خود در این مسیر قدم بردارید.

الگوریتم پیشرفته و ساختمان‌داده‌ها