Algoritmuselmélet - Vizsga, 2013.05.30.

2013.06.06. vizsga megoldásai

1. Feladat

TODO

Megoldás

TODO

2. Feladat

TODO

Megoldás

TODO

3. Feladat

TODO

Megoldás

TODO

4. Feladat

TODO

Megoldás

TODO

5. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy $T(n)=T\left(\left\lfloor {\frac {n}{4}}\right\rfloor \right)+O(n^{2})$ és tudjuk azt is, hogy $T(1)=T(2)=T(3)=1$. Bizonyítsa be, hogy $T(n)=O(n^{2})$.

Megoldás

$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_{4}n\right\rfloor }\left({\frac {1}{4}}\right)^{i}\right)$
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
$\sum _{i=0}^{k}r^{i}={\frac {1-r^{k+1}}{1-r}}$ ahol $k=\left\lfloor log_{4}n\right\rfloor ,r=0.25$, vagyis ${\frac {1-0.25^{\left\lfloor log_{4}n\right\rfloor +1}}{1-0.25}}$
$\lim _{n\to \infty }{\frac {1-0.25^{\left\lfloor log_{4}n\right\rfloor +1}}{1-0.25}}={\frac {1}{0.75}}$

Tehát $T(n)=...=1+{\frac {1}{0.75}}O(n^{2})=O(n^{2})$

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 $O(n^{2})$ 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).

Megoldás

• 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 $O(n^{2})$ időben el tudjuk végezni.
• Az így kapott G gráfra futtassunk egy Prim-algoritmust, ami $O(n^{2})$ 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 $O(n^{2})$ 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 $3*O(n^{2})$ időt igényel az algoritmus, ami összességben még mindig $O(n^{2})$, tehát az algoritmus jó.

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO