„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés

A VIK Wikiből
← Régebbi szerkesztésÚjabb szerkesztés →
VizuálisWikiszöveges
Arklur (vitalap | szerkesztései)
381 szerkesztés
Arklur (vitalap | szerkesztései)
381 szerkesztés
6. sor: 6. sor:
|szöveg=
|szöveg=


''[...] Más hibát nem veszek észre benne, én is kb. így oldanám meg. (by Katona Gyula Y.)''
Van olyan <math> c > 0</math> és <math> n_0</math>, hogy <math> n>n_0</math> esetén
''(2 hiba volt benne: egyik, hogy r = 1/16 helyett 1/4 volt, ill. hogy limeszt használtam felső becslés helyett).''
<math> T(n)=T\left(\left \lfloor  \frac{n}{4} \right \rfloor\right)+O(n^2) \leq T\left(\left \lfloor  \frac{n}{4} \right \rfloor\right)+cn^2 \leq T\left(\left \lfloor  \frac{n}{16} \right \rfloor\right)+c\left(n^2+\left(\frac{n^2}{4^2} \right)\right) \leq T\left(\left \lfloor  \frac{n}{64} \right \rfloor\right) + c\left(n^2+\left(\frac{n^2}{4^2} \right)+\left(\frac{n^2}{16^2} \right)\right) \leq \dots </math>
<math> \dots \leq 1+cn^2\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16}  \right )^i\right)</math>


<math> T(n) = T\left(\left \lfloor  \frac{n}{4} \right \rfloor\right) + O(n^2) = T\left(\left \lfloor  \frac{n}{16} \right \rfloor\right) + O\left(\frac{n^2}{16} \right) + O(n^2)=...=1 + O(n^2)\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16}  \right )^i\right)</math><br>
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:<br>
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:<br>
<math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</math><br>
<math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</math><br>
15. sor: 15. sor:
<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <math> n \geq 1</math>
<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <math> n \geq 1</math>


Tehát <math> T(n)=...=1+2 \cdot O(n^2)=O(n^2)</math>
Tehát <math> T(n)=...=1+2 \cdot cn^2=O(n^2)</math>
}}
}}


A lap 2013. június 12., 16:55-kori változata

2013.04.24. PZH megoldásai

1. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy és tudjuk azt is, hogy . Bizonyítsa be, hogy .

Megoldás

Van olyan és , hogy esetén

Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
, ahol , vagyis

ha

Tehát

2. Feladat (Van megoldás)

Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen n darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a legető legnagyobb az összes ilyen csúcs közül.

Megoldás
Megjegyzések a feladathoz
  • Bár nem tartozik a feladathoz, talán érdemes megjegyezzem, hogy bináris kereső fa nem is lehetne, hiszen akkor ott kapásból csak a legalsó szinten lévő elemek lehetnek kupacok (egy 1 elemet tartalmazó kupac), hiszen bináris keresőfánál balra kisebbek, jobbra nagyobbak vannak, míg kupacnál balra és jobbra is nagyobbak vannak.
  • Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága).

Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.

  • Első lépésben a legalsó szinteken lévő csúcsok esetén .
  • Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy az részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).
  • Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát .
    • Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
      • Ha majd a változónkba belerakjuk a csúcsot. Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) fiai magassága, és kupac tulajdonságú lesz.
      • Ha VAGY VAGY VAGY . Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).
Mivel minden csúcsot csak egyszer látogatunk meg, így lépésben megyünk végig a gráfon.

3. Feladat (Van megoldás)

Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha

(a) inorder bejárással kilolvasva a két fát ugyanazt a számsorozatot kapják?

(b) preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?

Megoldás

Mindkét esetben 1-1 ellenpéldát kell szolgáltatni:

  • a)

Fájl:Egyik.png Fájl:Masik.png

Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

  • b)

Fájl:Egyik 1.png Fájl:Masik 2.png

Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

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
A lap eredeti címe: „https://vik.wiki/index.php?title=Algoritmuselmélet_-_PZH,_2013.04.24.&oldid=167962”