آموزش درس طراحی الگوریتم رشته مهندسی نرم افزار کامپیوتر

درس طراحی الگوریتم یکی از دروس اصلی و حیاتی در دوره کارشناسی رشته نرم‌افزار کامپیوتر است که دانشجویان باید آن را با موفقیت پاس کنند. این درس به طراحی و تحلیل الگوریتم‌های کارآمد برای حل مسائل محاسباتی می‌پردازد و بر بهبود عملکرد و بهینه‌سازی زمان و منابع تمرکز دارد. این جزوه، برگرفته از دانشگاه امام محمد باقر ساری، به بررسی دقیق و تخصصی سرفصل‌های این درس می‌پردازد. تمامی سرفصل‌ها به زبان ساده و با جزئیات کامل شرح داده شده‌اند، شامل توضیحات اضافه‌شده برای الگوریتم‌های مرتب‌سازی ادغامی (Merge Sort)، مونت‌کارلو (Monte Carlo)، فلوید-وارشال (Floyd-Warshall)، و شروود (Sherwood) به همراه سایر مباحث.

طراحی الگوریتم چیست؟

طراحی الگوریتم به فرآیند ایجاد مجموعه‌ای از دستورات مشخص و کارآمد برای حل یک مسئله محاسباتی اشاره دارد. هدف اصلی این درس، آموزش روش‌های طراحی الگوریتم‌هایی است که در کمترین زمان و با کمترین منابع (حافظه، پردازش) به نتیجه مطلوب برسند.
هزینه اجرایی (Execution Cost): تعداد دقیق عملیات موردنیاز برای اجرای الگوریتم برای یک ورودی خاص.
مثال: برای یک الگوریتم که ( n ) عدد را جمع می‌کند (مثلاً ( n=5 ))، دقیقاً ( n-1=4 ) عملیات جمع انجام می‌شود.
مرتبه زمانی (Time Complexity): تخمینی کلی از تعداد عملیات برای همه ورودی‌ها با استفاده از تابع تقریبی، معمولاً با نماد Big-O (( O(n) )) بیان می‌شود.
مثال: در الگوریتم جمع ( n ) عدد، تعداد عملیات به‌صورت خطی با ( n ) افزایش می‌یابد، بنابراین مرتبه زمانی ( O(n) ) است.
مثال ساده: فرض کنید الگوریتمی برای جمع ( n ) عدد داریم:
ورودی: آرایه‌ای با ( n=5 ) عدد: [3, 7, 1, 4, 2]
هزینه اجرایی: 4 عملیات جمع (3+7, 10+1, 11+4, 15+2 = 17)
مرتبه زمانی: ( O(n) )، زیرا تعداد عملیات به‌صورت خطی با ( n ) افزایش می‌یابد.

زمان اجرای کد

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

انتساب و بازگشت (return): هر عملیات انتساب یا بازگشت از تابع، یک واحد زمان در نظر گرفته می‌شود.

تعریف متغیر: تعریف متغیر (بدون مقداردهی) معمولاً زمان صفر در نظر گرفته می‌شود.

حلقه‌ها: یک حلقه با ( n ) تکرار، معمولاً ( n+1 ) عملیات (شامل بررسی شرط حلقه) دارد.

فراخوانی تابع: تعداد دفعات فراخوانی تابع در زمان اجرا محاسبه می‌شود.

مثال:

