Algoritmuselmélet - Vizsga, 2013.05.30.

2013.06.06. vizsga megoldásai

1. Feladat

TODO

Megoldás

TODO

2. Feladat (Van megoldás)

Adja meg a 2-3 fa definícióját! Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!

Megoldás

Adja meg a 2-3 fa definícióját!

• Elemeket csak a levelekben tárolunk.
• Az elemek balról jobbra növekvő sorrendben állnak.
• Minden belső csúcsnak 2, vagy 3 fia lehet, se több, se kevesebb. (Kivéve, ha csak 1 elemet tárolunk a fában, mert akkor a gyökérnek csak 1 fia van.)
• A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).
• A belső csúcsokban mutatókat (M) és 1, vagy 2 elemet (S) tárolunk.
  • Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy elememet tárol. Fájl:2 3 2.png
    • A bal részfában az elemek kisebbek, mint S1.
    • A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).
  • Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 elemet tárol. Fájl:2 3 3.png
    • A bal részfában az elemek kisebbek, mint S1.
    • A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.
    • A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).

Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!

$log_{2}n+1\leq m\leq log_{3}n+1$, ahol $m$ a fa szintszáma.

Bizonyítás:

• $log_{2}n+1\leq m$
  • Minden belső csúcsnak legalább 2 fia van, így az $i.$ szinten legalább $2^{i-1}$ csúcs van, tehát: $2^{m-1}\geq n\Rightarrow m-1\geq log_{2}n\Rightarrow m\geq log_{2}n+1$
• $m\leq log_{3}n+1$
  • Minden belső csúcsnak maximum 3 fia van, így az $i.$ szinten maximum $3^{i-1}$ csúcs van, tehát: $3^{m-1}\leq n\Rightarrow m-1\leq log_{3}n\Rightarrow m\leq log_{3}n+1$

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