شرح مادة عال 311 (CSC 311) تصميم وتحليل الخوارزميات - جامعة الملك سعود

مادة عال 311 (CSC 311)، تصميم وتحليل الخوارزميات (Design and Analysis of Algorithms)، تُعتبر من اصعب المواد في خطة قسم علوم الحاسب بجامعة الملك سعود. مو مبالغة لما نقول لك ان كثير من الطلاب يعتبرونها اصعب مادة مرّت عليهم طوال المرحلة الجامعية. بس الخبر الحلو: لو دخلتها وانت فاهم ليش هي صعبة ومستعد لها، الوضع يختلف تماما.

المادة تبني مباشرة على عال 212 تراكيب البيانات. هنا الموضوع يتطور: ما تكتفي بقياس التعقيد، تتعلم كيف تصمم خوارزميات فعالة من الصفر وتُثبت صحتها رياضيا.

نعرف ان المادة ممكن تحسسك بالاحباط لما تواجه البراهين الرياضية او مسالة DP ما تعرف من وين تبدا. هذا طبيعي وكل طالب مرّ فيه. المهم انك ما توقف.

ليش عال 311 من اهم المواد في مسارك؟

هذي المادة ليست مجرد متطلب تعدّيه. هي جوهر علوم الحاسب:

• المقابلات الوظيفية: شركات مثل Google و Meta و Amazon تبني 80% من اسئلتها على مواضيع عال 311. البرمجة الديناميكية والجشعة والرسوم البيانية هي اللي تحدد تنقبل او لا
• حل المشكلات المعقدة: عال 311 تعلمك كيف تصمم حل من الصفر لما ما يكون في حل جاهز
• فهم حدود الحوسبة: NP-Completeness يعلمك متى المشكلة ما لها حل فعال، وهذا يوفر عليك ساعات ضائعة
• اساس AI وتعلم الالة: كثير من خوارزميات الذكاء الاصطناعي تعتمد على مفاهيم عال 311
• التفكير الرياضي: المادة تقوّي قدرتك على التحليل والاثبات

نظرة عامة على محتوى عال 311

الاسابيع	الموضوع	المفاهيم الرئيسية
1-2	التحليل التقاربي (Asymptotic Analysis)	Big-O, Big-Omega, Big-Theta, علاقات التكرار
3-4	القسمة والحل (Divide and Conquer)	Merge Sort, Quick Sort, Binary Search, Strassen
5-6	الخوارزميات الجشعة (Greedy)	Activity Selection, Huffman, Fractional Knapsack
7-9	البرمجة الديناميكية (Dynamic Programming)	0/1 Knapsack, LCS, Matrix Chain, Rod Cutting
10-12	خوارزميات الرسوم البيانية (Graph Algorithms)	BFS, DFS, Dijkstra, Bellman-Ford, Prim, Kruskal
13-14	NP-Completeness	P vs NP, تحويلات، مسائل NP-Complete
15	مراجعة شاملة	تمارين متكاملة

1. التحليل التقاربي (Asymptotic Analysis)

في عال 212 تعرّفت على Big-O بشكل مبسّط. هنا الموضوع يروح لمستوى ثاني: تتعلم ثلاث تعريفات رياضية دقيقة وتستخدمها في البراهين.

Big-O (الحد الاعلى)

Big-O يحدد اسوا حالة لنمو الدالة. بالتعريف الرسمي:

f(n) = O(g(n)) اذا وُجدت ثوابت c > 0 و n₀ بحيث: f(n) ≤ c·g(n) لكل n ≥ n₀

يعني: من نقطة معينة وطالع، f(n) ما تتجاوز مضاعف ثابت من g(n).

مثال: نثبت ان 3n² + 5n + 2 = O(n²)

نختار c = 10 و n₀ = 1. لكل n ≥ 1: 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n² ✓

Big-Omega (الحد الادنى)

f(n) = Ω(g(n)) اذا وُجدت ثوابت c > 0 و n₀ بحيث: f(n) ≥ c·g(n) لكل n ≥ n₀

يعني: الدالة على الاقل بسرعة g(n). هذا يفيدك لما تبي تثبت ان خوارزمية مستحيل تكون اسرع من حد معين.

Big-Theta (الحد المحكم)

f(n) = Θ(g(n)) اذا كانت f(n) = O(g(n)) و f(n) = Ω(g(n)) في نفس الوقت.

يعني: الدالة تنمو بالضبط بنفس معدل g(n). هذا اقوى تصنيف تقدر تعطيه.

الرمز	المعنى	مثال
O(n²)	ما تتجاوز n² (اسوا حالة)	Bubble Sort
Ω(n log n)	على الاقل n log n (افضل حالة)	خوارزميات الترتيب بالمقارنة
Θ(n log n)	بالضبط n log n	Merge Sort (كل الحالات)

علاقات التكرار (Recurrence Relations)

في عال 311 تتعامل مع خوارزميات تكرارية (recursive) وتحتاج تحسب تعقيدها. هنا تستخدم علاقات التكرار.

Master Theorem هي اهم اداة عندك. لو عندك علاقة بالشكل: T(n) = aT(n/b) + f(n)

حيث a هو عدد المشكلات الفرعية، n/b حجم كل مشكلة فرعية، و f(n) تكلفة التقسيم والدمج:

• الحالة 1: لو f(n) = O(n^(log_b(a) - ε)) فان T(n) = Θ(n^log_b(a))
• الحالة 2: لو f(n) = Θ(n^log_b(a)) فان T(n) = Θ(n^log_b(a) · log n)
• الحالة 3: لو f(n) = Ω(n^(log_b(a) + ε)) فان T(n) = Θ(f(n))

مثال: Merge Sort علاقته T(n) = 2T(n/2) + Θ(n). هنا a=2, b=2, log_b(a) = 1, f(n) = Θ(n¹) → الحالة 2 → T(n) = Θ(n log n) ✓

2. تحليل خوارزميات الترتيب

الترتيب مو موضوع جديد عليك من عال 212، لكن هنا ندرسه من زاوية التصميم والتحليل الرياضي.

Merge Sort — تحليل مفصل

Merge Sort مثال كلاسيكي لاسلوب القسمة والحل:

MERGE-SORT(A, p, r)
    if p < r
        q = (p + r) / 2           // حدد النص
        MERGE-SORT(A, p, q)       // رتّب النص الاول
        MERGE-SORT(A, q+1, r)     // رتّب النص الثاني
        MERGE(A, p, q, r)         // ادمج النصين المرتبين

• التعقيد الزمني: Θ(n log n) في كل الحالات (افضل، متوسط، اسوا)
• التعقيد المكاني: O(n) بسبب المصفوفة المساعدة في الدمج
• مستقرة: نعم

Quick Sort — لماذا اسرع عمليا؟

QUICKSORT(A, p, r)
    if p < r
        q = PARTITION(A, p, r)    // اختر pivot وقسّم
        QUICKSORT(A, p, q-1)      // رتّب اللي قبل pivot
        QUICKSORT(A, q+1, r)      // رتّب اللي بعد pivot

PARTITION(A, p, r)
    pivot = A[r]                  // العنصر الاخير كمحور
    i = p - 1
    for j = p to r-1
        if A[j] <= pivot
            i = i + 1
            swap A[i], A[j]       // حرّك الاصغر لليسار
    swap A[i+1], A[r]
    return i + 1

• التعقيد المتوسط: Θ(n log n)
• التعقيد الاسوا: Θ(n²) — يحصل لو المصفوفة مرتبة والـ pivot دائما الاصغر او الاكبر
• التعقيد المكاني: O(log n) للـ recursion stack
• اسرع عمليا من Merge Sort بسبب Cache Locality وثابت اصغر

الحد الادنى للترتيب بالمقارنة

نتيجة نظرية مهمة: اي خوارزمية ترتيب بالمقارنة لازم تكون Ω(n log n) في اسوا الحالات (اثبات بشجرة القرار: على الاقل n! ورقة، ارتفاع log(n!) = Θ(n log n)). هذا يعني Merge Sort مثالية تقاربيا.

3. القسمة والحل (Divide and Conquer)

اسلوب القسمة والحل يقوم على ثلاث خطوات: قسّم المشكلة لمشكلات اصغر، احل كل مشكلة فرعية، ادمج الحلول.

Binary Search — المثال الابسط

BINARY-SEARCH(A, low, high, key)
    if low > high
        return -1                  // العنصر مو موجود
    mid = (low + high) / 2
    if A[mid] == key
        return mid                 // لقيناه
    else if A[mid] > key
        return BINARY-SEARCH(A, low, mid-1, key)
    else
        return BINARY-SEARCH(A, mid+1, high, key)

علاقة التكرار: T(n) = T(n/2) + Θ(1). بتطبيق Master Theorem (الحالة 2 مع f(n) = Θ(1) و a=1, b=2): T(n) = Θ(log n)

Strassen’s Matrix Multiplication

ضرب مصفوفتين بالطريقة العادية: T(n) = 8T(n/2) + Θ(n²) → Θ(n³). Strassen قلل الضربات من 8 الى 7: T(n) = 7T(n/2) + Θ(n²) → Θ(n^2.81). ما تحتاج تحفظ التفاصيل، بس افهم ليش تقليل ضربة واحدة يحسّن التعقيد وتعرف تطبق Master Theorem عليها.

4. الخوارزميات الجشعة (Greedy Algorithms)

الفكرة بسيطة ظاهريا: في كل خطوة، اختر افضل خيار محلي وانت تامل انه يوصلك لافضل حل كلي. بس الصعوبة تكمن في: متى الاسلوب الجشع يعطي حل مثالي ومتى لا؟

Activity Selection Problem

عندك مجموعة انشطة، كل نشاط له وقت بداية ووقت نهاية. تبي تختار اكبر عدد من الانشطة اللي ما تتعارض:

ACTIVITY-SELECTION(s, f, n)
    // رتّب الانشطة حسب وقت النهاية
    sort activities by finish time f
    selected = {activity 1}        // اختر اول نشاط ينتهي
    last = 1
    for i = 2 to n
        if s[i] >= f[last]         // لو بدايته بعد نهاية الاخير
            selected = selected + {activity i}
            last = i
    return selected

ليش ينفع الحل الجشع هنا؟ لان اختيار النشاط اللي ينتهي اولا يعطيك اكبر مساحة متبقية لانشطة اخرى. هذا قابل للاثبات رياضيا بـ Greedy Choice Property و Optimal Substructure.

Huffman Coding

Huffman يبني شجرة ثنائية لضغط البيانات. الحروف الاكثر تكرارا تاخذ كود اقصر:

HUFFMAN(C)
    n = |C|
    Q = min-priority-queue(C)      // رتّب حسب التكرار
    for i = 1 to n-1
        z = new node
        z.left = x = EXTRACT-MIN(Q)   // اسحب الاقل
        z.right = y = EXTRACT-MIN(Q)  // اسحب الثاني
        z.freq = x.freq + y.freq
        INSERT(Q, z)               // ارجع العقدة المدمجة
    return EXTRACT-MIN(Q)          // جذر الشجرة

التعقيد: O(n log n) بسبب عمليات الـ Priority Queue.

Fractional Knapsack

شنطة سعتها W وعناصر كل واحد له وزن وقيمة. هنا تقدر تاخذ جزء من العنصر، فالحل الجشع بسيط: رتّب حسب (القيمة/الوزن) تنازليا وخذ قدر ما تقدر.

هذا الحل مثالي لان القسمة ممكنة. لكن لو ما تقدر تقسّم (0/1 Knapsack)، الحل الجشع لا يعمل ولازم تستخدم البرمجة الديناميكية.

5. البرمجة الديناميكية (Dynamic Programming)

هنا ندخل في الموضوع اللي يخلّي اغلب الطلاب يحسون بالضياع. البرمجة الديناميكية ليست خوارزمية واحدة، هي طريقة تفكير لحل مشكلات تتكرر فيها نفس المشكلات الفرعية.

الفرق عن Divide and Conquer: في D&C المشكلات الفرعية مستقلة، لكن في DP تتداخل وتتكرر. بدل ما تحلها عشر مرات، تحلها مرة وتحفظ النتيجة.

0/1 Knapsack Problem

عندك شنطة سعتها W كيلو و n عنصر. كل عنصر له وزن w[i] وقيمة v[i]. تبي تاخذ عناصر تعطيك اكبر قيمة بدون ما تتجاوز السعة. ما تقدر تقسّم العنصر (تاخذه كامل او تتركه).

تعريف الحالة: dp[i][w] = اكبر قيمة ممكنة باستخدام اول i عنصر وسعة w

الانتقال:

// لو وزن العنصر i اكبر من السعة المتبقية
if w[i] > w:
    dp[i][w] = dp[i-1][w]           // ما ناخذه
else:
    dp[i][w] = max(
        dp[i-1][w],                  // ما ناخذه
        dp[i-1][w - w[i]] + v[i]     // ناخذه
    )

التعقيد: O(nW) — وهو pseudo-polynomial (ما يعتبر polynomial حقيقي لان W ممكن يكون كبير جدا).

Longest Common Subsequence (LCS)

عندك نصّين X و Y وتبي تلاقي اطول تتابع مشترك بينهم (مو بالضرورة متتالي).

تعريف الحالة: dp[i][j] = طول LCS لـ X[1..i] و Y[1..j]

الانتقال:

if X[i] == Y[j]:
    dp[i][j] = dp[i-1][j-1] + 1     // الحرف مشترك، ضمّه
else:
    dp[i][j] = max(
        dp[i-1][j],                   // تجاهل حرف من X
        dp[i][j-1]                    // تجاهل حرف من Y
    )

التعقيد: O(mn) حيث m و n اطوال النصين.

Matrix Chain Multiplication

عندك سلسلة مصفوفات A₁ × A₂ × … × Aₙ وتبي تلاقي الترتيب الامثل للاقواس اللي يقلل عدد عمليات الضرب.

مثال: لو عندك A(10×30) × B(30×5) × C(5×60):

• (AB)C = 10×30×5 + 10×5×60 = 1500 + 3000 = 4500 عملية
• A(BC) = 30×5×60 + 10×30×60 = 9000 + 18000 = 27000 عملية

ترتيب الاقواس فرق 6 مرات! تخيل لو عندك 100 مصفوفة.

تعريف الحالة: dp[i][j] = اقل عدد ضربات لحساب Aᵢ × … × Aⱼ

الانتقال:

dp[i][j] = min over k from i to j-1:
    dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
    // جرّب كل نقطة تقسيم ممكنة

التعقيد: O(n³) — ثلاث حلقات متداخلة.

Rod Cutting Problem

عندك قطعة حديد طولها n وجدول اسعار لكل طول. تبي تقطّعها بطريقة تعطيك اكبر ربح.

تعريف الحالة: dp[i] = اكبر ربح ممكن من قطعة طولها i

الانتقال:

dp[i] = max over j from 1 to i:
    price[j] + dp[i - j]
    // جرّب كل قطعة ممكنة

التعقيد: O(n²)

6. خوارزميات الرسوم البيانية (Graph Algorithms)

في عال 212 تعلمت BFS (تعقيد O(V+E) لاقصر مسار بدون اوزان) و DFS (تعقيد O(V+E) للترتيب الطوبولوجي وكشف الدورات). في عال 311 نروح اعمق: اقصر المسارات بأوزان و الشجرة الممتدة الصغرى.

Dijkstra — اقصر المسارات من مصدر واحد

Dijkstra يلاقي اقصر مسار من رأس واحد لكل الرؤوس الثانية. شرط: الاوزان لازم تكون غير سالبة.

DIJKSTRA(G, w, s)
    for each vertex v in G
        dist[v] = infinity          // المسافة الابتدائية
        prev[v] = null
    dist[s] = 0                     // المصدر مسافته 0
    Q = min-priority-queue(all vertices)
    while Q is not empty
        u = EXTRACT-MIN(Q)          // خذ الاقرب
        for each neighbor v of u
            if dist[u] + w(u,v) < dist[v]
                dist[v] = dist[u] + w(u,v)
                prev[v] = u         // حدّث المسار
                DECREASE-KEY(Q, v, dist[v])

التعقيد: O((V + E) log V) مع Binary Heap، او O(V² + E) مع مصفوفة عادية.

Bellman-Ford — يتعامل مع الاوزان السالبة

لما يكون عندك حواف بأوزان سالبة، Dijkstra ما يشتغل. هنا تستخدم Bellman-Ford:

BELLMAN-FORD(G, w, s)
    for each vertex v in G
        dist[v] = infinity
    dist[s] = 0
    for i = 1 to |V| - 1           // كرر V-1 مرة
        for each edge (u,v) in G
            if dist[u] + w(u,v) < dist[v]
                dist[v] = dist[u] + w(u,v)
    // كشف الدورات السالبة
    for each edge (u,v) in G
        if dist[u] + w(u,v) < dist[v]
            return "دورة سالبة موجودة"

التعقيد: O(VE) — ابطا من Dijkstra، لكن يشتغل مع اوزان سالبة ويكشف الدورات السالبة.

الخوارزمية	التعقيد	اوزان سالبة؟	كشف دورات سالبة؟
Dijkstra	O((V+E) log V)	لا	لا
Bellman-Ford	O(VE)	نعم	نعم

الشجرة الممتدة الصغرى (Minimum Spanning Tree)

MST تربط كل الرؤوس باقل تكلفة ممكنة بدون دورات. عندك خوارزميتين:

Prim: يبدا من رأس واحد ويضيف اقرب رأس غير مزار باستخدام Priority Queue. التعقيد: O((V+E) log V).

Kruskal: يرتّب كل الحواف حسب الوزن ويضيفها واحدة واحدة باستخدام Union-Find لكشف الدورات. التعقيد: O(E log E).

الخوارزمية	الافضل متى؟	هيكل البيانات
Prim	رسم كثيف (Dense Graph)	Priority Queue
Kruskal	رسم خفيف (Sparse Graph)	Union-Find

مثال Kruskal:

KRUSKAL(G)
    MST = empty set
    sort edges by weight              // رتّب الحواف
    for each edge (u,v) in sorted order
        if FIND(u) != FIND(v)         // لو ما يسببون دورة
            MST = MST + {(u,v)}
            UNION(u, v)               // ادمج المجموعتين
    return MST

7. مقدمة في NP-Completeness

هذا الموضوع يغيّر طريقة تفكيرك كمبرمج. بدل ما تسال “كيف احل هذي المشكلة؟”، تتعلم تسال: “هل يمكن حل هذي المشكلة بكفاءة؟“

P vs NP

• P: مشكلات تقدر تحلها في وقت polynomial (مثل الترتيب، اقصر مسار)
• NP: مشكلات تقدر تتحقق من حلها في وقت polynomial (مثل: لو عطيتك حل لـ Sudoku، تقدر تتاكد بسرعة انه صح)
• NP-Complete: اصعب مشكلات NP. لو حليت وحدة منها بكفاءة، حليت كلها
• NP-Hard: على الاقل بصعوبة NP-Complete، بس ما بالضرورة في NP

هل P = NP؟ هذا السؤال المفتوح الاشهر في علوم الحاسب. لو احد اثبته، يفوز بمليون دولار من جائزة Clay Millennium.

مسائل NP-Complete شهيرة

المسالة	الوصف
SAT (Satisfiability)	هل يوجد تعيين يجعل تعبير منطقي صحيح؟
3-SAT	SAT لكن بثلاث متغيرات لكل عبارة
Vertex Cover	اقل مجموعة رؤوس تغطي كل الحواف
Hamiltonian Cycle	هل يوجد دورة تمر بكل الرؤوس مرة واحدة؟
Traveling Salesman (TSP)	اقصر مسار يزور كل المدن ويرجع
0/1 Knapsack	النسخة الكاملة (ايجاد الحل الامثل بالضبط)
Graph Coloring	تلوين الرسم بـ k لون بدون تجاور نفس اللون

التحويلات (Reductions)

عشان تثبت ان مشكلة B هي NP-Complete: (1) اثبت ان B في NP، (2) خذ مشكلة NP-Complete معروفة A وحوّلها الى B في وقت polynomial. لو نجحت، هذا يعني B على الاقل بصعوبة A.

اخطاء شائعة في عال 311

1. الخلط بين O و Θ: O(n²) تعني “على الاكثر n²” بينما Θ(n²) تعني “بالضبط n²”. كن دقيق في استخدامهم
2. تطبيق الحل الجشع على كل مشكلة: الجشع ما يشتغل دائما. لازم تتاكد من Greedy Choice Property
3. حفظ حلول DP بدون فهم الحالة: لو حفظت حل Knapsack بدون ما تفهم ليش dp[i][w]، راح تضيع لو غيّروا المسالة شوي
4. نسيان شرط Dijkstra: Dijkstra ما يشتغل مع اوزان سالبة. اذا شفت وزن سالب، استخدم Bellman-Ford
5. عدم رسم الامثلة على الورقة: الخوارزميات مثل Kruskal و Prim و DP تحتاج ترسمها وتتبعها يدويا
6. اهمال البراهين: في الاختبار ممكن يطلب منك تثبت صحة خوارزمية او تحلل تعقيدها رياضيا
7. عدم التمييز بين 0/1 Knapsack و Fractional: الاول يحتاج DP والثاني ينحل بالجشع

ربط عال 311 بمسارك الاكاديمي والمهني

عال 311 مو مادة تدرسها وتنساها. هي اكثر مادة راح تستفيد منها في حياتك المهنية:

• المقابلات الوظيفية: LeetCode و HackerRank مبنية على مفاهيم عال 311
• عال 361، الذكاء الاصطناعي: خوارزميات البحث والبرمجة الديناميكية اساسية في AI
• مشروع التخرج: كثير من المشاريع تحتاج تحسين اداء خوارزمي
• الدراسات العليا: لو تفكر في ماجستير او دكتوراه، عال 311 هي اساس ابحاث الخوارزميات

لو تبي تقوّي مهاراتك البرمجية بالتوازي مع عال 311، ممكن تستفيد من الدروس الخصوصية في البرمجة عشان تاخذ شرح مخصص لمستواك.

خلاصة

عال 311 فعلا مادة صعبة. بس هي نفس الوقت اكثر مادة ممتعة لما تبدا تفهمها: تحس انك صرت تفكر كعالم حاسب مو بس مبرمج.

ركّز على فهم لماذا قبل كيف. ارسم الامثلة على الورقة. حل مسائل DP كثيرة. راجع اختبارات سابقة. ولا تخجل تطلب مساعدة لما توقف — كل طالب مرّ بنفس الصعوبات.