شرح مادة عال 220 تحليل وتصميم الخوارزميات - جامعة الاميرة نورة

مادة عال 220 (المعروفة ايضا بـ CS 220)، تحليل وتصميم الخوارزميات (Algorithm Analysis & Design) بجامعة الاميرة نورة بنت عبدالرحمن، هي المادة اللي تفصل بين طالبة تعرف تكتب كود يشتغل، وطالبة تعرف تكتب كود اذكى. في CS 212 هياكل البيانات تعلمتي كيف تخزنين البيانات بطرق مختلفة. في عال 220 السؤال يتغير: ايش اسرع طريقة احل فيها المشكلة؟

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

ليش عال 220 اهم مادة في الخطة

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

• اسئلة المقابلات التقنية في STC وعلم وامازون السعودية وsdaia كلها خوارزميات. لو فهمتيها صح، نسبة نجاحك في المقابلات تتضاعف
• في مشروع التخرج، الفرق بين مشروع ياخذ ثانية ومشروع يعلق نصف دقيقة هو غالبا اختيار خوارزمية وحدة. شفنا هذا يتكرر كل فصل
• لو تفكرين في الماجستير، قبول الدراسات العليا يقرا درجة عال 220 بدقة اكثر من اي مادة ثانية
• كل ما تعمقتي في ML و AI، راح تحتاجين تفهمين التعقيد عشان تعرفين ليش نموذج يحتاج ساعة تدريب ونموذج ثاني يحتاج اسبوع
• تفكرين تشاركين في ICPC او هاكاثون؟ عال 220 هي التذكرة

نظرة عامة على خطة عال 220

المادة تتوزع عادة على 15 اسبوع بهذا الترتيب:

الاسابيع	الموضوع	صعوبة
1-2	مراجعة Big-O وتحليل التعقيد العميق	سهلة
3-4	المعادلات التكرارية ونظرية الرئيسية	متوسطة
5-6	فرق تسد (Divide and Conquer)	متوسطة
7-8	الخوارزميات الجشعة (Greedy)	متوسطة
9-11	البرمجة الديناميكية (Dynamic Programming)	صعبة
12-13	خوارزميات الرسوم البيانية	متوسطة
14	التراجع ومقدمة في NP-Completeness	صعبة
15	مراجعة شاملة ومشروع نهائي

1. تحليل التعقيد بشكل اعمق

في CS 212 تعرفتي على Big-O. في عال 220 راح تتوسعين في ثلاث رموز، كل واحد يقيس جانب مختلف:

• Big-O (O): الحد الاعلى، “الخوارزمية ما تتجاوز هذا الوقت” مثلا O(n²)
• Big-Omega (Ω): الحد الادنى، “الخوارزمية ما تقل عن هذا الوقت”
• Big-Theta (Θ): الحد الضيق، “الخوارزمية بالضبط ضمن هذي النسبة”

مثال عملي لفهم الفرق

// خوارزمية البحث الخطي
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

• افضل حالة: العنصر الاول هو المطلوب، Ω(1)
• اسوا حالة: العنصر مو موجود او في النهاية، O(n)
• الحالة العامة: مو ضيقة، فما نقدر نقول Θ لها

تعقيدات لازم تحفظينها

الخوارزمية	افضل	متوسط	اسوا
البحث الخطي	Ω(1)	Θ(n)	O(n)
البحث الثنائي	Ω(1)	Θ(log n)	O(log n)
Bubble Sort	Ω(n)	Θ(n²)	O(n²)
Merge Sort	Θ(n log n)	Θ(n log n)	O(n log n)
Quick Sort	Ω(n log n)	Θ(n log n)	O(n²)

2. المعادلات التكرارية ونظرية الرئيسية

هذا اول موضوع “رياضي صعب” في المادة. لما الخوارزمية تستدعي نفسها (Recursion)، ما نقدر نحسب تعقيدها بحلقات عادية، نحتاج معادلة تكرارية (Recurrence Relation).

مثال: تعقيد 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)
    }
}

المعادلة التكرارية:

T(n) = 2·T(n/2) + O(n)

تفسيرها: حل مشكلة حجمها n = حل مشكلتين حجمهن n/2 + تكلفة الدمج n.

نظرية الرئيسية (Master Theorem)

طريقة سريعة لحل اغلب المعادلات التكرارية من الشكل:

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

بدون ما ندخل في الاثباتات، القاعدة المختصرة:

1. قارني f(n) مع n^(log_b(a))
2. لو f(n) اصغر، الاجابة تساوي n^(log_b(a))
3. لو متساويات، الاجابة تضرب log n
4. لو f(n) اكبر، الاجابة تساوي f(n)

لـ Merge Sort: a=2, b=2, f(n) = n. حساب log₂(2) = 1، يعني n^1 = n. f(n) = n = n. الحالة الثانية: T(n) = Θ(n log n).

كثير من طالبات عال 220 يحسون ان المعادلات التكرارية اصعب جزء في المادة، خصوصا في البداية. لو حسيتي بالضياع، هذا طبيعي وما يعني انك ضعيفة في المادة.

3. فرق تسد (Divide and Conquer)

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

Binary Search، ابسط مثال

public static int binarySearch(int[] arr, int target, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    if (target < arr[mid])
        return binarySearch(arr, target, low, mid - 1);
    else
        return binarySearch(arr, target, mid + 1, high);
}

التعقيد: O(log n) لان كل خطوة تنصف حجم المشكلة.

Merge Sort، فرق تسد مع دمج

public static void merge(int[] arr, int l, int m, int r) {
    int[] temp = new int[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= m) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (k = 0; k < temp.length; k++) arr[l + k] = temp[k];
}

Merge Sort دائما Θ(n log n) في كل الحالات. هذي ميزة كبيرة على Quick Sort اللي ممكن يتحول لـ O(n²) في اسوا حالة.

Quick Sort

الفكرة: اختاري عنصر محور (pivot)، قسمي المصفوفة الى اصغر من المحور واكبر منه، ثم طبقي نفس الخوارزمية على كل قسم.

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
    int t = arr[i+1]; arr[i+1] = arr[high]; arr[high] = t;
    return i + 1;
}

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

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

مشكلة اختيار الانشطة (Activity Selection)

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

class Activity {
    int start, end;
    public Activity(int s, int e) { start = s; end = e; }
}

public static int selectActivities(Activity[] acts) {
    Arrays.sort(acts, (a, b) -> a.end - b.end);
    int count = 1, lastEnd = acts[0].end;
    for (int i = 1; i < acts.length; i++) {
        if (acts[i].start >= lastEnd) {
            count++;
            lastEnd = acts[i].end;
        }
    }
    return count;
}

مشكلة الفكة (Coin Change)، متى الجشع يفشل؟

لو عندك عملات [1, 5, 10, 25] وتبين فكة 30 ريال، الجشع يشتغل: 25 + 5 = 30. بس لو العملات [1, 3, 4] وتبين فكة 6، الجشع راح يختار 4 + 1 + 1 = 3 عملات. الحل الامثل هو 3 + 3 = عملتين فقط. هنا الجشع يفشل.

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

البرمجة الديناميكية (DP) هي اصعب موضوع في المادة بالاجماع. الفكرة: قسمي المشكلة الى مشاكل اصغر متداخلة، واحفظي حل كل مشكلة صغيرة عشان ما تحلينها مرتين.

البداية: فيبوناتشي بثلاث طرق

الطريقة السيئة، تكرار عادي

public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

التعقيد: O(2^n) لان كل استدعاء يولد استدعاءين. fib(30) ياخذ ثواني، fib(50) ياخذ دقائق.

الطريقة الوسطى، Memoization

int[] memo;
public int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

التعقيد ينزل لـ O(n) لاننا ما نحسب نفس القيمة مرتين.

الطريقة الذكية، Tabulation (Bottom-Up)

public static int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

مسالة حقيبة الظهر (0/1 Knapsack)

قبل ما ندخل في الكود، قصة صغيرة. قبل كم فصل جتنا طالبة من نورة تحل واجب Knapsack لليلتين كاملتين، كتبت الحل بالتكرار بس و فشلت ان الكود يشتغل على مدخلات اكبر من 15 عنصر. قلنا لها: المشكلة مو في الكود، المشكلة انك تعيدين حساب نفس الحالة الاف المرات. رسمنا لها شجرة الاستدعاءات، وشافت بعينها ان knapsack(2, 5) ينحسب 30 مرة في نفس التشغيل. بعد ما اضافت memoization صارت تشتغل على 100 عنصر في ثانية. هذي قصة اكثر طالبة DP مرت بها.

الفكرة بشكل رسمي: عندك حقيبة حجمها W، وعندك n من العناصر كل واحد له وزن وقيمة. اختاري مجموعة تعظم القيمة بدون ما تتجاوزين وزن الحقيبة.

public static int knapsack(int[] w, int[] v, int W) {
    int n = w.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (w[i-1] <= j)
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][W];
}

التعقيد: O(n·W).

خطوات التفكير في DP

اي مسالة DP تحلينها بنفس الخطوات الخمس:

1. عرفي الحالة (State): ايش البارامترات اللي تحدد اي مشكلة صغيرة؟ مثلا في Knapsack: (العنصر الحالي، الوزن المتبقي)
2. اكتبي المعادلة التكرارية: كيف اوصل للحل من حلول المشاكل الاصغر؟
3. حددي حالة الاساس (Base Case): ايش اصغر حالة ممكنة ومخرجها؟
4. اختاري Memoization او Tabulation: Memoization ابسط للكتابة، Tabulation اكفأ للذاكرة
5. حللي التعقيد: اضربي عدد الحالات الممكنة في تكلفة كل حالة

الطالبات اللي يعانون من DP يعانون لان المفهوم عكس ما تعودن عليه في CS 110 و CS 111. هناك كنتي تفكرين “كيف ابني الحل من الصفر؟”، هنا تفكرين “كيف استخدم حلول المشاكل الاصغر؟” التبديل بين العقليتين ياخذ وقت. لو ذاكرتي DP اسبوع ولسه ما قبضتي الفكرة، كملي ما تتوقفين، غالبا تفتح معك فجاة في الاسبوع الثاني.

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

