„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés

← Régebbi szerkesztés Újabb szerkesztés →

A lap 2013. június 16., 08:45-kori változata

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

2013.06.06. vizsga megoldásai

1. Feladat

TODO

Megoldás

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!

$l o g_{2} n + 1 \leq m \leq l o g_{3} n + 1$ , ahol $m$ a fa szintszáma.

Bizonyítás:

log2n+1≤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} \geq n \Rightarrow m - 1 \geq l o g_{2} n \Rightarrow m \geq l o g_{2} n + 1$
m≤log3n+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} \leq n \Rightarrow m - 1 \leq l o g_{3} n \Rightarrow m \leq l o g_{3} n + 1$

3. Feladat

TODO

Megoldás

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 (n m)$ 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.)

Megoldás

Hozzunk létre egy $n$ elemű $T N$ 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 (n m)$ .
Hozzunk létre egy $m$ elemű $T M$ 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 (n m)$ .

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] = T N [1]$ majd $N [i, 1] = N [i - 1, 1] + T N [i], i = 2 . . . (n - 1)$ .
- $N [1, 2] = \sum_{i = 2}^{n} T N [i]$ majd $N [i, 2] = N [i - 1, 2] - T N [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] = T M [1]$ majd $M [i, 1] = M [i - 1, 1] + T M [i], i = 2 . . . (m - 1)$ .
- $M [1, 2] = \sum_{i = 2}^{m} T M [i]$ majd $M [i, 2] = M [i - 1, 2] - T M [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 (n m) + O (n m) + O (n) + O (m) + O (n) + O (m) = O (n m)$ lépéssel megoldottuk a feladatot.

5. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy $T (n) = T (⌊ \frac{n}{4} ⌋) + 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 (⌊ \frac{n}{4} ⌋) + O (n^{2}) \leq T (⌊ \frac{n}{4} ⌋) + c n^{2} \leq T (⌊ \frac{n}{16} ⌋) + c (n^{2} + (\frac{n^{2}}{4^{2}})) \leq T (⌊ \frac{n}{64} ⌋) + c (n^{2} + (\frac{n^{2}}{4^{2}}) + (\frac{n^{2}}{1 6^{2}})) \leq \dots$ $\dots \leq 1 + c n^{2} \cdot (\sum_{i = 0}^{⌊ l o g_{4} n ⌋} {(\frac{1}{16})}^{i})$

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 = ⌊ l o g_{4} n ⌋, r = \frac{1}{16}$ , vagyis $\frac{1 - {\frac{1}{16}}^{⌊ l o g_{4} n ⌋ + 1}}{1 - \frac{1}{16}}$

$\frac{1 - {\frac{1}{16}}^{⌊ l o g_{4} n ⌋ + 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 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).

Megoldás

7. Feladat

TODO

Megoldás

8. Feladat

TODO

Megoldás

@@ 52. sor: / 52. sor: @@
 }}
-===4. Feladat===
+===4. Feladat (Van megoldás)===
-TODO
+Van egy tábla <math> (n</math> <big>x</big> <math>m</math> kockákból álló<math> ) </math>. Az <math> A </math> <math> n</math> <big>x</big> <math>m</math>-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 <math> k_1 </math> kocka csoki, és <math> m_1 </math> darab mogyoró van, a másikban pedig <math> k_2 </math> kocka csoki és <math> m_2 </math> darab mogyoró, akkor az igazságtalansági faktor <math> \left | \left ( k_1+m_1 \right ) -(k_2+m_2)\right | </math>. Adjon <math> O(nm) </math> 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 <math> A </math> mátrixból vagy ha összeadást, illetve kivonást hajtunk végre két számon.)
 {{Rejtett
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
+[[File:algel_vizsga1_2013tavasz_4_csoki.PNG|200px]]
+*Hozzunk létre egy <math> n </math> elemű <math> TN </math> tömböt, ahol az <math> i. </math> cellában az szerepel, hogy az <math> A </math> mátrix annyiadik oszlopában mennyi a <math> k+m </math>. ''(ez <math> n*m </math> kiolvasás, és <math> n*(m-1) </math> összeadás, vagyis <math> \Rightarrow O(nm) </math>.
+*Hozzunk létre egy <math> m </math> elemű <math> TM </math> tömböt, ahol az <math> i. </math> cellában az szerepel, hogy az <math> A </math> mátrix annyiadik sorában mennyi a <math> k+m </math>. ''(ez <math> m*n </math> kiolvasás, és <math> m*(n-1) </math> összeadás, vagyis <math> \Rightarrow O(nm) </math>.
+[[File:algel_vizsga1_2013tavasz_4_tn_tm.PNG|200px]]
+*Hozzunk létre egy <math> (n-1) </math> x <math> 2 </math>-es <math> N </math> tömböt, ahol az 1. sorban balról jobbra nézzük, mennyi a <math> k+m </math>, a 2. sorban pedig jobbról balra. ''<math>(</math>1. sor a <math> (k_1+m_1) </math>, 2. sor pedig a hozzá tartozó  <math> (k_2+m_2) .)</math>
+**<math>N[1,1]= TN[1] </math> majd <math>N[i,1]= N[i-1,1]+TN[i] , i=2...(n-1)</math>.
+**<math>N[1,2]= \sum_{i=2}^{n}TN[i] </math> majd <math>N[i,2]= N[i-1,2]-TN[i] , i=2...(n-1)</math>.
+*Hozzunk létre egy <math> (m-1) </math> x <math> 2 </math>-es <math> M </math> tömböt, ahol az 1. sorban fentről lefele nézzük, mennyi a <math> k+m </math>, a 2. sorban pedig alulról felfele. ''<math>(</math>1. sor a <math> (k_1+m_1) </math>, 2. sor pedig a hozzá tartozó <math> (k_2+m_2) .)</math>
+**<math>M[1,1]= TM[1] </math> majd <math>M[i,1]= M[i-1,1]+TM[i] , i=2...(m-1)</math>.
+**<math>M[1,2]= \sum_{i=2}^{m}TM[i] </math> majd <math>M[i,2]= M[i-1,2]-TM[i] , i=2...(m-1)</math>.
+[[File:algel_vizsga1_2013tavasz_4_N_M.PNG|200px]]
+*Az <math> N </math> és <math> M </math> tömbök létrehozása <math> O(n) </math> és <math> O(m) </math> lépést igényel.
+*Nincs is más dolgunk, mint végigmenni az <math> N </math> és <math> M </math> tömbökön úgy, hogy az <math> i. </math> 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 <math> O(n) </math> és <math> O(m) </math> lépés.
+*Összesen tehát <math> O(nm)+O(nm)+O(n)+O(m)+O(n)+O(m)=O(nm) </math> lépéssel megoldottuk a feladatot.
+:::::[[File:algel_vizsga1_2013tavasz_4_1.PNG|400px]]              [[File:algel_vizsga1_2013tavasz_4_2.PNG|400px]]
-TODO
 }}

Bejelentkezés

Keresés

„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés

Névterek

Több

Lapműveletek

A lap 2013. június 16., 08:45-kori változata

Tartalomjegyzék

2013.06.06. vizsga megoldásai

1. Feladat

2. Feladat (Van megoldás)

3. Feladat

4. Feladat (Van megoldás)

5. Feladat (Van megoldás)

6. Feladat

7. Feladat

8. Feladat

Navigáció

Navigáció

Egyetem

Wikieszközök

Wikieszközök

Bejelentkezés

Keresés

„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés

A lap 2013. június 16., 08:45-kori változata

2013.06.06. vizsga megoldásai

1. Feladat

2. Feladat (Van megoldás)

3. Feladat

4. Feladat (Van megoldás)

5. Feladat (Van megoldás)

6. Feladat

7. Feladat

8. Feladat

Navigáció

Wikieszközök

Eszközök

Kategóriák