شرح مادة CPCS 223 تحليل وتصميم الخوارزميات - جامعة الملك عبدالعزيز

مادة CPCS 223، تحليل وتصميم الخوارزميات (Analysis & Design of Algorithms). لو سألت أي طالب في علوم الحاسب بجامعة الملك عبدالعزيز عن أصعب مادة في المسار، الجواب في الغالب راح يكون هذه المادة. مو لأن المادة مستحيلة، بل لأنها تتطلب نوعين من التفكير في نفس الوقت: التفكير الرياضي التحليلي والتفكير البرمجي العملي.

الخوارزميات هي قلب علوم الحاسب. كل شيء تبنيه أو تطوره لاحقا، سواء تطبيق ويب أو نظام ذكاء اصطناعي أو قاعدة بيانات، يعتمد بشكل مباشر على مدى كفاءة الخوارزميات اللي تستخدمها. المادة تبني على هياكل البيانات CPCS 204 وتضيف عليها عمق رياضي تحليلي لم تلتقِ به من قبل.

ليش CPCS 223 مختلفة عن كل المواد اللي درستها؟

في CPCS 202 و203 تعلمت تكتب كود يشتغل. في CPCS 204 تعلمت تنظّم البيانات بكفاءة. بس في CPCS 223، السؤال تغيّر بشكل جذري:

بدل “كيف أحل المشكلة؟” صار السؤال “ما أفضل طريقة ممكنة لحلها؟”

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

• هل خوارزميتي صحيحة؟ كيف أثبت ذلك رياضيا؟
• كم وقتا وذاكرة تستهلك؟
• هل في طريقة أسرع أو أذكى؟

هذا النوع من التفكير النقدي هو ما يميز مهندس البرمجيات الجيد عن غيره.

نظرة عامة على مادة CPCS 223

الأسابيع	الموضوع	المفاهيم الرئيسية
1-2	مراجعة التحليل التدريجي (Asymptotic Analysis)	Big-O, Big-Omega, Big-Theta، قواعد التبسيط
3-4	علاقات التكرار (Recurrence Relations)	طريقة الاستبدال، شجرة التكرار، المبرهنة الرئيسية
5-6	الفرق والتغلب (Divide & Conquer)	Merge Sort, Quick Sort, Binary Search, Strassen
7-8	البرمجة الديناميكية (Dynamic Programming)	Memoization, Tabulation، مسألة الحقيبة، LCS
9-10	الخوارزميات الجشعة (Greedy Algorithms)	Activity Selection, Huffman Coding, Kruskal
11	التراجع (Backtracking)	N-Queens، مسألة مجموع المجموعة
12-13	خوارزميات الرسوم البيانية (Graph Algorithms)	BFS, DFS، الترتيب الطوبولوجي، المكونات المتصلة
14	أقصر مسار والشجرة الممتدة الدنيا	Dijkstra, Bellman-Ford, Prim, Kruskal
15	مراجعة شاملة	ربط المفاهيم وتمارين الاختبار

مقارنة تعقيد الخوارزميات، Big-O Cheat Sheet

قبل ما ندخل في التفاصيل، هذا الجدول راح يكون مرجعك الدائم طول الفصل:

الرمز	الاسم	مثال	n=100
O(1)	ثابت (Constant)	الوصول لعنصر في مصفوفة	1 عملية
O(log n)	لوغاريتمي (Logarithmic)	البحث الثنائي	~7 عمليات
O(n)	خطي (Linear)	البحث التسلسلي	100 عملية
O(n log n)	خطي لوغاريتمي	Merge Sort	~700 عملية
O(n²)	تربيعي (Quadratic)	Bubble Sort	10,000 عملية
O(n³)	مكعبي (Cubic)	ضرب المصفوفات التقليدي	1,000,000 عملية
O(2ⁿ)	أسي (Exponential)	Fibonacci التكراري الساذج	ضخم جدا
O(n!)	مضروب (Factorial)	كل التباديل	مستحيل عمليا

1. التحليل التدريجي، Asymptotic Analysis

Big-O، Big-Omega، وBig-Theta

هذي المفاهيم الثلاثة أساس كل شيء في المادة. فهمها صح من البداية يوفّر عليك تشويش كبير لاحقا.

Big-O (الحد الأعلى): الحد الأعلى لوقت تنفيذ الخوارزمية. بمعنى آخر، أسوأ سيناريو ممكن.

