Algoritmuselmélet 2010.11.19. PZH megoldásai

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

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]
  
  

Megoldás

• [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]
    
    

• 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]
    
    

• Tehát a megoldás [math] f_1(n) \rightarrow f_3(n) \rightarrow f_2(n) .[/math]

2. Feladat

TODO

Megoldás

TODO

3. Feladat

TODO

Megoldás

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.

Megoldás

• Egy egyszerű Dijkstra-s feladat.
• Annyit kell megjegyezni hozzá, hogy:
  • Ha [math] X \leq 2 [/math], akkor az [math]X[/math] élt [math]( D \rightarrow E )[/math] veszi be.
  • Ha [math] X \geq 2 [/math], akkor a [math]C \rightarrow E [/math] élt veszi be.

5. Feladat

TODO

Megoldás

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!

Megoldás

• BESZÚR(13):
  • Egyszerű, mint az 1x1
    

• TÖRÖL(10):
  • Töröljük a 10-t.
  • A BAL oldali részfából kiválasztjuk a LEGNAGYOBB elemet, és berakjuk a gyökérbe (ebben az esetben a 7).
  • A fát rendbe rakjuk (ez esetben a 6-t beírjuk a 7 régi helyére).
    

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?

Megoldás

• 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]
    
    
• 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

Megoldás

TODO