خريطة النجاة والتميز 🗺️

دليلك الشامل لفك شفرات مادة Theory of Computation

1

كل شيء يجب أن تفهمه (المفاهيم العميقة)

هذه الأشياء لا تحفظها، بل افهم "كيف تعمل" لأن السؤال سيأتي كتطبيق.

  • Pumping Lemma (لنوعين): افهم أنها أداة "للإثبات بالنفي". إذا قدرت تكرر جزء من الكلمة وخرجت عن نمط اللغة، فاللغة ليست Regular (أو ليست CFL).
  • الفرق بين DFA و NFA: افهم أن NFA لديه "قدرة تخمين" (مسارات متعددة لنفس المدخل أو $\epsilon$-moves)، لكنهما متساويان في القوة (Power).
  • عمل المكدس (Stack) في PDA: افهم أن الـ PDA هي DFA + ذاكرة LIFO. هي الوحيدة القادرة على عد ومقارنة شيئين (مثل $a^n b^n$).
  • آلية عمل آلة تورنغ (TM): افهم حركة الرأس (Head) يمين ويسار، والكتابة على الشريط. هي النموذج الأقوى لأنها تملك ذاكرة عشوائية (Tape).
  • مفهوم Undecidability: افهم أن هناك مشاكل (مثل Halting Problem) لا يملك الكمبيوتر حلاً لها مهما كان قوياً.
  • الفئات P vs NP:
    • P: مشاكل نحلها بسرعة.
    • NP: مشاكل نتأكد من حلها بسرعة (لكن الحل قد يكون صعباً).
    • NP-Complete: أصعب مشاكل في NP (مثل SAT).
  • التحويل (Reduction): افهم أن تحويل المشكلة A إلى B يعني أن B أصعب أو تساوي صعوبة A. (ننقل العدوى من المعروف للجديد).
2

كل شيء يجب حفظه (صمّ)

هذه تعاريف وقواعد ثابتة تأتي نصاً.

التعاريف الرسمية (Tuples)
  • DFA: ٥ عناصر ($Q, \Sigma, \delta, q_0, F$).
  • PDA: ٧ عناصر (نفس الـ ٥ + $\Gamma$ للمكدس + $Z_0$ قاع المكدس).
  • TM: ٧ عناصر (نفس الـ ٥ + $\Gamma$ شريط + $B$ الفراغ).
خصائص الانغلاق (Closure Properties)
  • Regular: مغلقة مع الكل (Union, Intersection, Complement, Star).
  • CFL: غير مغلقة مع (Intersection, Complement). (مهم جداً).
  • Recursive: مغلقة مع متممتها (Complement).
  • RE: غير مغلقة مع متممتها.

هرم تشومسكي (Chomsky Hierarchy):
Regular $\subset$ CFL $\subset$ Recursive $\subset$ RE.

أسماء المشاكل وفئاتها:

  • P: 2-SAT, Eulerian Circuit.
  • NP-Complete: 3-SAT, Hamiltonian Circuit, TSP, Vertex Cover, Clique.
  • PSPACE: QBF.
  • Undecidable: Halting Problem, PCP, Ambiguity of CFG.
3

دليل الرموز والاختصارات (فك الشفرات)

الرمز المعنى السياق / ملاحظة للربط
$\Sigma$الأبجدية (Input Alphabet)مجموعة الرموز المسموحة (0,1 أو a,b).
$\Gamma$أبجدية الشريط/المكدسدائماً أكبر من $\Sigma$ لأنها تشمل رموزاً إضافية (مثل B أو $Z_0$).
$\delta$دالة الانتقال (Transition)محرك الآلة. يختلف شكله حسب نوع الآلة.
$L(M)$اللغة المقبولةالكلمات التي تقبلها الآلة M.
$\epsilon / \lambda$السلسلة الفارغةطولها صفر. وجودها في NFA يعني حركة مجانية.
$\phi$المجموعة الخاليةلغة لا تحتوي أي كلمات.
$\vdash$خطوة انتقال (Move)تستخدم في TM لتقول "تحركت الآلة من وضع لوضع".
$\forall / \exists$لكل / يوجدتستخدم في Logic و QBF.
PPolynomial Timeزمن معقول (سريع).
NPNondeterministic Polyزمن معقول (بالتخمين).
NPCNP-Completeزعماء المشاكل الصعبة.
4

لو كنت أنا أستاذ المادة (تسريب الاختبار الافتراضي) 🕵️‍♂️

