Algoritmuselmélet - Vizsga, 2013.05.30.
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 kulcsot (S) tárolunk.
- Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot 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 kulcsot 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).
- Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. Fájl:2 3 2.png
Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!
, ahol a fa szintszáma.
Bizonyítás:
-
- Minden belső csúcsnak legalább 2 fia van, így az szinten legalább csúcs van, tehát:
-
- Minden belső csúcsnak maximum 3 fia van, így az szinten maximum csúcs van, tehát:
3. Feladat
TODO
4. Feladat
TODO
5. Feladat (Van megoldás)
Egy algoritmus lépésszámáról tudjuk, hogy és tudjuk azt is, hogy . Bizonyítsa be, hogy .
Van olyan és , hogy esetén
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
, ahol , vagyis
ha (A lényeg, hogy felülről becsüljük!)
Tehát6. 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 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