مقدمه

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

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

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

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

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

بزن بریم!

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

اهداف فصل

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

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

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

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

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

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

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

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

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

میانه صحیح

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

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

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

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

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

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

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

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

نیمه مرتب

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

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

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

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

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

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

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

استقرای قوی

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

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

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

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

مجموع ارقام

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

آشنایی اولیه

چند مثال ساده

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

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

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

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

فرکتال

ب.م.م

برج هانوی

کد گرِی

𝑛تایی مرتب

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

بخش‌بندی

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

خریدن کتاب

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

پمپ بنزین

کاف‌کیک

انرژی خور

تخته

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

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

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

جاسوسی

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

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

پله‌نوردی

علسوپا

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

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

بسته‌های شکر

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

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

مساوات

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

دومینوار

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

آجرچینی

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

انتخاب

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

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

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

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

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

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

ضرب ماتریس

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

بریم توچال!

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

مسائل پس‌گرد

تعداد جایگشت

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

سودوکو

𝑛 وزیر

یک اسب

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

ادغامات

محاسبهٔ توان

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

قلّه

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

بشمر!

نابه‌جایی

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

pivot کجاست؟

دسته به دسته

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

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

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

مثلث‌ها

خواب پوپک

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

تکامل

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

رژیم سخت

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

سینما، سینما

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

شیر

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

آجر چینی (۲)

بازار موبایل

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

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

پشته

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

هیستوری

صف

الگوی من کیه؟

صف دو‌طرفه

آرایه پویا

لیست پیوندی

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

ویرایشگر متن

درخت هرمی

کافه‌ سالاد

میانه‌روی

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

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

برش کیک

پول یا وجدان؟

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

مجموع جزئی

خواستار

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

مربع

کادوی مشتی

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

کمینه در بازه

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

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

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

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

گراف

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

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

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

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

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

مسافرت

پادشاه

دوست‌یابی

جدول

قطـــر

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

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

زینی

بتایپ

قطار کامیابی

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

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

مرتفع

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

ترور

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

اسم فامیل

صفا

مساحت محصور

عدد روی تخته

دنباله

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

ضمیمه

منابع خوب

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

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

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

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

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

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

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

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

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

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

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

برای شروع شمارش عملیات‌ها ابتدا نیاز است که عملیات‌های پایه را تعریف و تعیین کنیم.
عملیات پایه در واقع کلاس‌های عملیاتی ما هستند که ما در تحلیل الگوریتم‌ها، هر نمونه از این کلاس‌ها را یک واحد عملیاتی محسوب می‌کنیم.

در حالت کلی عملیات‌های پایه ریاضی (جمع، ضرب و...)، عملیات‌های پایه بیتی (شیفت و عملیات‌های منطقی)، مقایسه، انتساب و چاپ جزو عملیات‌های پایه ما محسوب می‌شوند. حال برای شمارش عملیات یک الگوریتم باید تعداد کل عملیات‌های پایه را شمارش کنیم.

----------

# مثال ۱
متغیر‌های ورودی `x` و `y` هستند.

```
1. a = x
2. x = y
3. y = a
```
<details class="blue">
<summary>
عملکرد شبه‌کد 
</summary>
این برنامه مقدار دو متغیر ورودی یعنی `x` و `y` را با یکدیگر جابه‌جا می‌کند.
</details>

<details class="pink">
<summary>
تعداد عملیات
</summary>
این قطعه کد در مجموع شامل سه عملیات انتساب است و در نتیجه تعداد عملیات‌ها ۳ عدد است و به مقدار متغیرهای ورودی وابسته نیست.

</details>

----------

# مثال ۲
متغیر‌های ورودی `a` و `b` و `c` هستند.

```
1. max = a                // یک عملیات انتساب
2. if(a > b)              // یک عملیات شرط
3.    if(a > c) max = a   // یک عملیات شرط + انتساب
4.    else max = c
5. else
6.    if(b > c) max = b
7.    else max = c 
```
<details class="blue">
<summary>
عملکرد شبه‌کد 
</summary>

این برنامه بزرگترین عدد بین ۳ عدد `a`، `b` و  `c` را محاسبه می‌کند.

</details>

<details class="pink">
<summary>
تعداد عملیات
</summary>

در این مثال ابتدا یک عملیات انتساب، سپس بررسی یک شرط و در ادامه بررسی شرط دیگر و یک انتساب داشتیم. پس در مجموع تعداد عملیات ما ۴ است. توجه کنید که برای شمارش عملیات شرطها در نهایت یکی از بدنه‌های `if` یا `else` اجرا خواهد شد نه هیچکدام یا هردو! 

همچنین در این مثال نیز تعداد عملیات‌ها به مقدار متغیر‌های ورودی وابسته نبود.

</details>

----------

# مثال ۳
متغیر ورودی عدد طبیعی `n` است.

```
1. sum = 0                    // 1 
2. for x from 1 to n:         // 1+(n)+(n+1)
3.           sum = sum + x    // 2*n 
```
<details class="blue">
<summary>
عملکرد شبه‌کد 
</summary>
در این برنامه، مجموع اعداد ۱ تا `n` محاسبه خواهد شد.

</details>

<details class="pink">
<summary>
تعداد عملیات
</summary>

در این مثال ابتدا یک عملیات انتساب، در ادامه یک حلقه `for` که در مجموع شامل $2n+2$ عملیات (یک عملیات انتساب اولیه `i` و $n$ عملیات `i = i + 1` و $n+1$ عملیات شرط `x <= n` است.) و  همچنین $2n$ بار (به تعداد دفعات اجرای حلقه) دستور `sum = sum + x` اجرا می‌شود. پس درمجموع $4n+3$ عدد عملیات انجام می‌شود. 

توجه کنید که در این مثال تعداد‌ عملیات‌ها وابسته به مقدار متغیر ورودی است.

</details>

<details class="yellow">
<summary>
توجه
</summary>

در فصل بعد یاد می‌گیریم که ما برای تحلیل الگوریتم‌ها نیاز به شمارش دقیق تعداد‌ عملیات‌ها نداریم‌، بلکه ارائه یک تعداد تقریبی از تعداد عملیات‌ها نیز می‌تونه برای ما مفید باشه و این تقریب تاثیر چندانی در محاسبه‌ی طول زمان اجرای الگوریتم ندارد. 

برای مثال در الگوریتم بالا می‌تونیم تعداد عملیات‌ها را بجای $4n+3$ با تقریب $n$ درنظر بگیریم.

</details>

----------

# مثال ۴
متغیر ورودی عدد طبیعی `n` است.

```
1. for x from 1 to n:
2.     for y from 1 to n:
3.         output (x * y)
```
<details class="blue">
<summary>
عملکرد شبه‌کد 
</summary>

این برنامه، جدول ضرب اعداد ۱ تا $n$ را چاپ می‌کند.

</details>

<details class="pink">
<summary>
تعداد عملیات
</summary>

تعداد عملیات‌های این شبه‌کد را می‌توانیم تعداد اعداد چاپ شده در نظر بگیریم. از آن‌جا که جدول ضرب اعداد ۱ تا $n$ شامل $n^2$  مقدار هست، آن را به عنوان تعداد عملیات‌ها در نظر می‌گیریم.

توجه کنید که در این مثال دیگه عملیات‌های پایه داخلی حلقه‌ها و در نظر نگرفتیم چون نسبت به چاپ، تعداد عملیات کمتری داشتند با تقریب از آن‌ها صرف‌نظر کردیم.

</details>

----------
# مثال ۵
متغیر ورودی عدد طبیعی `n` است.

```
1. t = 0
2. while n > 0:
3.     t = t + 1
4.     n = n // 10
5. output t 
-------------------------
// -> خارج قسمت
```
<details class="blue">
<summary>
عملکرد شبه‌کد 
</summary>

این برنامه، تعداد ارقام عدد $n$ را چاپ می‌کند.

</details>

<details class="pink">
<summary>
تعداد عملیات
</summary>

یک عملیات برای مقداردهی متغیر `t` و یک خط دستور برای چاپ آن استفاده شده. دو خط دستور در حلقه `while` هر کدام به اندازه تعداد ارقام عدد `n` اجرا می‌شوند، از آن‌جایی که تعداد ارقام عدد $n$ برابر 
$1 + \lfloor \log(n) \rfloor$
 است بنابراین تعداد عملیات‌های این شبه کد 
 $4 + 2\lfloor \log(n) \rfloor$
خواهد بود. (ضریب ۲ و جمع با عدد ثابت در شمارش عملیات‌ها مورد توجه قرار می‌گیرند ولی در زمان اجرای الگوریتم تاثیر چندانی نخواهند داشت و به طور تقریبی می‌توان تعداد عملیات‌ها را 
$\lfloor \log(n) \rfloor$
در نظر گرفت)

همچنین توجه کنید که مانند مثال قبل از عملیات‌های داخلی حلقه یعنی بررسی شرط $n > 0$  صرف‌نظر شده است.

</details>

----------

# مثال ۶ 
متغیر‌های ورودی عدد‌های طبیعی `n` و `m` هستند.

```
1. res = 0
2. for r from 1 to n:
2.     for c from 1 to m:
3.         for i from 1 to r:
4.             for j from 1 to c:
5.                 res += (i * j)
```
<details class="blue">
<summary>
عملکرد شبه‌کد 
</summary>
این برنامه مجموع مساحت، زیرجدول‌های یک جدول مستطیل $n \times m$ را محاسبه می‌کند. 
</details>

<details class="pink">
<summary>
تعداد عملیات
</summary>

$$ T = \sum_{r=1}^{n} \sum_{c=1}^{m} \sum_{i=1}^{r} \sum_{j=1}^{c} 1 = \sum_{r=1}^{n} \sum_{c=1}^{m} r \times c = \sum_{r=1}^{n} r 
\times \sum_{c=1}^{m} c$$
$$ T = \sum_{r=1}^{n} r \times \frac{m \times (m + 1)}{2} = \frac{m \times (m+1)}{2} \times \frac{n \times (n+1)}{2}$$

بنابراین $ T = \frac{m \times (m+1)}{2} \times \frac{n \times (n+1)}{2} $.

</details>

----------

# مثال ۷
متغیر ورودی عدد طبیعی `n` است.
```
1. for x from 1 to n:
2.           if (n mod x) = 0:
3.                     output x
---------------------------------
mod -> باقی مانده
```

<details class="blue">
<summary>
عملکرد شبه‌کد 
</summary>
این قطعه کد، مقسوم‌علیه‌های عدد $n$ را چاپ خواهد کرد.
</details>

<details class="pink">
<summary>
تعداد عملیات
</summary>

دستور چاپ در این شبه‌کد به تعداد مقسوم‌علیه‌های عدد $n$ اجرا می‌شود اما در نگاهی دیگر می‌توان تعداد عملیات‌ها را با توجه به تعداد بارهای چک شدن شرط (if) محاسبه کرد که این تعداد برابر $n$ است.

در حقیقت شرط $n$ بار چک می‌شود و دستور چاپ هم به تعداد مقسوم‌علیه‌های $n$. در نتیجه تعداد عملیات‌ها عددی بین $n$ و $2n$ خواهد بود و از آن‌جا که ضریب ۲ در زمان اجرای الگوریتم تاثیر خیلی زیاد ندارد می‌توان این تعداد را به تقریب، $n$ در نظر گرفت.

</details>

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