Algoritmuselmélet - Vizsga, 2013.05.30.

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

2013.06.06. vizsga megoldásai

1. Feladat

TODO

kinyitMegoldá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!

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

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!

$lo{g}_{2}n+1\le m\le lo{g}_{3}n+1$, ahol $m$ a fa szintszáma.

Bizonyítás:

• $lo{g}_{2}n+1\le 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}\ge n\Rightarrow m-1\ge lo{g}_{2}n\Rightarrow m\ge lo{g}_{2}n+1$
• $m\le lo{g}_{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}\le n\Rightarrow m-1\le lo{g}_{3}n\Rightarrow m\le lo{g}_{3}n+1$

3. Feladat

TODO

kinyitMegoldás

TODO

4. Feladat (Van megoldás)

Van egy tábla $(n$ x $m$ kockákból álló$)$. Az $A$ $n$ x $m$-es mátrixban adott, hogy az egyes kockákban hány mogyoró van (a mogyorók nem lógnak át egyik kockából a másikba). Két gyerek akar osztozkodni a csokin, úgy, hogy a csokit kéfelé törik (egyenes vonal mentén, párhuzamosan a tábla valamelyik szélével). Egy osztkozkodás igazságtalansági faktorát a következőképpen kaphatjuk: ha az egyik darabban $k_1$ kocka csoki, és $m_1$ darab mogyoró van, a másikban pedig $k_2$ kocka csoki és $m_2$ darab mogyoró, akkor az igazságtalansági faktor $|(k_1+m_1)-(k_2+m_2)|$. Adjon $O(nm)$ lépést használó algoritmust, ami eldönti, hogy melyik szétosztásnak a legkisebb az igazságtalansági faktora. (Egy lépésnek számít, ha kiolvasunk egy értéket az $A$ mátrixból vagy ha összeadást, illetve kivonást hajtunk végre két számon.)

kinyitMegoldás

• Hozzunk létre egy $n$ elemű $TN$ tömböt, ahol az $i.$ cellában az szerepel, hogy az $A$ mátrix annyiadik oszlopában mennyi a $k+m$. (ez $n*m$ kiolvasás, és $n*(m-1)$ összeadás, vagyis $\Rightarrow O(nm)$.
• Hozzunk létre egy $m$ elemű $TM$ tömböt, ahol az $i.$ cellában az szerepel, hogy az $A$ mátrix annyiadik sorában mennyi a $k+m$. (ez $m*n$ kiolvasás, és $m*(n-1)$ összeadás, vagyis $\Rightarrow O(nm)$.

• Hozzunk létre egy $(n-1)$ x $2$-es $N$ tömböt, ahol az 1. sorban balról jobbra nézzük, mennyi a $k+m$, a 2. sorban pedig jobbról balra. $($1. sor a $(k_1+m_1)$, 2. sor pedig a hozzá tartozó $(k_2+m_2).)$
  • $N[1,1]=TN[1]$ majd $N[i,1]=N[i-1,1]+TN[i],i=2...(n-1)$.
  • $N[1,2]=\sum _{i=2}^{n}TN[i]$ majd $N[i,2]=N[i-1,2]-TN[i],i=2...(n-1)$.
• Hozzunk létre egy $(m-1)$ x $2$-es $M$ tömböt, ahol az 1. sorban fentről lefele nézzük, mennyi a $k+m$, a 2. sorban pedig alulról felfele. $($1. sor a $(k_1+m_1)$, 2. sor pedig a hozzá tartozó $(k_2+m_2).)$
  • $M[1,1]=TM[1]$ majd $M[i,1]=M[i-1,1]+TM[i],i=2...(m-1)$.
  • $M[1,2]=\sum _{i=2}^{m}TM[i]$ majd $M[i,2]=M[i-1,2]-TM[i],i=2...(m-1)$.

• Az $N$ és $M$ tömbök létrehozása $O(n)$ és $O(m)$ lépést igényel.
• Nincs is más dolgunk, mint végigmenni az $N$ és $M$ tömbökön úgy, hogy az $i.$ oszlopban vesszük a 2 szám különbségének abszolút értékét, vagyis az igazságtalansági faktort számoljuk, és mindig elmentjók egy változóba a minimumot, és a ehhez tartozó törésvonalat. Ez is $O(n)$ és $O(m)$ lépés.
• Összesen tehát $O(nm)+O(nm)+O(n)+O(m)+O(n)+O(m)=O(nm)$ lépéssel megoldottuk a feladatot.

5. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy $T(n)=T\left(\lfloor \frac{n}{4}\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)$.

kinyitMegoldás

Van olyan $c>0$ és $n_0$, hogy $n>n_0$ esetén $T(n)=T\left(\lfloor \frac{n}{4}\rfloor \right)+O(n^2)\le T\left(\lfloor \frac{n}{4}\rfloor \right)+c{n}^2\le T\left(\lfloor \frac{n}{16}\rfloor \right)+c(n^2+\left(\frac{n^2}{4^2}\right))\le T\left(\lfloor \frac{n}{64}\rfloor \right)+c(n^2+\left(\frac{n^2}{4^2}\right)+\left(\frac{n^2}{16^2}\right))\le \dots$ $\dots \le 1+c{n}^2\cdot \left(\sum _{i=0}^{\lfloor lo{g}_{4}n\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:
$\sum _{i=0}^k{r}^i=\frac{1-r^{k+1}}{1-r}$, ahol $k=\lfloor lo{g}_{4}n\rfloor ,r=\frac{1}{16}$, vagyis $\frac{1-{\frac{1}{16}}^{\lfloor lo{g}_{4}n\rfloor +1}}{1-\frac{1}{16}}$

$\frac{1-{\frac{1}{16}}^{\lfloor lo{g}_{4}n\rfloor +1}}{1-\frac{1}{16}}<2,$ha $n\ge 1$ (A lényeg, hogy felülről becsüljük!)

Tehát $T(n)=\dots \le 1+2\cdot c{n}^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 $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).

kinyitMegoldás

TODO

7. Feladat

TODO

kinyitMegoldás

TODO

8. Feladat

TODO

kinyitMegoldás

TODO