Algoritmuselmélet - Vizsga, 2013.05.30.

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

2013.06.06. vizsga megoldásai

1. Feladat

Ebben a feladatban a Floyd algoritmussal kapcsolatos kérdésekre kell válaszolnia. (A Floyd-algoritmus egy grában minden pontpárra meghatározza a köztük levő legrövidebb út hosszát.)

(a) Mit jelöl az $F_{k}$ mátrix $F_{k}[i,j]$ eleme?

(b) Hogyan kell kiszámolni az $F_{k-1}$ mátrixból az $F_{k}$ mátrixot?

(c) Igazolja, hogy ez a kiszámítási mód helyes!

(d) Mennyi a lépésszáma a (b) lépés egyszeri végrehajtásának? (A lépésszámot nem kell igazolni.)

Megoldás

a) $F_{k}[i,j]$ azon $i\rightarrow j$ utak legrövidebbjeinek a hosszát tartalmazza, amelyek közbülső pontjai $k$-nál nem nagyobb sorszámúak. (Magyarul: Az $F_{k}[i,j]$ azt mondja meg, hogy $i$-ből $j$-be mennyi a legrövidebb út összsúlya, ha csak az első $k$ darab csúcsot használtuk.)

b) $F_{k}[i,j]:=min\left\{F_{k-1}[i,k]+F_{k-1}[k,j],F_{k-1}[i,j]\right\}$ $($Vagyis vagy az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i \rightarrow k \rightarrow j } lesz a legrövidebb út, vagy "marad a régi" Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i \rightarrow j .)}

c) Tulajdonképpen az előzőből következik. Hiszen vagy nem változik az új csúccsal a legrövidebb út a 2 pont között Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (i \rightarrow j) } , vagy ha igen, akkor az a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (i \rightarrow k) + (k \rightarrow j) } lesz az.

d) Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n^2) } . Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (} Maga az algoritmus Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n^3)} , de csúcsonként Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n^2) } , vagyis Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n \cdot O(n^2) = O(n^3) ).}

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

Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): É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 (Van megoldás)

Van egy tábla Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (n} x Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m} kockákból állóÉrtelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle ) } . Az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle A } Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} x Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k_1 } kocka csoki, és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m_1 } darab mogyoró van, a másikban pedig Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k_2 } kocka csoki és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m_2 } darab mogyoró, akkor az igazságtalansági faktor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \left | \left ( k_1+m_1 \right ) -(k_2+m_2)\right | } . Adjon Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle A } mátrixból vagy ha összeadást, illetve kivonást hajtunk végre két számon.)

Megoldás

• Hozzunk létre egy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n } elemű Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle TN } tömböt, ahol az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i. } cellában az szerepel, hogy az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle A } mátrix annyiadik oszlopában mennyi a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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(\left\lfloor {\frac {n}{4}}\right\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})$.

Megoldás

Van olyan $c>0$ és $n_{0}$, hogy $n>n_{0}$ esetén $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$ $\dots \leq 1+cn^{2}\cdot \left(\sum _{i=0}^{\left\lfloor log_{4}n\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:
$\sum _{i=0}^{k}r^{i}={\frac {1-r^{k+1}}{1-r}}$, ahol $k=\left\lfloor log_{4}n\right\rfloor ,r={\frac {1}{16}}$, vagyis ${\frac {1-{\frac {1}{16}}^{\left\lfloor log_{4}n\right\rfloor +1}}{1-{\frac {1}{16}}}}$

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

Tehát $T(n)=\dots \leq 1+2\cdot cn^{2}=O(n^{2})$

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

• Első lépésben az élsúly legyen a $Profit=-(Bevetel-Kiadas).$
• Vegyük fel az összes profitot termelő, vagy legalábbis veszteséget nem termelő éleket $(Profit\geq 0)$ $\Rightarrow O(n^{2})$ lépés. Ez legyen mondjuk a G gráf.
• Két eshetőség áll fenn:
  • Ha a G gráf összefüggő, akkor jók is vagyunk, nincs további teendőnk, meg is vagyunk.
  • Ha nem összefüggő, akkor:
    • Az egyes komponenseket tekintsük egy pontnak. Minden olyan él, ami ebbe a komponensbe megy, menjen ebbe a pontba. Így kapunk egy F gráfot.
    • Erre az F gráfra hívunk meg egy Prim-algoritmust, ami $O(n^{2})$ időben keres az F gráfban egy minimális feszítőfát (vagyis a komponenseket - ami most jelenleg 1-1 pont a gráfban - a lehető legkisebb költségű élekkel köti össze).

• Tehát Prim-algoritmussal, vagy anélkül $O(n^{2})$ időben megmondjuk, hogy mely hajójáratok indításával lesz az évi bevétel a legmagasabb.

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO