„Algoritmuselmélet 2010.11.19. PZH megoldásai” változatai közötti eltérés

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
 
(4 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)===
−
TODO
+
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=
  
−
TODO
+
*<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>
 
}}
 
}}
  
57. sor: 78. sor:
 
}}
 
}}
  
−
===6. Feladat===
+
===6. Feladat (Van megoldás)===
−
TODO
+
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!
 +
 
 +
[[File:algel_pzh_2010osz_6_f.PNG|200px]]
 
{{Rejtett
 
{{Rejtett
 
|mutatott=<big>'''Megoldás'''</big>
 
|mutatott=<big>'''Megoldás'''</big>
 
|szöveg=
 
|szöveg=
  
−
TODO
+
*BESZÚR(13):
 +
**Egyszerű, mint az 1x1<br>
 +
[[File:algel_pzh_2010osz_6_1.png|300px]]
 +
 
 +
*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).<br>
 +
[[File:algel_pzh_2010osz_6_2.png|300px]]
 +
 
 
}}
 
}}
  
−
===7. Feladat===
+
===7. Feladat (Van megoldás)===
−
TODO
+
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?
 
{{Rejtett
 
{{Rejtett
 
|mutatott=<big>'''Megoldás'''</big>
 
|mutatott=<big>'''Megoldás'''</big>
 
|szöveg=
 
|szöveg=
  
−
TODO
+
*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.<br><br>
 +
**Továbbá <math> fm \geq \frac{m}{2} \Rightarrow fm \geq 3 </math> <br><br>
 +
*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 < 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>
 
}}
 
}}
  

A lap jelenlegi, 2014. április 22., 20:19-kori változata

← 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.

Algel pzh 2010osz 4 f.PNG

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.
Algel pzh 2010osz 4 2.PNGAlgel pzh 2010osz 4 3.PNGAlgel pzh 2010osz 4 1.png

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!

Algel pzh 2010osz 6 f.PNG

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

Algel pzh 2010osz 6 1.png

  • 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).
Algel pzh 2010osz 6 2.png

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
A lap eredeti címe: „https://wiki.sch.bme.hu/index.php?title=Algoritmuselmélet_2010.11.19._PZH_megoldásai&oldid=180559”