في CS 212 تعلمتي تمثيل الرسوم البيانية و BFS و DFS. في عال 220 راح تتعلمين خوارزميات اعقد لحل مشاكل حقيقية.

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

تلاقي اقصر مسار من نقطة بداية لكل العقد في رسم باوزان موجبة. تستخدم في تطبيقات مثل خرائط جوجل وتحديد مسارات الشحن.

public static int[] dijkstra(int[][] graph, int src) {
    int n = graph.length;
    int[] dist = new int[n];
    boolean[] visited = new boolean[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        int u = minDistance(dist, visited);
        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²) في النسخة البسيطة، O(E log V) باستخدام Priority Queue.

الشجرة المغطية ذات الوزن الادنى (MST)

خوارزميتين مهمتين:

• Kruskal’s: رتبي الاضلاع بالوزن، وخذي الاقل وزنا في كل خطوة لو ما يسوي دورة. تستخدم Union-Find. التعقيد O(E log E)
• Prim’s: ابدئي من اي عقدة، اضيفي الضلع الاقل وزنا اللي يوصلك لعقدة جديدة. شبيهة بـ Dijkstra. التعقيد O(E log V)

7. التراجع (Backtracking)

التراجع هو تقنية حل المشاكل بتجربة كل الاحتمالات، والرجوع لما نصل لطريق مسدود. الامثلة الكلاسيكية: N-Queens، Sudoku، Subset Sum.

مسالة المجموع الفرعي (Subset Sum)

عندك مصفوفة ارقام ومبلغ معين، هل فيه مجموعة فرعية مجموعها يساوي المبلغ؟

public static boolean subsetSum(int[] arr, int idx, int target) {
    if (target == 0) return true;
    if (idx == arr.length || target < 0) return false;
    // اما ناخذ العنصر الحالي او ما ناخذه
    return subsetSum(arr, idx + 1, target - arr[idx])
        || subsetSum(arr, idx + 1, target);
}

التراجع تعقيده عادة اسي O(2^n) او اكثر، ولذلك نستخدم DP لتسريعه لما نقدر.

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

في نهاية المادة راح تسمعين عن P و NP و NP-Complete. الفكرة العامة بدون رياضيات:

• P (Polynomial): مشاكل نقدر نحلها بخوارزمية تعقيدها كثير حدود، مثل الترتيب O(n log n)
• NP: مشاكل لو اعطيتك حل مقترح، تقدرين تتحققين منه بسرعة، لكن ايجاد الحل نفسه قد يكون صعب
• NP-Complete: اصعب مشاكل في NP. لو حليتي وحدة منها بخوارزمية سريعة، تقدرين تحلين كل مشاكل NP

مشاكل NP-Complete مشهورة: مسالة البائع المتجول (TSP)، التلوين ثلاثي (3-Coloring)، SAT.

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

خطة مذاكرة عال 220

ربط المادة بمسارك الاكاديمي

بعد ما تنهين عال 220 بنجاح، هذي المواد اللي راح تستفيدين فيها مباشرة من اللي تعلمتيه:

• عال 321 الخوارزميات المتقدمة: تكملة مباشرة، تدخلين في خوارزميات اصعب مثل Randomized Algorithms و Amortized Analysis
• عال 322 اللغات المنضبطة والنظرية الآلية: تبني على فكرة تحليل التعقيد وتدخل في الاتمتة والنظرية
• قواعد البيانات المتقدمة: الاستعلامات والفهارس تعتمد كليا على تحليل التعقيد
• مشروع التخرج: اي مشروع فيه بيانات او ذكاء اصطناعي راح يحتاجك تختارين خوارزمية وتحللين تعقيدها
• المقابلات الوظيفية: هذي المادة هي المرجع المباشر لمقابلات شركات مثل STC و امازون السعودية

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

خلاصة

عال 220 مو مادة كود، هي مادة تفكير. الطالبة اللي تذاكرها بعقلية “كيف اكتب هذا الكود؟” راح تعاني، والطالبة اللي تذاكرها بعقلية “ايش افكار الخوارزمية؟ وكيف احلل كفاءتها؟” راح تستمتع وتتفوق.

ثلاث نصائح تنجيك من اكثر مزالق المادة:

• ورقة وقلم قبل الكود. اي خوارزمية جديدة، ارسميها يدويا على ورقة قبل ما تفتحين IDE
• فهمي قبل تحفظي. معادلات التعقيد مو للحفظ، هي للفهم. لو فهمتي ليش Merge Sort هو O(n log n)، راح تستنتجين تعقيد اي خوارزمية فرق تسد ثانية بسهولة
• لا تراكمين. المادة تراكمية بشكل حاد. فهم DP في الاسبوع 10 يعتمد على فهمك للمعادلات التكرارية في الاسبوع 3. لو فاتك موضوع، ارجعي وذاكريه فورا

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