أ) أهم المواضيع (The Hot Topics):

  • تحويلات القواعد (Simplification & CNF): سأعطيك قواعد فيها $\epsilon$ أو Unit وأطلب خطوة الحذف الأولى.
  • خصائص CFL: سأحاول خداعك بسؤال: "تقاطع لغتين CFL هو؟". الجواب: ليس بالضرورة CFL.
  • مقارنة الآلات: سأسأل عن الفرق بين PDA و TM. (الذاكرة المحدودة vs الشريط اللانهائي).
  • مشاكل NP-Complete: سأعطيك مشكلة مشهورة (مثل TSP) وأسألك عن صنفها.
ب) أهم الخدع (Traps):
  • خدعة الـ 2 vs 3: 2-SAT (سهلة P) مقابل 3-SAT (صعبة NPC). Euler (سهل) مقابل Hamiltonian (صعب).
  • خدعة المتممة: متممة Recursive هي Recursive. متممة RE هي Not RE.
  • خدعة التعريف: NP لا تعني Not Polynomial، بل Non-deterministic Polynomial.
ج) حيل "الهاكر" للحل السريع:
  • Regular Expression: لا تشتق المعادلة. خذ أقصر كلمة وجربها في الخيارات واستبعد الخطأ.
  • CNF: الجواب الصحيح شكله نظيف: (حرفين كبار $AB$) أو (حرف صغير واحد $a$). أي شيء غير ذلك اشطبه.
  • Pumping Lemma: مقارنة عددين ($a^n b^n$) = ليست Regular. مقارنة ثلاثة ($a^n b^n c^n$) = ليست CFL.
  • Logic ($P \to Q$): إذا كانت البداية (P) خطأ، فالجملة كلها صحيحة (True) فوراً.

د) الأسئلة المقالية الـ 5 المتوقعة (مع الإجابة المثالية):

س١: اشرح الفرق بين P و NP و NP-Complete؟

P: تحل بسرعة بآلة محددة. NP: نتحقق من حلها بسرعة. NPC: أصعب مشاكل NP وتتحول إليها بقية المشاكل.

س٢: أثبت أن اللغة $L = \{a^n b^n c^n\}$ ليست Context-Free؟

باستخدام Pumping Lemma: نقسم الكلمة $z=uvwxy$. من المستحيل أن يحتوي الجزءان $v, x$ على الرموز الثلاثة معاً. عند الضخ، سيزيد عدد رمزين ويختل التوازن مع الثالث.

س٣: حول القواعد $S \to aSb | ab$ إلى صيغة CNF؟

1. متغيرات للرموز: $X_a \to a, X_b \to b$.
2. القاعدة: $S \to X_a S X_b | X_a X_b$.
3. كسر الثلاثي: $S \to X_a Y$ حيث $Y \to S X_b$.

س٤: ما هي نظرية كوك (Cook’s Theorem)؟

تنص على أن مشكلة SAT هي NP-Complete. أهميتها أنها فتحت الباب لإثبات صعوبة المشاكل الأخرى بالتحويل منها.

س٥: عرف آلة تورنغ (TM)؟

نموذج رياضي يتكون من شريط لا نهائي ورأس للقراءة والكتابة ووحدة تحكم. تتكون من ٧ عناصر ($Q, \Sigma, \Gamma, \delta, q_0, B, F$).

5

الجداول الذهبية (للطباعة الذهنية)

جدول مقارنة فئات اللغات والآلات

اللغة (Language) الآلة (Machine) الذاكرة (Memory) القيود
RegularDFA / NFAلا توجد (States فقط)لا تستطيع العد
CFLPDAStack (LIFO)ذاكرة محدودة الوصول (Top only)
RecursiveTM (Halting)Tape (Infinite)قوية جداً (تتوقف دائماً)
RETM (Standard)Tape (Infinite)قد لا تتوقف (Loop)

جدول القوانين السريعة (Logic Laws)

القانونالصيغةالفائدة
De Morgan$\neg(A \land B) \equiv \neg A \lor \neg B$توزيع النفي (يقلب الإشارة).
Implication$A \to B \equiv \neg A \lor B$التخلص من السهم (مهم جداً).
Contrapositive$A \to B \equiv \neg B \to \neg A$المعاكس الإيجابي (يكافئه).
Quantifier$\neg \forall x P(x) \equiv \exists x \neg P(x)$نفي الكل هو وجود العكس.

🌟 نصيحة الختام (سر التفوق)

يا بطل، أنت الآن تملك "مفتاح المصمم" للاختبار. المادة تبدو كثيفة لكنها مترابطة.
ابدأ بالـ Regular (بدائية) $\to$ CFL (مكدس) $\to$ TM (كمبيوتر كامل).
ثم انظر للمشاكل: هل هي سهلة (P)، صعبة (NP)، أم مستحيلة (Undecidable).

بهذا التسلسل، الـ ٦٥ سؤال ستكون نزهة. توكل على الله! 💯🔥