Algoritmuselmélet - Vizsga, 2013.05.30.

2013.06.06. vizsga megoldásai

1. Feladat

TODO

kinyitMegoldás

TODO

2. Feladat

TODO

kinyitMegoldás

TODO

3. Feladat

TODO

kinyitMegoldás

TODO

4. Feladat

TODO

kinyitMegoldás

TODO

5. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy Értelmezés sikertelen (formai hiba): {\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)$.

kinyitMegoldás

$T(n)=T\left(\lfloor \frac{n}{4}\rfloor \right)+O(n^2)=T(n)=T\left(\lfloor \frac{n}{16}\rfloor \right)+O\left(\frac{n^2}{4}\right)+O(n^2)=...=1+O(n^2)*\left(\sum _{i=0}^{\lfloor lo{g}_{4}n\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=\lfloor lo{g}_{4}n\rfloor ,r=0.25$, vagyis $\frac{1-0.25^{\lfloor lo{g}_{4}n\rfloor +1}}{1-0.25}$
$\underset{n\to \mathrm{\infty }}{\lim }\frac{1-0.25^{\lfloor lo{g}_{4}n\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

kinyitMegoldás

TODO

7. Feladat

TODO

kinyitMegoldás

TODO

8. Feladat

TODO

kinyitMegoldás

TODO