„Algoritmuselmélet - PPZH, 2013.05.23.” változatai közötti eltérés

@@ 2. sor: / 2. sor: @@
 == 2013.05.23 - PPZH megoldásai==
-===1. Feladat===
+===1. Feladat (Van megoldás)===
-TODO
+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.)
 {{Rejtett
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
-TODO
+'''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.
 }}