Algoritmuselmélet - Vizsga, 2013.05.30.

← Vissza az előző oldalra – Algoritmuselmélet

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).

Fájl:2 3 pelda.PNG

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

Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle log_2n+1\leq m \leq log_3n+1} , ahol Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m} a fa szintszáma.

Bizonyítás:

• Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle log_2n+1\leq m}
  • Minden belső csúcsnak legalább 2 fia van, így az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} szinten legalább Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2^{i-1}} csúcs van, tehát: Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2^{m-1} \geq n \Rightarrow m-1 \geq log_2n \Rightarrow m \geq log_2n+1}
• Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m\leq log_3n+1}
  • Minden belső csúcsnak maximum 3 fia van, így az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} szinten maximum Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 3^{i-1}} csúcs van, tehát: Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 3^{m-1} \leq n \Rightarrow m-1 \leq log_3n \Rightarrow m \leq log_3n+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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)} és tudjuk azt is, hogy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T(1)=T(2)=T(3)=1} . Bizonyítsa be, hogy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T(n)=O(n^2)} .

Megoldás

Van olyan Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle c > 0} és Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n_0} , hogy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n>n_0} esetén Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T(n)=T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+O(n^2) \leq T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+cn^2 \leq T\left(\left \lfloor \frac{n}{16} \right \rfloor\right)+c\left(n^2+\left(\frac{n^2}{4^2} \right)\right) \leq T\left(\left \lfloor \frac{n}{64} \right \rfloor\right) + c\left(n^2+\left(\frac{n^2}{4^2} \right)+\left(\frac{n^2}{16^2} \right)\right) \leq \dots } Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \dots \leq 1+cn^2\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16} \right )^i\right)}

Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} } , ahol Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}} , vagyis Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}}

Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,} ha Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n \geq 1} (A lényeg, hogy felülről becsüljük!)

Tehát Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T(n) = \dots \leq 1+2 \cdot cn^2=O(n^2)}

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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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

TODO

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO