„Algoritmuselmélet 2010.11.19. PZH megoldásai” változatai közötti eltérés
(2 közbenső módosítás, amit egy másik szerkesztő végzett, nincs mutatva) | |||
2. sor: | 2. sor: | ||
== 2010.11.19 - PZH megoldásai== | == 2010.11.19 - PZH megoldásai== | ||
− | ===1. Feladat=== | + | ===1. Feladat (Van megoldás)=== |
− | + | Az alábbi függvényeket rendezze olyan sorozatba, hogy ha <math> f_i </math> után közvetlenül <math> f_j </math> következik a sorban, akkor <math> f_i(n) = O(f_j(n)) </math> teljesüljün! | |
+ | |||
+ | *<math> f_1(n)=2010 \cdot log_3(n^n) </math><br><br> | ||
+ | *<math> f_2(n)=n^{1+2+ \dots +loglogn} </math><br><br> | ||
+ | *<math> f_3(n)=4^{100+logn} </math><br><br> | ||
+ | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
− | + | *<math> f_1(n)=2010 \cdot log_3(n^n) = 2010n \cdot log_3n </math><br><br> | |
+ | *<math> f_2(n)=n^{1+2+ \dots +loglogn} </math> ezt alulról becsülhetjük <math> f_{2}^{*}(n) = n^{logn} </math>-nel.<br><br> | ||
+ | *<math> f_3(n)=4^{100+logn} = 4^{100} \cdot 4^{logn} = 4^{100} \cdot (2^2)^{logn} = 4^{100} \cdot (2^{logn})^2 = 4^{100} \cdot n^2</math><br><br> | ||
+ | |||
+ | *Első lépésben belátjuk, hogy <math> f_1(n)=O(f_3(n)). </math><br><br> | ||
+ | **<math> 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 </math><br><br> | ||
+ | **<math> 2010 \cdot log_3n \leq c \cdot 4^{100} \cdot n </math><br><br> | ||
+ | **<math> log_3n \leq c \cdot \frac{4^{100}}{2010} \cdot n </math><br><br> | ||
+ | **<math> c=\frac{2010}{4^{100}}, n \geq 1 </math><br><br> | ||
+ | |||
+ | *Második lépésben belátjuk, hogy <math> f_1(n)=O( f_{2}^{*}(n)). </math> ''(Ha ezt belátjuk, akkor <math> f_1(n)=O( f_{2}(n)) </math> is igaz lesz.)'' <br><br> | ||
+ | **<math> 4^{100} \cdot n^2 \leq c \cdot n^{logn} </math><br><br> | ||
+ | **<math> n^2 \leq \frac{c}{4^{100}} \cdot n^{logn} </math><br><br> | ||
+ | **<math> c = 4^{100} </math><br><br> | ||
+ | **És a kitevők alapján pedig <math> n \geq 4 </math><br><br> | ||
+ | |||
+ | *Tehát a megoldás <math> f_1(n) \rightarrow f_3(n) \rightarrow f_2(n) .</math> | ||
}} | }} | ||
A lap jelenlegi, 2014. április 22., 20:19-kori változata
Tartalomjegyzék
2010.11.19 - PZH megoldásai
1. Feladat (Van megoldás)
Az alábbi függvényeket rendezze olyan sorozatba, hogy ha [math] f_i [/math] után közvetlenül [math] f_j [/math] következik a sorban, akkor [math] f_i(n) = O(f_j(n)) [/math] teljesüljün!
- [math] f_1(n)=2010 \cdot log_3(n^n) [/math]
- [math] f_2(n)=n^{1+2+ \dots +loglogn} [/math]
- [math] f_3(n)=4^{100+logn} [/math]
- [math] f_1(n)=2010 \cdot log_3(n^n) = 2010n \cdot log_3n [/math]
- [math] f_2(n)=n^{1+2+ \dots +loglogn} [/math] ezt alulról becsülhetjük [math] f_{2}^{*}(n) = n^{logn} [/math]-nel.
- [math] f_3(n)=4^{100+logn} = 4^{100} \cdot 4^{logn} = 4^{100} \cdot (2^2)^{logn} = 4^{100} \cdot (2^{logn})^2 = 4^{100} \cdot n^2[/math]
- Első lépésben belátjuk, hogy [math] f_1(n)=O(f_3(n)). [/math]
- [math] 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 [/math]
- [math] 2010 \cdot log_3n \leq c \cdot 4^{100} \cdot n [/math]
- [math] log_3n \leq c \cdot \frac{4^{100}}{2010} \cdot n [/math]
- [math] c=\frac{2010}{4^{100}}, n \geq 1 [/math]
- [math] 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 [/math]
- Második lépésben belátjuk, hogy [math] f_1(n)=O( f_{2}^{*}(n)). [/math] (Ha ezt belátjuk, akkor [math] f_1(n)=O( f_{2}(n)) [/math] is igaz lesz.)
- [math] 4^{100} \cdot n^2 \leq c \cdot n^{logn} [/math]
- [math] n^2 \leq \frac{c}{4^{100}} \cdot n^{logn} [/math]
- [math] c = 4^{100} [/math]
- És a kitevők alapján pedig [math] n \geq 4 [/math]
- [math] 4^{100} \cdot n^2 \leq c \cdot n^{logn} [/math]
- Tehát a megoldás [math] f_1(n) \rightarrow f_3(n) \rightarrow f_2(n) .[/math]
2. Feladat
TODO
3. Feladat
TODO
4. Feladat (Van megoldás)
Dijkstra algoritmussal határozza meg a G gráfban az [math]A[/math] pontból az összes többi pontba menő legrövidebb utak hosszát az [math]X[/math] pozitív valós paraméter függvényében. Minden lépésnél írja fel a távolságokat tartalmazó D tömb állapotát, és a KÉSZ halmaz elemeit.
5. Feladat
TODO
6. Feladat (Van megoldás)
Hajtsa végre az alábbi [math]F[/math] bináris keresőfán a BESZÚR(13), TÖRÖL(10) műveleteket! Minden lépést jelezzen!
7. Feladat (Van megoldás)
Egy piros-fekete fa gyökerének mindkét gyereke fekete. A gyökér baloldali részfájában 14, a jobboldali részfájában 63 elemet tárolunk. Mennyi lehet a fa fekete-magassága?
- Először vizsgáljuk a jobboldali részfát:
- Tudjuk, hogy [math] n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 [/math], vagyis a jobb oldali részfa magassága legalább 6.
- Továbbá [math] fm \geq \frac{m}{2} \Rightarrow fm \geq 3 [/math]
- Tudjuk, hogy [math] n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 [/math], vagyis a jobb oldali részfa magassága legalább 6.
- Most nézzük a baloldali részfát:
- Ismert, hogy [math] b_v \geq 2^{fm(v)}-1 \Rightarrow 14 \geq 2^{fm(v)}-1 \Rightarrow fm \leq 3.907 \Rightarrow \Rightarrow fm \lt 4 [/math]
- A 2 korlátot összevetve jön ki, hogy a bal és jobb részfa esetén [math] fm = 3.[/math]
- Emiatt az eredeti fában pedig [math] fm = 4.[/math]
8. Feladat
TODO