Algoritmuselmélet - PZH, 2013.04.24.

2013.04.24. PZH megoldásai

1. 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) + O(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\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 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]

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

2. Feladat

TODO

Megoldás

TODO

3. Feladat

Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha

(a) inorder bejárással kilolvasva a két fát ugyanazt a számsorozatot kapják?

(b) preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?

Megoldás

Mindkét esetben 1-1 ellenpéldát kell szolgáltatni:

• a)

200px 200px

Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

• b)

200px 200px

Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

4. Feladat

TODO

Megoldás

TODO

5. Feladat

TODO

Megoldás

TODO

6. Feladat

TODO

Megoldás

TODO

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO