📐
The Master Formulas
Linear Recurrence
For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$:
Char Eq: $r^2 - c_1 r - c_2 = 0$
Distinct Roots: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$
Repeated Root: $a_n = \alpha_1 r_0^n + \alpha_2 n r_0^n$
Distinct Roots: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$
Repeated Root: $a_n = \alpha_1 r_0^n + \alpha_2 n r_0^n$
Inclusion-Exclusion
$|A \cup B \cup C| = \sum |A_i| - \sum |A_i \cap A_j| + |A \cap B \cap C|$
تذكر: الإشارات تتبدل (+ - + -).
Handshaking Theorem
$$ 2|E| = \sum_{v \in V} \deg(v) $$
عدد الرؤوس ذات الدرجة الفردية يجب أن يكون زوجياً.
🌳
Structures Properties
Trees (Full m-ary)
- Total Vertices ($n$) $m \cdot i + 1$
- Leaves ($l$) $(m-1)i + 1$
- Internal ($i$) $(n-1)/m$
Tree Edges = Vertices - 1
Euler vs Hamilton
Euler Circuit (Edges):
موجود إذا كانت كل الدرجات زوجية.
موجود إذا كانت كل الدرجات زوجية.
Hamilton Circuit (Vertices):
لا يوجد شرط بسيط وكافٍ (مشكلة NP-Complete).
شرط Dirac (كافٍ غير لازم): $deg(v) \ge n/2$.
لا يوجد شرط بسيط وكافٍ (مشكلة NP-Complete).
شرط Dirac (كافٍ غير لازم): $deg(v) \ge n/2$.
💻
Modeling Computation
Chomsky Hierarchy
- Type 0 (Unrestricted): Turing Machine.
- Type 1 (Context-Sensitive): Linear Bounded Automata.
- Type 2 (Context-Free): Pushdown Automata.
- Type 3 (Regular): Finite Automata.
Recognizers
Finite State Machine (FSM)
ذاكرة محدودة (States only).
Turing Machine (TM)
شريط لا نهائي (Infinite Tape) + قراءة وكتابة.