شرح مادة عال 281 (CSC 281) التراكيب المتقطعة - جامعة الملك سعود

مادة عال 281 (CSC 281)، التراكيب المتقطعة (Discrete Mathematics for Computer Science)، تعتبر من اكثر المواد اللي تفاجئ طلاب علوم الحاسب في جامعة الملك سعود. الطالب جاي وهو يتوقع كود وبرمجة، فيلقى نفسه يكتب براهين رياضية ويحل مسائل منطق. بس بعد ما تخلص المادة، تكتشف انها كانت اساس كل شي راح تدرسه بعدين.

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

ليش عال 281 مادة محورية في خطتك؟

كثير من الطلاب يستهينون بـ 281 ويعتبرونها “مادة رياضيات تعدّيها”، لكن الحقيقة عكس ذلك. هذي المادة هي اللي تفصل بين الطالب اللي يحفظ الكود والطالب اللي يفهم كيف يشتغل.

• اساس تحليل الخوارزميات: Big-O والتعقيد اللي راح تشوفه في عال 311 مبني على مفاهيم المجموعات والاستقراء
• قواعد البيانات: الجبر العلائقي في عال 380 هو في الاصل عمليات على المجموعات
• شبكات الحاسب: خوارزميات التوجيه (Routing) مبنية على نظرية الرسوم البيانية
• الذكاء الاصطناعي: خوارزميات البحث (BFS, DFS, A*) كلها تطبيقات على Graphs
• التشفير والامن: RSA و Diffie-Hellman مبنية على نظرية الاعداد والحساب الموديولي
• مقابلات الشركات: اسئلة LeetCode الصعبة غالبا تحتاج تفكير تركيبي او براهين تكرارية

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

الاسابيع	الموضوع	المفاهيم الرئيسية
1-2	المنطق والقضايا	Propositions, Truth Tables, Implications, Quantifiers
3	طرق البرهان	Direct Proof, Contradiction, Contrapositive
4	المجموعات	Union, Intersection, Power Set, Cartesian Product
5	الدوال	Injective, Surjective, Bijective, Composition
6-7	التسلسلات والاستقراء الرياضي	Mathematical Induction, Strong Induction
8	العلاقات التكرارية	Recurrence Relations, Solving Linear Recurrences
9	التوافيق والتباديل	Permutations, Combinations, Binomial Theorem
10	الاحتمالات المتقطعة	Discrete Probability, Bayes Theorem
11	نظرية الاعداد	Modular Arithmetic, GCD, Euclidean Algorithm
12	العلاقات	Equivalence Relations, Partial Orders
13-14	الرسوم البيانية	Graph Theory, Trees, Spanning Trees
15	المراجعة وحل اسئلة سابقة	—

1. المنطق والقضايا (Propositional Logic)

اول موضوع في المادة هو المنطق، وهذي مو صدفة. كل البرمجة في النهاية مبنية على عبارات منطقية: if, while, &&, ||. الفرق ان في 281 راح تتعلم كيف تحلل هذي العبارات رياضيا.

القضايا والروابط المنطقية

القضية (Proposition) هي جملة لها قيمة صدق محددة: صحيحة (T) او خاطئة (F).

P: 5 + 3 = 8       (T)
Q: الرياض عاصمة مصر  (F)
R: x > 10           (ليست قضية، تعتمد على x)

الروابط الاساسية:

الرابط	الرمز	المعنى	التشبيه البرمجي
النفي	¬P	ليس P	!P
العطف	P ∧ Q	P و Q	P && Q
الفصل	P ∨ Q	P او Q	P || Q
الاستلزام	P → Q	اذا P فان Q	لا يوجد مكافئ مباشر
التكافؤ	P ↔ Q	P اذا وفقط اذا Q	P == Q

المسورات (Quantifiers)

المسور الكلي (∀) يعني “لكل”، والمسور الوجودي (∃) يعني “يوجد”.

∀x ∈ ℕ: x ≥ 0          (لكل عدد طبيعي اكبر او يساوي صفر — صحيح)
∃x ∈ ℕ: x² = 16        (يوجد عدد طبيعي مربعه 16 — صحيح، x = 4)
∀x ∈ ℕ ∃y ∈ ℕ: y > x   (لكل عدد، يوجد عدد اكبر منه — صحيح)

نفي المسور: نفي ∀ يعطيك ∃، والعكس. هذي قاعدة دي مورجان للمسورات.

¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)

2. المجموعات والعلاقات (Sets and Relations)

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

العمليات الاساسية على المجموعات

العملية	الرمز	المعنى
الاتحاد	A ∪ B	كل عنصر في A او في B
التقاطع	A ∩ B	كل عنصر في A و B
الفرق	A − B	كل عنصر في A وليس في B
المتممة	Aᶜ	كل عنصر خارج A
الجداء الديكارتي	A × B	جميع الازواج المرتبة (a, b)
مجموعة القوة	P(A)	جميع المجموعات الجزئية لـ A

مجموعة القوة P(A) فيها 2ⁿ عنصر اذا كان |A| = n. هذا الناتج كثير راح يطلع معك في تحليل الخوارزميات.

العلاقات

العلاقة R بين A و B هي مجموعة جزئية من A × B. كثير من المسائل في 281 تطلب منك تحدد:

• هل العلاقة انعكاسية (Reflexive)؟ — كل عنصر مرتبط بنفسه
• هل العلاقة متماثلة (Symmetric)؟ — اذا a R b فان b R a
• هل العلاقة متعدية (Transitive)؟ — اذا a R b و b R c فان a R c

اذا اجتمعت الخصائص الثلاث، تكون العلاقة علاقة تكافؤ (Equivalence Relation)، وتقسم المجموعة الى اقسام (Partitions). هذي الفكرة هي اللي يبنى عليها مفهوم الفئات في تعلم الالة وتقسيم البيانات.

3. الدوال (Functions)

الدالة f: A → B هي قاعدة تربط كل عنصر في A بعنصر واحد بالضبط في B. كل دالة تعرفها في الرياضيات هي حالة خاصة من هذا التعريف.

انواع الدوال

• متباينة (Injective / One-to-One): كل عنصر في B يقابل عنصر واحد على الاكثر في A
• شاملة (Surjective / Onto): كل عنصر في B يقابل عنصر واحد على الاقل في A
• متقابلة (Bijective): متباينة وشاملة في نفس الوقت — تعطي علاقة واحد لواحد كاملة

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

f(x) = 2x        (متباينة لكن غير شاملة على الاعداد الصحيحة)
f(x) = x mod 5   (شاملة على {0,1,2,3,4} لكن غير متباينة)
f(x) = x + 1     (متقابلة على الاعداد الصحيحة)

4. طرق البرهان (Proof Techniques)

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

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

البرهان المباشر (Direct Proof)

تبدا من الفرضيات وتصل للنتيجة عن طريق سلسلة من الخطوات المنطقية.

مثال: اثبت ان مجموع عددين زوجيين هو زوجي.

لو n و m عددان زوجيان
اذن n = 2k₁ و m = 2k₂ لاعداد صحيحة k₁, k₂
n + m = 2k₁ + 2k₂ = 2(k₁ + k₂)
بما ان (k₁ + k₂) عدد صحيح، فان n + m من الشكل 2 × (عدد صحيح)
اذن n + m زوجي. ∎

البرهان بالتناقض (Proof by Contradiction)

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

مثال: اثبت ان √2 عدد غير نسبي.

افتراض العكس: √2 = p/q بحيث p, q اعداد صحيحة و gcd(p,q) = 1. بالتربيع: 2 = p²/q² → 2q² = p² → p² زوجي → p زوجي. نضع p = 2k، اذن 2q² = 4k² → q² = 2k² → q² زوجي → q زوجي. لكن لو p زوجي و q زوجي فان gcd(p,q) ≥ 2، تناقض مع الافتراض. ∎

الاستقراء الرياضي (Mathematical Induction)

اقوى ادوات البرهان في علوم الحاسب، لانها تشبه التكرار في البرمجة.

خطوات الاستقراء:

1. حالة الاساس: اثبت ان العبارة صحيحة لـ n = 1 (او n = 0)
2. فرضية الاستقراء: افترض ان العبارة صحيحة لـ n = k
3. خطوة الاستقراء: اثبت ان العبارة صحيحة لـ n = k + 1

مثال: اثبت ان 1 + 2 + 3 + … + n = n(n+1)/2.

حالة الاساس: n = 1، طرف ايسر = 1، طرف ايمن = 1(2)/2 = 1. ✓
فرضية: 1 + 2 + ... + k = k(k+1)/2
خطوة: نضيف (k+1) للطرفين
1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1)
                       = (k+1)(k/2 + 1)
                       = (k+1)(k+2)/2 ✓ ∎

5. التوافيق والتباديل (Combinatorics)

العد التركيبي يجاوب على سؤال: “كم طريقة فيه ل…؟”. هذا السؤال يطلع كثير في تحليل الخوارزميات والاحتمالات.

القواعد الاساسية

• قاعدة الجمع: لو فيه n طريقة لعمل A، و m طريقة لعمل B، فان عدد طرق عمل A او B = n + m
• قاعدة الضرب: عدد طرق عمل A ثم B = n × m

التباديل (Permutations)

التبديل = اختيار وترتيب. عدد طرق ترتيب n عنصر = n! (n factorial).

P(n, r) = n! / (n − r)!   عدد طرق اختيار وترتيب r من n

