Algoritmuselmélet - Vizsga, 2013.05.30.

A VIK Wikiből
A lap korábbi változatát látod, amilyen Arklur (vitalap | szerkesztései) 2013. június 7., 21:19-kor történt szerkesztése után volt.
Ugrás a navigációhoz Ugrás a kereséshez

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 [math] T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + Ο(n^2)[/math] és tudjuk azt is, hogy [math] T(1)=T(2)=T(3)=1[/math]. Bizonyítsa be, hogy [math] T(n)=O(n^2)[/math].

Megoldás

[math] 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_4n \right \rfloor} \left (\frac{1}{4} \right )^i\right)[/math]
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van egy magic képletünk:
[math]\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} [/math] ahol [math] k = \left \lfloor log_4n \right \rfloor, r = 0.25[/math], vagyis [math]\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25}[/math]
[math] \lim_{n \to \infty}\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25} = \frac{1}{0.75}[/math]

Vagyis [math] T(n)=...=1+\frac{1}{0.75}O(n^2)=O(n^2)[/math]

6. Feladat

TODO

Megoldás
TODO

7. Feladat

TODO

Megoldás
TODO

8. Feladat

TODO

Megoldás
TODO