Big-Omega (الحد الأدنى): أفضل سيناريو ممكن. مفيد نظريا بس أقل استخداما عمليا.

Big-Theta (الحد الدقيق): لما تكون الخوارزمية لها نفس السلوك في أحسن وأسوأ الحالات. يعني Big-O وBig-Omega متطابقان.

قواعد تبسيط Big-O لازم تحفظها

• احذف الثوابت: O(3n) تصير O(n)
• احتفظ بالحد الأعلى: O(n² + n) تصير O(n²)
• الحلقات المتداخلة تتضاعف: حلقتان متداخلتان على n تعطيان O(n²)
• الحلقات المتتالية تُجمع: حلقتان متتاليتان O(n) + O(n) = O(n)

// مثال تحليل، هذا الكود ما تعقيده؟
public static void example(int[] arr) {
    int n = arr.length;
    // حلقة واحدة: O(n)
    for (int i = 0; i < n; i++) {
        System.out.println(arr[i]);
    }
    // حلقتان متداخلتان: O(n^2)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(arr[i] + arr[j]);
        }
    }
}
// المجموع: O(n) + O(n^2) = O(n^2) بعد الحذف

2. علاقات التكرار، Recurrence Relations

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

المبرهنة الرئيسية، Master Theorem

المبرهنة الرئيسية هي اختصار قوي لحل كثير من علاقات التكرار اللي تأخذ الشكل:

T(n) = a T(n/b) + f(n)

حيث a عدد المشاكل الفرعية، 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) + O(n). هنا a=2، b=2، f(n)=n. log_2(2)=1، وf(n)=n=n¹، فنحن في الحالة الثانية. الناتج T(n) = Θ(n log n). هذا يطابق ما تعرفه عن Merge Sort.

3. الفرق والتغلب، Divide and Conquer

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

Merge Sort، المثال الكلاسيكي

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);      // قسّم الجزء الأيسر
        mergeSort(arr, mid + 1, right); // قسّم الجزء الأيمن
        merge(arr, left, mid, right);   // ادمج الجزأين
    }
}
// التعقيد: O(n log n) في جميع الحالات

Binary Search، ذكاء في نصف ثانية

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // العنصر غير موجود
}
// التعقيد: O(log n)

ليش Binary Search عبقرية؟ لأنها في كل خطوة تشطب نص الاحتمالات. مليار عنصر يحتاج فقط 30 خطوة.

Quick Sort، الأسرع في التطبيق العملي

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}
// أفضل وأوسط حالة: O(n log n)
// أسوأ حالة: O(n^2) عند اختيار pivot سيء

4. البرمجة الديناميكية، Dynamic Programming

وصلنا للجزء الأصعب في المادة. كثير من الطلاب يتعثّرون هنا. البرمجة الديناميكية (DP) مو تقنية برمجية بالمعنى المعتاد، هي طريقة تفكير.

الفكرة الأساسية: لو مشكلة كبيرة تتكوّن من مشاكل أصغر متكررة، بدل ما تحلّ كل مشكلة من أول وجديد، احفظ الحل في جدول وارجع إليه عند الحاجة.

متى تستخدم DP؟

لازم تتوفر شرطان:

1. مشاكل فرعية متداخلة (Overlapping Subproblems): نفس المشكلة الفرعية تحسب أكثر من مرة
2. البنية المثلى (Optimal Substructure): الحل الأمثل للمشكلة الكبيرة يتكوّن من حلول مثلى للمشاكل الأصغر

مثال Fibonacci، من O(2ⁿ) إلى O(n)

// الطريقة الساذجة: O(2^n) بطيء جدا
public static int fibSlow(int n) {
    if (n <= 1) return n;
    return fibSlow(n - 1) + fibSlow(n - 2);
}

// DP بـ Memoization: O(n) بعد حفظ النتائج
static int[] memo = new int[1000];
public static int fibDP(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n]; // الحل محفوظ، ارجع إليه
    memo[n] = fibDP(n - 1) + fibDP(n - 2);
    return memo[n];
}

مسألة أطول سلسلة مشتركة، LCS

من أشهر مسائل DP. عندك سلسلتان من الحروف، تبي تعرف أطول تسلسل مشترك بينهما.

public static int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1))
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}
// التعقيد: O(m*n) وقتا وذاكرة

مسألة الحقيبة (0/1 Knapsack)

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

public static int knapsack(int W, int[] wt, int[] val, int n) {
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w]; // لا تاخذ الغرض i
            if (wt[i-1] <= w)      // لو ممكن تاخذه
                dp[i][w] = Math.max(dp[i][w],
                    val[i-1] + dp[i-1][w - wt[i-1]]);
        }
    }
    return dp[n][W];
}
// التعقيد: O(n*W) وقتا وذاكرة

5. الخوارزميات الجشعة، Greedy Algorithms

الخوارزمية الجشعة بسيطة في مبدأها: في كل خطوة، خذ القرار الأفضل محليا وامشِ. لا ترجع للخلف، لا تجرّب بدائل. الفكرة أن هذه القرارات المحلية الجشعة تقود للحل الأمثل عالميا.

الفرق الحقيقي مع DP: DP تنظر لكل الاحتمالات وتختار الأمثل. Greedy تختار الأفضل الآن وتمشي بدون رجعة.

متى تنجح الخوارزمية الجشعة؟

ليست كل المشاكل تُحل بشكل جشع. تحتاج إثبات أن الاختيار الجشع دائما يقود للحل الأمثل. كثير من المشاكل تحتاج DP لا Greedy.

Huffman Coding، ضغط البيانات

خوارزمية Huffman لضغط البيانات تستخدم الجشع: الحرف الأكثر تكرارا يأخذ أقصر كود، والأقل تكرارا يأخذ أطول كود.

// الفكرة المبسطة لـ Huffman
// 1. احسب تكرار كل حرف
// 2. أنشئ min-heap من العقد (حرف، تكرار)
// 3. كرر: اسحب أصغر عقدتين، ادمجهما بعقدة أب
// 4. أعد العقدة المدمجة للـ heap
// 5. الشجرة الناتجة هي شجرة Huffman
// التعقيد: O(n log n)

مسألة اختيار الأنشطة، Activity Selection

عندك n نشاط لكل نشاط وقت بداية ونهاية، تبي تختار أكبر عدد من الأنشطة غير المتداخلة.

الحل الجشع: رتّب الأنشطة حسب وقت النهاية، اختر الأول، ثم اختر كل نشاط ينتهي قبل ما يبدأ التالي يختار.

public static int activitySelection(int[] start, int[] end) {
    // بافتراض الترتيب حسب وقت الانتهاء
    int count = 1, lastEnd = end[0];
    for (int i = 1; i < start.length; i++) {
        if (start[i] >= lastEnd) {
            count++;
            lastEnd = end[i];
        }
    }
    return count;
}
// التعقيد: O(n log n) مع الترتيب، O(n) بعده

6. التراجع، Backtracking

التراجع هو البحث الذكي. تجرّب حلا، لو ما نجح، ارجع وجرّب غيره. أبسط من DP رياضيا، لكن أبطأ عموما لأنه يجرّب أكثر من احتمال.

مسألة N-Queens

ضع N ملكة على رقعة شطرنج N×N بحيث لا تهاجم أي ملكة أخرى.

public static boolean solveNQueens(int[][] board, int row, int n) {
    if (row == n) return true; // وضعنا كل الملكات
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 1; // ضع الملكة
            if (solveNQueens(board, row + 1, n))
                return true;
            board[row][col] = 0; // ارجع وجرّب غيره
        }
    }
    return false;
}
// التعقيد: O(n!) في أسوأ حالة

7. خوارزميات الرسوم البيانية، Graph Algorithms

الرسوم البيانية (Graphs) هي هيكل بيانات قوي جدا يمثّل العلاقات بين الأشياء. الشبكات الاجتماعية، خرائط الطرق، شبكات الحاسوب، كلها تُمثَّل بـ Graphs.

BFS وDFS، الأساس

BFS (البحث بالعرض): يستكشف المستوى الأقرب أولا. يستخدم Queue. مثالي لإيجاد أقصر مسار في رسم بياني غير موزون.

public static void bfs(int[][] adj, int start, int n) {
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}
// التعقيد: O(V + E) حيث V عدد الرؤوس وE عدد الحواف

DFS (البحث بالعمق): ينزل في أعمق مسار ممكن قبل الرجوع. يستخدم Stack أو Recursion. مثالي لاكتشاف الدورات وترتيب الأعتمادية.

public static void dfs(int[][] adj, int node, boolean[] visited) {
    visited[node] = true;
    System.out.print(node + " ");
    for (int neighbor : adj[node]) {
        if (!visited[neighbor])
            dfs(adj, neighbor, visited);
    }
}
// التعقيد: O(V + E)

خوارزمية Dijkstra، أقصر مسار

لو عندك رسم بياني بأوزان موجبة وتبي أقصر مسار من نقطة لأخرى، Dijkstra هي الجواب.

// Dijkstra المبسطة
public static int[] dijkstra(int[][] graph, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    boolean[] visited = new boolean[n];
    dist[src] = 0;
    for (int count = 0; count < n - 1; count++) {
        int u = minDistance(dist, visited, n); // أقرب رأس غير محسوب
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0
                    && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        }
    }
    return dist;
}
// التعقيد: O(V^2) بالتطبيق البسيط، O((V+E) log V) مع Priority Queue

الشجرة الممتدة الدنيا، Minimum Spanning Tree

لو عندك رسم بياني غير موجه وتبي توصّل كل الرؤوس بأقل تكلفة إجمالية ممكنة، تحتاج MST.

خوارزميتان رئيسيتان:

• Kruskal: رتّب الحواف حسب الوزن، أضف الأخف تدريجيا مع تجنب الدورات. يستخدم Union-Find.
• Prim: ابدأ من رأس، أضف دائما الحافة الأخف تصل لرأس جديد. يشبه Dijkstra.

كلتاهما تعطيان O(E log E) أو O(E log V).

خطوات النجاح في CPCS 223

الأخطاء الشائعة في CPCS 223

الخطأ الأول: اللجوء لـ DP لكل شيء. مو كل مسألة تحتاج DP. أحيانا Greedy أسرع وأبسط. السؤال الصحيح دائما: هل في حل جشع يُثبت أنه مثالي؟

الخطأ الثاني: نسيان إثبات صحة الخوارزمية. في الاختبار مو بس تكتب الكود، تحتاج تقنع الدكتور أن الخوارزمية صحيحة وتحلل تعقيدها.

الخطأ الثالث: الخلط بين Memoization وTabulation في DP. Memoization = تكرار + حفظ (من فوق لأسفل). Tabulation = جدول يُملأ تدريجيا (من أسفل لفوق). كلاهما DP لكن بأسلوب مختلف.

إهمال التحليل الرياضي مشكلة رابعة. تكتب الكود وتشتغل، بس ما تعرف ليش هو O(n log n). هذا يضرّك في الاختبار.

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

ربط CPCS 223 بالمواد الأخرى

مادة الخوارزميات لها روابط قوية مع مواد كثيرة في خطتك الدراسية:

المتطلبات السابقة اللي تؤثر عليك:

• CPCS 204، هياكل البيانات: أشجار، قوائم، وطوابير هي الأدوات اللي تبني عليها الخوارزميات. ضعفك فيها سينعكس هنا.
• CPCS 222، الرياضيات المتقطعة: الإثباتات الرياضية والمنطق الصوري ضروريان لإثبات صحة الخوارزميات وتحليلها.

ما تبنيه في هذه المادة: تقدر تقرأ أكثر عن الجانب العملي في دليل هياكل البيانات والخوارزميات الشامل اللي يربط المفاهيم النظرية بالتطبيق العملي في مشاريع البرمجة.

نصائح ذهبية قبل الاختبار

لو أسبوع الاختبار وصل وأحس إنك مو مستعد كفاية، هذه أولويات ذاكر فيها:

1. راجع جدول Big-O وتأكد تقدر تحلل أي كود تشوفه.
2. ذاكر المبرهنة الرئيسية وشروط تطبيقها.
3. اشتغل على ثلاث مسائل DP كلاسيكية (Fibonacci, LCS, Knapsack) وتأكد تقدر تبنيها من الصفر.
4. اعرف BFS وDFS وDijkstra وKruskal.
5. راجع أسئلة اختبارات قديمة.

هل CPCS 223 مهمة بعد التخرج؟

الإجابة المختصرة: أكثر مما تتوقع.

شركات التقنية الكبرى مثل Google وMeta وAmazon وMicrosoft تجعل مسائل الخوارزميات جوهر مقابلاتها التقنية. خوارزميات البحث، نظم التوصيات، خوارزميات الضغط، بروتوكولات الشبكات، محركات قواعد البيانات، كلها تعتمد على المفاهيم اللي تدرسها هنا.

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

من ناحية أكاديمية، الخوارزميات هي المدخل لمواد الذكاء الاصطناعي وتعلم الآلة، اللي تعتمد بشكل مباشر على تحليل التعقيد والبرمجة الديناميكية والرسوم البيانية.