التوافيق (Combinations)

التوفيق = اختيار بدون ترتيب.

C(n, r) = n! / (r! × (n − r)!)   عدد طرق اختيار r من n بدون ترتيب

مثال: كم طريقة فيه لاختيار 3 طلاب من فصل فيه 10 لتشكيل لجنة؟

C(10, 3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 120

مبدأ الحمام (Pigeonhole Principle)

لو فيه n+1 حمامة و n عش، لازم عش واحد على الاقل فيه حمامتين. هذي الفكرة بسيطة لكن قوية، وتستخدم في اثبات تصادمات Hash Tables وفي خوارزميات التشفير.

6. الرسوم البيانية والاشجار (Graphs and Trees)

الرسم البياني هو هيكل يتكون من راس (Vertices) واضلاع (Edges) تربط بينها. هذا الموضوع راح يلازمك في كل المواد المتقدمة.

المفاهيم الرئيسية

• المسار (Path): سلسلة رؤوس متصلة باضلاع
• الدائرة (Cycle): مسار يبدا وينتهي في نفس الراس
• الاتصال (Connectivity): الرسم متصل لو فيه مسار بين اي راسين
• درجة الراس (Degree): عدد الاضلاع المتصلة به

الاشجار (Trees)

الشجرة هي رسم بياني متصل وبدون دورات. خصائصها:

• شجرة بـ n راس فيها n−1 ضلع بالضبط
• بين اي راسين فيه مسار واحد بالضبط
• اذا اضفت اي ضلع، تتكون دورة

تطبيقات في علوم الحاسب:

الهيكل	الاستخدام
Binary Search Tree	البحث المرتب
AVL Tree	بحث متوازن O(log n)
Heap	طوابير الاولوية
Trie	البحث في النصوص
Spanning Tree	بروتوكولات الشبكات (مثل STP)

نظرية اويلر (Euler)

نظرية اويلر مهمة وتطلع في الاختبار غالبا: الرسم له مسار اويلر اذا وفقط اذا كان عدد الرؤوس ذات الدرجة الفردية = 0 او 2 بالضبط.

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

كثير من الطلاب يخسرون درجات في الاختبار بسبب نفس الاخطاء المتكررة. تجنبها يرفع درجتك بدون مجهود اضافي.

• الخلط بين الاستلزام والتكافؤ: P → Q ليست P ↔ Q. الاستلزام في اتجاه واحد
• نسيان حالة الاساس في الاستقراء: بدون حالة الاساس، البرهان غير مكتمل ولو الخطوة صحيحة
• استخدام التباديل بدل التوافيق او العكس: اسال نفسك “هل الترتيب يهم؟” قبل ما تختار الصيغة
• افتراض ان الدالة متقابلة بدون اثبات: لازم تثبت انها متباينة وشاملة قبل ما تستخدم وجود الدالة العكسية
• الخلط بين A ⊆ B و A ∈ B: الاول مجموعة جزئية، الثاني عضوية مباشرة
• عدم رسم جدول الصدق كامل: اذا فيه n قضية، الجدول لازم 2ⁿ صف. لا تختصر

ربط عال 281 بمسارك الاكاديمي

عال 281 ليست محطة منعزلة، هي لغة راح تستخدمها في كل ما يجي بعدها:

• عال 311 (تصميم الخوارزميات): Big-O وتحليل التعقيد مبني على المجموعات والاستقراء. راجع دليل عال 311 الخوارزميات
• عال 380 (قواعد البيانات): الجبر العلائقي هو في الاصل عمليات على المجموعات (Union, Intersection, Cartesian Product)
• عال 339 (نظرية الحوسبة): كل المادة عبارة عن براهين رياضية على الالات والاوتوماتا
• عال 361 (الذكاء الاصطناعي): خوارزميات البحث (BFS, DFS, A*) كلها مبنية على نظرية الرسوم البيانية
• التشفير وامن الانظمة: RSA و Diffie-Hellman مستحيل تفهمهم بدون نظرية الاعداد والحساب الموديولي

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

خلاصة

عال 281 ليست مادة “تعدّيها”، هي اساس كل ما هو جاي في تخصصك. الطلاب اللي يحطون فيها مجهود ويفهمونها عدل، يلاقون باقي مواد علوم الحاسب اوضح بكثير. لا تخاف من البراهين، هي مهارة تتحسن مع التمرين، والمكافاة في النهاية تستاهل.

ابدا بدري، حل تمارين Rosen، وما تستهين بمواضيع المنطق والمسورات لانها تطلع في كل اختبار. لو وقفت في موضوع، اطلب المساعدة قبل ما يتراكم. النجاح في 281 يفتح لك ابواب 6 مواد على الاقل بسهولة اكبر.