Algoritmuselmélet 2010.11.19. PZH megoldásai
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