„Algoritmuselmélet - PPZH, 2013.05.23.” változatai közötti eltérés
Ugrás a navigációhoz
Ugrás a kereséshez
(Új oldal, tartalma: „{{Vissza|Algoritmuselmélet}} == 2013.05.23 - PPZH megoldásai== ===1. Feladat=== TODO {{Rejtett |mutatott=<big>'''Megoldás'''</big> |szöveg= TODO }} ===2. Feladat…”) |
|||
| 2. sor: | 2. sor: | ||
== 2013.05.23 - PPZH megoldásai== | == 2013.05.23 - PPZH megoldásai== | ||
| − | ===1. Feladat=== | + | ===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.) | ||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
| − | + | '''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. | ||
| + | |||
}} | }} | ||
A lap 2013. június 18., 16:25-kori változata
Tartalomjegyzék
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
TODO
Megoldás
TODO
6. Feladat
TODO
Megoldás
TODO
7. Feladat
TODO
Megoldás
TODO
8. Feladat
TODO
Megoldás
TODO
