Algoritmuselmélet - Vizsga, 2013.05.30. forrásának megtekintése

==2013.06.06. vizsga megoldásai==
===1. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

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!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

'''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. [[File:2_3_2.png|300px]]
***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. [[File:2_3_3.png|400px]]
***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). 
:::::::::::::::::[[File:2_3_pelda.PNG|400px]]

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

<math>log_2n+1\leq m \leq log_3n+1</math>, ahol <math>m</math> a fa szintszáma.

''Bizonyítás:''
*<math>log_2n+1\leq m</math>
**Minden belső csúcsnak legalább 2 fia van, így az <math>i.</math> szinten legalább <math>2^{i-1}</math> csúcs van, tehát: <math>2^{m-1} \geq n \Rightarrow m-1 \geq log_2n \Rightarrow m \geq log_2n+1</math>
*<math>m\leq log_3n+1</math>
**Minden belső csúcsnak maximum 3 fia van, így az <math>i.</math> szinten maximum <math>3^{i-1}</math> csúcs van, tehát: <math>3^{m-1} \leq n \Rightarrow m-1 \leq log_3n \Rightarrow m \leq log_3n+1</math>
}}

===3. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===4. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

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>.
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

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

}}

===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).
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*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
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===8. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}