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

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
50. sor: 50. sor:
  
 
===6. Feladat (Van megoldás)===
 
===6. Feladat (Van megoldás)===
Egy ország ''n'' kis szigetből áll. Szerezné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).
+
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).
 
{{Rejtett
 
{{Rejtett
 
|mutatott=<big>'''Megoldás'''</big>
 
|mutatott=<big>'''Megoldás'''</big>

A lap 2013. június 8., 08:19-kori változata

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 [math] T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + Ο(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].

Megoldás

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

Vagyis [math] T(n)=...=1+\frac{1}{0.75}O(n^2)=O(n^2)[/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).

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

Megoldás
TODO

8. Feladat

TODO

Megoldás
TODO