מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/מתמטיקה

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מבני נתונים ואלגוריתמים - מחברת קורס | נספחים

קפיצה אל: ניווט, חיפוש

מבני נתונים ואלגוריתמים - מחברת קורס

דף זה מכיל מספר סימונים ונוסחאות שימושיים לקורס.

תוכן עניינים

1 עיגולים
2 חזקות, עצרות, ולוגריתמים
3 טורים
- 3.1 טורים שימושיים
- 3.2 חסמי אינטגרלים
4 מספר הגדרות בקבוצות

[עריכה] עיגולים

הגדרה:

$\displaystyle \left\lceil x \right \rceil$ מציין עיגול כלפי מעלה של המספר $\displaystyle x$ .
$\displaystyle \left\lfloor x \right \rfloor$ מציין עיגול כלפי מטה של המספר $\displaystyle x$ .

דוגמה:

$\displaystyle \left\lceil 2.5 \right \rceil = 3$
$\displaystyle \left\lfloor 2.5 \right \rfloor = 2$

[עריכה] חזקות, עצרות, ולוגריתמים

הגדרה:

בקורס זה, בסיס הלוגריתם הוא 2, אא"כ צויין אחרת: לכל $\displaystyle a > 0$ ,‏ $\displaystyle \log(a) = \log_2(a)$ .

משפט:

לכל $\displaystyle a, b, c > 0$ ,‏ $\displaystyle a^{\log_b(c)} = c^{\log_b(a)}$ . בפרט, $\displaystyle a = 2^{\log(a)}$ .

משפט: נוסחת סטירלינג

$\displaystyle \sqrt{2 \pi n}\left( \frac{n}{e} \right)^n \le n! \le \sqrt{2 \pi n}\left( \frac{n}{e} \right)^{n + \frac{1}{12n}}$

כדאי לדעת:

מותר להשתמש בנוסחת סטירלינג גם ללא ידיעת הוכחתה.

[עריכה] טורים

פעמים רבות, במהלך ניתוח סדר הגדילה של אלגוריתם כלשהו, יש לנתח את סדר הגדילה של טור כלשהו. נראה כעת מספר טורים שימושיים שיופיעו רבות במהלך החומר, וטכניקה כללית לניתוח טורים רבים.

[עריכה] טורים שימושיים

משפט:

לכל שלם $\displaystyle n > 1$ וקבוע $\displaystyle q > 0$ :‏

$\displaystyle \sum_{i = 1}^n[i] = \frac{n \cdot (n + 1)}{2}$
$\displaystyle \forall_{q \ne 1}\sum_{i = 1}^n[q^i] = \frac{ q^{n + 1} - 1 }{ q - 1 }$
$\displaystyle \forall_{0 < q < 1}\sum_{i = 1}^{\infty}[q^i] = \frac{1}{ 1 - q }$
$\displaystyle \sum_{i = 1}^n[\log(i)] = \Theta(n \cdot \log(n))$

הוכחה: (4)

מצד אחד, $\displaystyle \sum_{i = 1}^n[\log(i)] \le \sum_{i = 1}^n[\log(n)] = n \cdot \log(i)$

ולכן $\displaystyle \sum_{i = 1}^n[\log(i)] = O(n \cdot \log(n))$ .

מצד שני,

$\displaystyle \sum_{i = 1}^n[\log(i)] \ge \sum_{i = \left\lceil n / 2 \right\rceil}^n[\log(i)] \ge \sum_{i = \left\lceil n / 2 \right\rceil}^n[\log(\left \lfloor n / 2 \right\rfloor)] \ge (n / 2 - 1) \cdot \log (n / 2 - 1)$

ולכן $\displaystyle \sum_{i = 1}^n[\log(i)] = \Omega(n \cdot \log(n))$ (אפשר לראות זאת לפי מבחן גבול מנות).

כדאי לדעת:

אפשר להוכיח את 4 בקלות רבה גם על ידי נוסחת סטירלינג.

[עריכה] חסמי אינטגרלים

משפט:

לכל $\displaystyle f(n)$ :

אם $\displaystyle f(n)$ מונוטונית לא יורדת, אז $\displaystyle \int_{m -1}^n f(x) dx \le \sum_{i = m}^n[f(i)] \le \int _m^{n + 1} f(x) dx$
אם $\displaystyle f(n)$ מונוטונית לא עולה, אז $\displaystyle \int_m^{n + 1} f(x) dx \le \sum_{i = m}^n[f(i)] \le \int_{m - 1}^n f(x) dx$

[עריכה] מספר הגדרות בקבוצות

בקורס זה אנו מניחים ידע בסיסי בתורת הקבוצות. להלן מספר סימונים:

סימון קבוצה על ידי איבריה: $\displaystyle A = \left\{ a_1, \ldots, a_n \right\}$
שיוך איבר $\displaystyle a$ בקבוצה $\displaystyle A$ :‏ $\displaystyle a \in A$
הכלת קבוצה $\displaystyle B$ בקבוצה $\displaystyle A$ :‏ $\displaystyle B \subseteq A$
גודל קבוצה $\displaystyle A$ (מספר האיברים בה): $\displaystyle \vert A \vert$
הפרש בין קבוצות $\displaystyle A$ ו $\displaystyle B$ (האיברים שב $\displaystyle A$ אך לא ב $\displaystyle B$ ):‏ $\displaystyle A \setminus B$