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

הגדרה:

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

דוגמה:

1. ${\displaystyle \displaystyle \left\lceil 2.5\right\rceil =3}$
2. ${\displaystyle \displaystyle \left\lfloor 2.5\right\rfloor =2}$

הגדרה:

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

משפט:

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

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

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

כדאי לדעת:

משפט:

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

1. ${\displaystyle \displaystyle \sum _{i=1}^{n}[i]={\frac {n\cdot (n+1)}{2}}}$
2. ${\displaystyle \displaystyle \forall _{q\neq 1}\sum _{i=1}^{n}[q^{i}]={\frac {q^{n+1}-1}{q-1}}}$
3. ${\displaystyle \displaystyle \forall _{0<q<1}\sum _{i=1}^{\infty }[q^{i}]={\frac {1}{1-q}}}$
4. ${\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))}$

כדאי לדעת:

משפט:

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

1. אם ${\displaystyle \displaystyle f(n)}$ מונוטונית לא יורדת, אז ${\displaystyle \displaystyle \int _{m-1}^{n}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m}^{n+1}f(x)dx}$
2. אם ${\displaystyle \displaystyle f(n)}$ מונוטונית לא עולה, אז ${\displaystyle \displaystyle \int _{m}^{n+1}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m-1}^{n}f(x)dx}$