„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
| 75. sor: | 75. sor: | ||
}} | }} | ||
| − | ===6. Feladat | + | ===6. Feladat=== |
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). | 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 | ||
| 81. sor: | 81. sor: | ||
|szöveg= | |szöveg= | ||
| − | + | TODO | |
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
A lap 2013. június 11., 12:50-kori változata
Tartalomjegyzék
2013.06.06. vizsga megoldásai
1. Feladat
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!
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. 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. 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).
- Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy elememet tárol. 300px
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
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}{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]
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 = \frac{1}{16}[/math], vagyis [math]\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}[/math]
[math]\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} \lt 2 ,[/math]ha [math] n \geq 1[/math]
Tehát [math] T(n)=...=1+2 \cdot O(n^2)=O(n^2)[/math]6. Feladat
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).
7. Feladat
TODO
8. Feladat
TODO