int sum(int arr[], int n) { int total = 0; // 1 عملیات (انتساب) for (int i = 0; i < n; i++) { // n+1 عملیات (حلقه) total += arr[i]; // n عملیات (جمع و انتساب) } return total; // 1 عملیات (بازگشت) }

کل عملیات: ( 1 + (n+1) + n + 1 = 2n + 3 )

مرتبه زمانی: ( O(n) )

روش تقسیم بر غلبه (Divide and Conquer)

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

تقسیم (Divide): مسئله اصلی به زیرمسئله‌های کوچک‌تر و مشابه تقسیم می‌شود.

حل (Conquer): زیرمسئله‌ها به‌صورت بازگشتی حل می‌شوند تا به مسائل ابتدایی (پایه) برسند که حل آن‌ها ساده است.

ترکیب (Combine): راه‌حل‌های زیرمسئله‌ها ترکیب می‌شوند تا راه‌حل مسئله اصلی به دست آید.

مثال: مرتب‌سازی ادغامی (Merge Sort):

توضیحات در بخش بعدی ارائه شده است.

مرتب‌سازی ادغامی (Merge Sort)

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

روش کار:

تقسیم: آرایه به دو نیمه تقسیم می‌شود تا به آرایه‌های تک‌عنصری (مرتب‌شده) برسیم.

حل: هر نیمه به‌صورت بازگشتی مرتب می‌شود.

ترکیب: دو نیمه مرتب‌شده با مقایسه عناصر و قرار دادن آن‌ها در جایگاه درست ادغام می‌شوند.

مرتبه زمانی: ( O(n \log n) )

( \log n ) مرحله تقسیم (عمق درخت بازگشتی).

هر مرحله ادغام ( O(n) ) عملیات نیاز دارد.

مزایا:

پایدار (ترتیب عناصر یکسان حفظ می‌شود).

مناسب برای داده‌های بزرگ و لیست‌های پیوندی.

معایب: نیاز به فضای اضافی ( O(n) ) برای ادغام.

مثال:

آرایه: [38, 27, 43, 3, 9, 82, 10]

تقسیم: [38, 27, 43, 3] و [9, 82, 10]

ادامه تقسیم: [38, 27], [43, 3], [9, 82], [10]

ادغام: [27, 38], [3, 43], [9, 82], [10] → [3, 27, 38, 43], [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

کد:

void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1, n2 = r - m; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } }

مرتب‌سازی انتخابی (Selection Sort)

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

روش کار:

آرایه به دو بخش مرتب و نامرتب تقسیم می‌شود.

در هر مرحله، کوچک‌ترین عنصر از بخش نامرتب پیدا شده و با اولین عنصر بخش نامرتب جابه‌جا می‌شود.

بخش مرتب بزرگ‌تر و بخش نامرتب کوچک‌تر می‌شود.

مرتبه زمانی: ( O(n^2) )، زیرا برای هر عنصر، کل آرایه نامرتب بررسی می‌شود.

مثال:

آرایه اولیه: [64, 34, 25, 12]

مرحله 1: کوچک‌ترین = 12 → جابه‌جایی → [12, 34, 25, 64]

مرحله 2: کوچک‌ترین = 25 → جابه‌جایی → [12, 25, 34, 64]

مرحله 3: کوچک‌ترین = 34 → [12, 25, 34, 64]

کد:

void selectionSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } }

مرتب‌سازی سریع (Quick Sort)

مرتب‌سازی سریع یک الگوریتم کارآمد مبتنی بر تقسیم بر غلبه است که از یک عنصر به‌عنوان پیوت (معمولاً اولین یا آخرین عنصر) استفاده می‌کند.

روش کار:

یک پیوت انتخاب می‌شود (مثلاً اولین عنصر).

آرایه به دو بخش تقسیم می‌شود: عناصر کوچک‌تر از پیوت در سمت چپ و بزرگ‌تر یا مساوی در سمت راست.

پیوت در جایگاه نهایی خود قرار می‌گیرد.

این فرآیند به‌صورت بازگشتی برای بخش‌های چپ و راست تکرار می‌شود.

مرتبه زمانی:

میانگین: ( O(n \log n) )

بدترین حالت: ( O(n^2) ) (وقتی پیوت بد انتخاب شود، مثلاً آرایه مرتب‌شده).

عمق درخت: عمق درخت بازگشتی در حالت میانگین ( \log n ) است.

مثال:

آرایه: [10, 7, 8, 9, 1, 5]

پیوت: 10

تقسیم: [7, 8, 9, 1, 5] | 10 | []

ادامه به‌صورت بازگشتی برای [7, 8, 9, 1, 5].

کد:

void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int partition(int arr[], int low, int high) { int pivot = arr[low]; int i = low + 1, j = high; while (i <= j) { while (i <= high && arr[i] <= pivot) i++; while (arr[j] > pivot) j--; if (i < j) swap(arr[i], arr[j]); } swap(arr[low], arr[j]); return j; }

ضرب ماتریس‌های بزرگ

ضرب ماتریس‌های بزرگ نیازمند بهینه‌سازی است، به‌ویژه وقتی ابعاد ماتریس‌ها بزرگ باشند.

شرایط:

ماتریس‌ها باید مربعی باشند (تعداد سطر و ستون برابر).

ابعاد باید توانی از 2 باشند (مثلاً ( 2^k )) برای استفاده از الگوریتم‌های تقسیم بر غلبه مانند الگوریتم استراسن.

روش استاندارد:

برای دو ماتریس ( A ) و ( B ) با ابعاد ( n \times n )، ضرب به‌صورت زیر محاسبه می‌شود:

( C[i][j] = \sum_{k=1}^n A[i][k] \cdot B[k][j] )

مرتبه زمانی: ( O(n^3) ).

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

ماتریس‌ها به چهار زیرماتریس تقسیم می‌شوند.

با 7 ضرب بازگشتی (به‌جای 8) و ترکیب نتایج، مرتبه زمانی به ( O(n^{2.81}) ) کاهش می‌یابد.

مثال: برای ماتریس‌های ( 2 \times 2 ):

// ماتریس A = [[1, 2], [3, 4]] و B = [[5, 6], [7, 8]] // نتیجه: C = [[19, 22], [43, 50]]

الگوریتم‌های حریص (Greedy Algorithms)

الگوریتم‌های حریص در هر مرحله بهترین انتخاب ممکن را انجام می‌دهند بدون در نظر گرفتن تأثیر آن بر مراحل بعدی، با این فرض که این انتخاب‌ها به راه‌حل بهینه کلی منجر می‌شوند.

روش کار:

در هر مرحله، مؤثرترین عنصر (بر اساس معیار مشخص) انتخاب می‌شود.

عنصر به فضای پاسخ اضافه می‌شود.

این فرآیند تا تکمیل راه‌حل ادامه می‌یابد.

مثال: الگوریتم کوله‌پشتی کسری (Fractional Knapsack):

اقلام بر اساس نسبت ارزش به وزن مرتب می‌شوند.

اقلام با بیشترین نسبت ارزش/وزن انتخاب می‌شوند.

مرتبه زمانی: معمولاً ( O(n \log n) ) به دلیل مرتب‌سازی اولیه.

مثال:

struct Item { int value, weight; }; void fractionalKnapsack(Item arr[], int n, int W) { sort(arr, arr + n, [](Item a, Item b) { return (double)a.value/a.weight > (double)b.value/b.weight; }); double totalValue = 0; int curWeight = 0; for (int i = 0; curWeight < W && i < n; i++) { if (curWeight + arr[i].weight <= W) { curWeight += arr[i].weight; totalValue += arr[i].value; } else { int remain = W - curWeight; totalValue += arr[i].value * ((double)remain / arr[i].weight); curWeight = W; } } printf("Total value: %.2f\n", totalValue); }

گراف‌های جهت‌دار، هادی، و درخت

گراف ساختاری از گره‌ها (Vertices) و یال‌ها (Edges) است که برای مدل‌سازی روابط استفاده می‌شود.

تعاریف:

گراف جهت‌دار (Directed Graph): یال‌ها جهت دارند (مثلاً از A به B).

گراف هادی (Undirected Graph): یال‌ها بدون جهت هستند.

گراف وزن‌دار: یال‌ها دارای وزن (هزینه یا فاصله) هستند.

گراف متصل: بین هر دو گره حداقل یک مسیر وجود دارد.

مسیر (Path): دنباله‌ای از گره‌ها که با یال‌ها به هم متصل‌اند.

دور (Cycle): مسیری که به گره اولیه بازمی‌گردد.

درخت: گرافی متصل و بدون دور.

گراف متصل وزن‌دار: گرافی که تمام گره‌ها به هم متصل‌اند و یال‌ها وزن دارند.

درخت پوشا (Spanning Tree): زیرگرافی از گراف متصل که شامل تمام گره‌ها و ( n-1 ) یال است و هیچ دوری ندارد.

بین هر دو گره فقط یک مسیر وجود دارد.

یک گراف ممکن است چندین درخت پوشا داشته باشد.

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

1. الگوریتم کراسکال (Kruskal’s Algorithm)

روش کار:

یال‌ها را بر اساس وزن به‌صورت صعودی مرتب کنید.

یال‌ها را به ترتیب اضافه کنید، به شرطی که دور ایجاد نشود (با استفاده از ساختار داده Union-Find).

مرتبه زمانی: ( O(E \log E) )، به دلیل مرتب‌سازی یال‌ها.

مثال:

گراف با یال‌ها: (A-B, 1), (B-C, 2), (A-C, 3), (C-D, 4)

مرتب‌سازی: (A-B, 1), (B-C, 2), (C-D, 4)

اضافه کردن یال‌ها: A-B, B-C, C-D (چون A-C دور ایجاد می‌کند، نادیده گرفته می‌شود).

کد:

struct Edge { int u, v, weight; }; int find(int parent[], int i) { /* Union-Find */ } void kruskal(Edge edges[], int V, int E) { sort(edges, edges + E, [](Edge a, Edge b) { return a.weight < b.weight; }); int parent[V]; for (int i = 0; i < V; i++) parent[i] = i; for (int i = 0; i < E; i++) { if (find(parent, edges[i].u) != find(parent, edges[i].v)) { printf("%d-%d (%d)\n", edges[i].u, edges[i].v, edges[i].weight); union(parent, edges[i].u, edges[i].v); } } }

الگوریتم پرایم (Prim’s Algorithm)

روش کار:

از یک گره دلخواه شروع کنید.

کم‌وزن‌ترین یال متصل به گره‌های انتخاب‌شده را اضافه کنید.

گره جدید را به مجموعه اضافه کنید و تکرار کنید.

مرتبه زمانی: ( O(E \log V) ) با استفاده از هیپ.

مثال:

شروع از گره A: یال A-B (1) → یال B-C (2) → یال C-D (4).

کد:

void prim(int graph[V][V], int V) { int key[V], parent[V]; bool mstSet[V]; for (int i = 0; i < V; i++) key[i] = INT_MAX, mstSet[i] = false; key[0] = 0; parent[0] = -1; for (int count = 0; count < V-1; count++) { int u = minKey(key, mstSet, V); mstSet[u] = true; for (int v = 0; v < V; v++) if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) parent[v] = u, key[v] = graph[u][v]; } }

زمان‌بندی سخنران‌ها با الگوریتم حریص

مسئله زمان‌بندی سخنران‌ها: در یک همایش با زمان شروع و پایان مشخص، هدف انتخاب بیشترین تعداد سخنرانی بدون تداخل است.

روش کار:

سخنرانی‌ها را بر اساس زمان پایان (( p_i )) به‌صورت صعودی مرتب کنید.

اولین سخنرانی (با کمترین ( p_i )) را انتخاب کنید.

سخنرانی بعدی را انتخاب کنید که زمان شروعش (( s_i )) بعد از زمان پایان سخنرانی قبلی باشد.

این فرآیند را ادامه دهید.

مرتبه زمانی: ( O(n \log n) ) به دلیل مرتب‌سازی.

مثال:

سخنرانی‌ها: [(1, 3), (2, 4), (3, 5), (4, 6)]

مرتب‌شده بر اساس زمان پایان: [(1, 3), (2, 4), (3, 5), (4, 6)]

انتخاب: (1, 3), (3, 5) → حداکثر 2 سخنرانی.

کد:

struct Interval { int start, end; }; void activitySelection(Interval arr[], int n) { sort(arr, arr + n, [](Interval a, Interval b) { return a.end < b.end; }); int last = 0; printf("Selected: (%d, %d)\n", arr[0].start, arr[0].end); for (int i = 1; i < n; i++) { if (arr[i].start >= arr[last].end) { printf("Selected: (%d, %d)\n", arr[i].start, arr[i].end); last = i; } } }

مسئله کوله‌پشتی کسری (Fractional Knapsack)

مسئله کوله‌پشتی کسری: هدف انتخاب اقلامی است که نسبت ارزش به وزن (( value/weight )) آن‌ها حداکثر باشد، با محدودیت ظرفیت کوله‌پشتی.

روش کار:

اقلام را بر اساس نسبت ( value/weight ) به‌صورت نزولی مرتب کنید.

اقلام را به ترتیب اضافه کنید تا ظرفیت پر شود.

اگر ظرفیت باقی‌مانده کمتر از وزن قلم باشد، کسری از آن قلم انتخاب می‌شود.

مرتبه زمانی: ( O(n \log n) ).

مثال:

اقلام: [(60, 10), (100, 20), (120, 30)]، ظرفیت = 50

نسبت‌ها: [6, 5, 4]

انتخاب: کل قلم 1 (10 واحد)، کل قلم 2 (20 واحد)، 20/30 از قلم 3 → ارزش کل = 60 + 100 + 80 = 240.

کد:

struct Item { int value, weight; }; void fractionalKnapsack(Item arr[], int n, int W) { sort(arr, arr + n, [](Item a, Item b) { return (double)a.value/a.weight > (double)b.value/b.weight; }); double totalValue = 0; int curWeight = 0; for (int i = 0; curWeight < W && i < n; i++) { if (curWeight + arr[i].weight <= W) { curWeight += arr[i].weight; totalValue += arr[i].value; } else { int remain = W - curWeight; totalValue += arr[i].value * ((double)remain / arr[i].weight); curWeight = W; } } printf("Total value: %.2f\n", totalValue); }

زمان‌بندی کارها (مشابه SJF)

زمان‌بندی کارها: مشابه الگوریتم Shortest Job First (SJF) در سیستم‌عامل، هدف کمینه کردن زمان انتظار با اجرای کارهایی با کمترین زمان اجرا است.

روش کار:

کارها را بر اساس زمان اجرا به‌صورت صعودی مرتب کنید.

کارها را به ترتیب اجرا کنید.

مرتبه زمانی: ( O(n \log n) ).

مثال:

کارها: [(J1, 3), (J2, 1), (J3, 4)]

مرتب‌شده: [(J2, 1), (J1, 3), (J3, 4)]

ترتیب اجرا: J2 → J1 → J3.

زمان‌بندی با ضرب‌الاجل

مسئله زمان‌بندی با ضرب‌الاجل: هدف حداکثر کردن سود با انتخاب کارهایی است که در ضرب‌الاجل خود اجرا شوند.

روش کار:

کارها را بر اساس سود به‌صورت نزولی مرتب کنید.

هر کار را در دیرترین زمان ممکن (قبل از ضرب‌الاجل) که هنوز رزرو نشده، قرار دهید.

مرتبه زمانی: ( O(n \log n) ).

مثال:

کارها: [(J1, profit=40, deadline=2), (J2, profit=30, deadline=1), (J3, profit=50, deadline=2)]

مرتب‌شده بر اساس سود: [(J3, 50, 2), (J1, 40, 2), (J2, 30, 1)]

زمان‌بندی: J3 در زمان 2، J2 در زمان 1 → سود کل = 50 + 30 = 80.

کد:

struct Job { int id, profit, deadline; }; void jobScheduling(Job arr[], int n) { sort(arr, arr + n, [](Job a, Job b) { return a.profit > b.profit; }); int maxDeadline = 0; for (int i = 0; i < n; i++) maxDeadline = max(maxDeadline, arr[i].deadline); int slot[maxDeadline] = {0}; for (int i = 0; i < n; i++) { for (int j = min(maxDeadline, arr[i].deadline) - 1; j >= 0; j--) { if (slot[j] == 0) { slot[j] = arr[i].id; printf("Job %d at slot %d\n", arr[i].id, j + 1); break; } } } }

ضرب ماتریس به روش حریص

مسئله ضرب زنجیره‌ای ماتریس‌ها: هدف یافتن بهترین ترتیب پرانتزگذاری برای ضرب ماتریس‌ها است تا تعداد عملیات کمینه شود.

روش کار:

با استفاده از برنامه‌نویسی پویا (Dynamic Programming)، تمام ترکیب‌های ممکن بررسی می‌شوند.

الگوریتم حریص مستقیماً قابل‌استفاده نیست، اما می‌توان به‌صورت تقریبی از ایده‌های حریص برای انتخاب ترتیب استفاده کرد.

مرتبه زمانی: ( O(n^3) ) با برنامه‌نویسی پویا.

مثال:

ماتریس‌ها: ( A_1 (10 \times 30), A_2 (30 \times 5), A_3 (5 \times 60) )

پرانتزگذاری بهینه: ( (A_1 \times A_2) \times A_3 )

تعداد عملیات: ( (10 \times 30 \times 5) + (10 \times 5 \times 60) = 1500 + 3000 = 4500 ).

کد:

int matrixChainOrder(int p[], int n) { int dp[n][n]; for (int i = 1; i < n; i++) dp[i][i] = 0; for (int L = 2; L < n; L++) { for (int i = 1; i < n - L + 1; i++) { int j = i + L - 1; dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]); } } } return dp[1][n-1]; }

الگوریتم کدگذاری هافمن (Huffman Coding)

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

روش کار:

فرکانس هر کاراکتر را محاسبه کنید.

دو گره با کمترین فرکانس را انتخاب کرده و ادغام کنید (جمع فرکانس‌ها به‌عنوان گره والد).

این فرآیند را تا تشکیل درخت دودویی کامل ادامه دهید.

برای هر کاراکتر، مسیر از ریشه به برگ (0 برای چپ، 1 برای راست) کد هافمن است.

مرتبه زمانی: ( O(n \log n) ) با استفاده از هیپ.

مثال:

کاراکترها و فرکانس‌ها: [(a, 5), (b, 2), (c, 1), (d, 1)]

ادغام: (c, 1) + (d, 1) = (cd, 2) → (cd, 2) + (b, 2) = (cdb, 4) → (cdb, 4) + (a, 5) = (cdba, 9)

کدها: a=0, b=10, c=110, d=111

کد:

struct Node { char data; int freq; Node *left, *right; }; void huffmanCoding(char data[], int freq[], int n) { priority_queue<Node*, vector<Node*>, compare> minHeap; for (int i = 0; i < n; i++) { minHeap.push(new Node(data[i], freq[i])); } while (minHeap.size() > 1) { Node *left = minHeap.top(); minHeap.pop(); Node *right = minHeap.top(); minHeap.pop(); Node *newNode = new Node('$', left->freq + right->freq); newNode->left = left; newNode->right = right; minHeap.push(newNode); } printCodes(minHeap.top(), ""); }

الگوریتم مونت‌کارلو (Monte Carlo)

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

کاربردها:

محاسبه تقریبی (مثلاً محاسبه مساحت یا انتگرال).

مسائل بهینه‌سازی.

شبیه‌سازی سیستم‌های پیچیده.

روش کار:

یک نمونه تصادفی از ورودی‌ها یا حالات ممکن انتخاب می‌شود.

محاسبات بر اساس این نمونه‌ها انجام می‌شود.

با افزایش تعداد نمونه‌ها، دقت جواب افزایش می‌یابد.

مرتبه زمانی: وابسته به تعداد نمونه‌ها و پیچیدگی مسئله.

مثال: تخمین عدد پی (( \pi )):

فرض کنید یک مربع با ضلع 2 و یک دایره با شعاع 1 داخل آن داریم.

نقاط تصادفی در مربع تولید می‌کنیم و بررسی می‌کنیم که چند نقطه داخل دایره قرار می‌گیرند.

نسبت نقاط داخل دایره به کل نقاط تقریباً ( \pi/4 ) است.

کد:

#include <stdlib.h> #include <time.h> double estimatePi(int n) { srand(time(0)); int insideCircle = 0; for (int i = 0; i < n; i++) { double x = (double)rand() / RAND_MAX * 2 - 1; // [-1, 1] double y = (double)rand() / RAND_MAX * 2 - 1; // [-1, 1] if (x * x + y * y <= 1) insideCircle++; } return 4.0 * insideCircle / n; }

الگوریتم فلوید-وارشال (Floyd-Warshall)

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

روش کار:

یک ماتریس فاصله ( n \times n ) ایجاد کنید که ( d[i][j] ) نشان‌دهنده وزن یال بین گره‌های ( i ) و ( j ) باشد.

برای هر گره ( k ) به‌عنوان گره واسطه، بررسی کنید که آیا مسیر از ( i ) به ( j ) از طریق ( k ) کوتاه‌تر است یا خیر.

ماتریس فاصله را به‌روزرسانی کنید: ( d[i][j] = \min(d[i][j], d[i][k] + d[k][j]) ).

مرتبه زمانی: ( O(n^3) )، که ( n ) تعداد گره‌هاست.

مزایا: ساده و مناسب برای گراف‌های متراکم.

معایب: کندتر از الگوریتم‌هایی مثل دایکسترا برای گراف‌های پراکنده.

مثال:

گراف با 4 گره و یال‌ها: (1-2, 4), (2-3, 3), (3-4, 1), (4-1, 2)

ماتریس فاصله نهایی کوتاه‌ترین مسیرها را نشان می‌دهد.

کد:

#define INF 99999 void floydWarshall(int graph[V][V], int V) { int dist[V][V]; for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = graph[i][j]; for (int k = 0; k < V; k++) for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; // چاپ ماتریس فاصله for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) printf("%d ", dist[i][j] == INF ? INF : dist[i][j]); printf("\n"); } }

الگوریتم شروود (Sherwood)

الگوریتم شروود یک تکنیک برای بهبود الگوریتم‌های تصادفی است، به‌ویژه در الگوریتم‌هایی مثل مرتب‌سازی سریع (Quick Sort)، که عملکردشان در بدترین حالت ضعیف است. این روش با تصادفی کردن انتخاب‌ها (مثلاً انتخاب پیوت) احتمال وقوع بدترین حالت را کاهش می‌دهد.

روش کار:

به‌جای انتخاب یک پیوت ثابت (مثلاً اولین یا آخرین عنصر)، پیوت به‌صورت تصادفی انتخاب می‌شود.

این کار باعث می‌شود مرتبه زمانی میانگین (( O(n \log n) )) در اکثر موارد حفظ شود.

کاربرد: در مرتب‌سازی سریع برای جلوگیری از بدترین حالت (( O(n^2) ))، مثلاً وقتی آرایه از قبل مرتب است.

مثال: مرتب‌سازی سریع با شروود:

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

کد:

int randomPartition(int arr[], int low, int high) { int pivotIndex = low + rand() % (high - low + 1); swap(arr[pivotIndex], arr[low]); int pivot = arr[low]; int i = low + 1, j = high; while (i <= j) { while (i <= high && arr[i] <= pivot) i++; while (arr[j] > pivot) j--; if (i < j) swap(arr[i], arr[j]); } swap(arr[low], arr[j]); return j; } void quickSortSherwood(int arr[], int low, int high) { if (low < high) { int pi = randomPartition(arr, low, high); quickSortSherwood(arr, low, pi - 1); quickSortSherwood(arr, pi + 1, high); } }

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