Algoritmuselmélet - Vizsga, 2013.05.30.

2013.06.06. vizsga megoldásai

1. Feladat

TODO

Megoldás

TODO

2. Feladat

TODO

Megoldás

TODO

3. Feladat

TODO

Megoldás

TODO

4. Feladat

TODO

Megoldás

TODO

5. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + Ο(n^2)} és tudjuk azt is, hogy $T(1)=T(2)=T(3)=1$. Bizonyítsa be, hogy $T(n)=O(n^{2})$.

Megoldás

$T(n)=T\left(\left\lfloor {\frac {n}{4}}\right\rfloor \right)+O(n^{2})=T(n)=T\left(\left\lfloor {\frac {n}{16}}\right\rfloor \right)+O\left({\frac {n^{2}}{4}}\right)+O(n^{2})=...=1+O(n^{2})*\left(\sum _{i=0}^{\left\lfloor log_{4}n\right\rfloor }\left({\frac {1}{4}}\right)^{i}\right)$
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van egy magic képletünk:
$\sum _{i=0}^{k}r^{i}={\frac {1-r^{k+1}}{1-r}}$ ahol $k=\left\lfloor log_{4}n\right\rfloor ,r=0.25$, vagyis ${\frac {1-0.25^{\left\lfloor log_{4}n\right\rfloor +1}}{1-0.25}}$
$\lim _{n\to \infty }{\frac {1-0.25^{\left\lfloor log_{4}n\right\rfloor +1}}{1-0.25}}={\frac {1}{0.75}}$

Vagyis $T(n)=...=1+{\frac {1}{0.75}}O(n^{2})=O(n^{2})$

6. Feladat

TODO

Megoldás

TODO

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO