Algoritmuselmélet - PPZH, 2013.05.23.

← Vissza az előző oldalra – Algoritmuselmélet

2013.05.23 - PPZH megoldásai

1. Feladat (Van megoldás)

Tudjuk, hogy az [math] f(n), g(n) : \textsc{N} \rightarrow \textsc{N} [/math] függvényekre igaz, hogy [math] f(n)= \Omega (logn) [/math] és [math] g(n) = \Theta (n^4) .[/math] Lehetséges-e, hogy:

(a) [math] f(n) = \Theta (g(n)) ?[/math]

(b) [math] g(n) = O(f(n)) ?[/math]

(Ez két, egymástól függetlenül megválaszolandó kérdés.)

Megoldás

a)

• Ha [math] f(n) = n^4 , g(n) = n^4 [/math]
• Akkor igaz az, hogy:
  • [math] f(n)= \Omega (logn) \Rightarrow n^4 = \Omega (logn)[/math]
  • És az is, hogy [math] f(n) = \Theta (g(n)) \Rightarrow n^4 = \Theta (n^4)[/math]
• Tehát lehetséges.

b)

• Ha [math] g(n) = n^4 , f(n) = n^4 [/math]
• Akkor igaz az, hogy:
  • [math] g(n)= \Theta (n^4) \Rightarrow n^4 = \Theta (n^4)[/math]
  • És az is, hogy [math] g(n) = O(f(n)) \Rightarrow n^4 = O(n^4)[/math]
• Tehát lehetséges.

2. Feladat

TODO

Megoldás

TODO

3. Feladat

TODO

Megoldás

TODO

4. Feladat

TODO

Megoldás

TODO

5. Feladat (Van megoldás)

Egy kupac elemeit preorder bejárás szerint kiolvasva az alábbi számsorozatot kapjuk: [math] 1, 17, 19, 21, 22, 31, 37, 2, 8, 3.[/math] Rekonstruálható-e ebből a kupac?

Megoldás

• A kupac egy teljes bináris fa, így tudjuk, hogy mi a fa alakja.
• Nincs is más dolgunk, mint felrajzolni, majd a preorder bejárás alapján beírni az elemeket a megfelelő csúcsokba, és ellenőrizni, hogy sérül-e valahol a kupac adatszerkezet egy tulajdonsága.

• Látszik, hogy minden rendben van, így a kupac rekonstruálható.

6. Feladat

TODO

Megoldás

TODO

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO