„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
| 37. sor: | 37. sor: | ||
===5. Feladat (Van megoldás)=== | ===5. Feladat (Van megoldás)=== | ||
| − | Egy algoritmus lépésszámáról tudjuk, hogy <math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + | + | Egy algoritmus lépésszámáról tudjuk, hogy <math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)</math> és tudjuk azt is, hogy <math> T(1)=T(2)=T(3)=1</math>. Bizonyítsa be, hogy <math> T(n)=O(n^2)</math>. |
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
A lap 2013. június 8., 06:19-kori változata
Tartalomjegyzék
2013.06.06. vizsga megoldásai
1. Feladat
TODO
2. Feladat
TODO
3. Feladat
TODO
4. Feladat
TODO
5. Feladat (Van megoldás)
Egy algoritmus lépésszámáról tudjuk, hogy [math] T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)[/math] és tudjuk azt is, hogy [math] T(1)=T(2)=T(3)=1[/math]. Bizonyítsa be, hogy [math] T(n)=O(n^2)[/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}{4} \right) + O(n^2)=...=1 + O(n^2)*\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{4} \right )^i\right)[/math]
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
[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 = 0.25[/math], vagyis [math]\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25}[/math]
[math] \lim_{n \to \infty}\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25} = \frac{1}{0.75}[/math]
6. Feladat (Van megoldás)
Egy ország n kis szigetből áll. Szeretnénk néhány hajójáratot indítani a szigetek között úgy, hogy bárhonnan bárhova el lehessen jutni (esetleg átszállással). Ehhez ismerjük bármely két szigetre, hogy mennyibe kerül egy évben a hajójárat fenntartása közöttük, illetve azt, hogy mekkora az itt várható éves bevétel. Adjon algoritmust, ami ezen adatok ismeretében [math]O(n^2)[/math] időben meghatározza, hogy hol indítsuk el a hajójáratokat, ha a lehető legnagyobb várható éves hasznot (vagy a lehető legkisebb veszteséget) szeretnénk elérni. (Egy szigeten egy hajóállomás van csak).
- Az élek súlya legyen a "Veszteség" = Fenntartás - Bevétel (Így a súly minél kisebb, annál nagyobb a Profitunk). Ezt [math]O(n^2)[/math] időben el tudjuk végezni.
- Az így kapott G gráfra futtassunk egy Prim-algoritmust, ami [math]O(n^2)[/math] időben keres nekünk egy minimális feszítőfát, ez legyen F. Ez azért jó, mert így bármelyik szigetről bármelyik szigetre eltudunk jutni a lehető legnagyobb profittal bíró útvonalakon.
- Mivel a cél a profitmaximalizálás, így minden olyan élt, aminek nem pozitív a súlya (tehát profitot termel, vagy legalábbis nincs rajta veszteségünk), felvesszük a F gráfhoz, ez legyen az M gráf. Ez is [math]O(n^2)[/math] időt vesz igénybe.
- Az M gráfról elmondhatjuk, hogy bármelyik szigetről bármelyik szigetre el tudunk jutni, és a hajóhálózat a legnagyobb profittal rendelkezik.
- Tulajdonképpen [math]3*O(n^2)[/math] időt igényel az algoritmus, ami összességben még mindig [math]O(n^2)[/math], tehát az algoritmus jó.
7. Feladat
TODO
8. Feladat
TODO
