VIK Wiki - Felhasználó közreműködései [hu]

Algoritmuselmélet - Vizsga, 2013.05.30.

2015-06-18T17:22:55Z

Bartos Bence: /* 2. Feladat (Van megoldás) */

{{Vissza|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 <math> F_k </math> mátrix <math> F_k[i,j] </math> eleme?

'''(b)''' Hogyan kell kiszámolni az <math> F_{k-1} </math> mátrixból az <math> F_k </math> 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.)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

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

'''b)''' <math> F_k[i,j]:=min\left \{ F_{k-1}[i,k]+F_{k-1}[k,j],F_{k-1}[i,j]\right \} </math> ''<math>(</math>Vagyis vagy az <math> i \rightarrow k \rightarrow j </math> lesz a legrövidebb út, vagy "marad a régi" <math> i \rightarrow j .)</math>''

'''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 <math> (i \rightarrow j) </math>, vagy ha igen, akkor az a <math> (i \rightarrow k) + (k \rightarrow j) </math> lesz az.

'''d)''' <math> O(n^2) </math>. ''<math>(</math>Maga az algoritmus <math>O(n^3)</math>, de csúcsonként <math> O(n^2) </math>, vagyis <math> n \cdot O(n^2) = O(n^3) ).</math>''
}}

===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!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

'''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. [[File:Algel vizsga 2013tavasz V1 2 2fia.png|300px]]
***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. [[File:Algel_vizsga_2013tavasz_V1_2_3fia.png|400px]]
***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).

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

<math>log_2n+1\leq m \leq log_3n+1</math>, ahol <math>m</math> a fa szintszáma.

$$$ Ez nem pont fordítva van a dián? $$$

''Bizonyítás:''
*<math>log_2n+1\leq m</math>
**Minden belső csúcsnak legalább 2 fia van, így az <math>i.</math> szinten legalább <math>2^{i-1}</math> csúcs van, tehát: <math>2^{m-1} \geq n \Rightarrow m-1 \geq log_2n \Rightarrow m \geq log_2n+1</math>
*<math>m\leq log_3n+1</math>
**Minden belső csúcsnak maximum 3 fia van, így az <math>i.</math> szinten maximum <math>3^{i-1}</math> csúcs van, tehát: <math>3^{m-1} \leq n \Rightarrow m-1 \leq log_3n \Rightarrow m \leq log_3n+1</math>
}}

===3. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===4. Feladat (Van megoldás)===
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]]

}}

===5. Feladat (Van megoldás)===
Egy algoritmus lépésszámáról tudjuk, hogy <math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)</math> és tudjuk azt is, hogy <math> T(1)=T(2)=T(3)=1</math>. Bizonyítsa be, hogy <math> T(n)=O(n^2)</math>.
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

Van olyan <math> c > 0</math> és <math> n_0</math>, hogy <math> n>n_0</math> esetén
<math> 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 </math>
<math> \dots \leq 1+cn^2\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16} \right )^i\right)</math>

Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk: 
<math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</math> 

<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <math> n \geq 1</math> ''(A lényeg, hogy felülről becsüljük!)''

Tehát <math> T(n) = \dots \leq 1+2 \cdot cn^2=O(n^2)</math>

}}

===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 <math>O(n^2)</math> 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).
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*Első lépésben az élsúly legyen a <math> Profit = -(Bevetel - Kiadas) .</math>
*Vegyük fel az összes profitot termelő, vagy legalábbis veszteséget nem termelő éleket <math> (Profit \geq 0 )</math> <math> \Rightarrow O(n^2) </math> 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 <math> O(n^2) </math> 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 <math> O(n^2) </math> időben megmondjuk, hogy mely hajójáratok indításával lesz az évi bevétel a legmagasabb.
}}

===7. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===8. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

[[Kategória:Infoalap]]

Algoritmuselmélet - Vizsga, 2013.06.06.

2015-06-18T14:11:07Z

Bartos Bence: /* 6. Feladat (Van megoldás) */

{{Vissza|Algoritmuselmélet}}

==2013.06.06. vizsga megoldásai==
===1. Feladat (Van megoldás) ===
Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.
* '''(a)''' Adja meg a keresztél definícióját!
* '''(b)''' A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket? ''Vizsgán megjegyzést fűztek hozzá: irányított gráfokra kell gondolni.''
* '''(c)''' Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''a)''' 
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.

'''b)''' 
msz - mélységi szám 
bsz - befejezési szám 
Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél. 
[[Fájl:Algel vizsga 2013tavasz Keresztel 1.png]] 
'''c)''' 
A '''b)''' rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna. 
'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben. 
[[Fájl:Algel vizsga 2013tavasz Keresztel 2.PNG]] 
}}

===2. Feladat (Van megoldás)===
Milyen műveletek vannak a nyitott címzésű hash-elésnél? Hogyan kell megvalósítani a keresést, ha a nyitott címzésű hashelésnél kvadratikus maradék próbát használunk?

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a nyitott címzésű hash-elés?''' 
lásd: [[Hash_tömb]] 

'''Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?''' 
todo 
}}
'''Nyitott címzésű hash-elés műveletei:''' 
Új elem beszúrása, elem keresése, elem törlése. 
A törlés speciális jelzéssel történik. 

'''Keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:''' 
A kvadratikus maradék próba egy álvéletlen próba, ezért másodlagos csomósodáshoz vezethet. 
Legyen M egy 4k + 3 alakú prímszám, ahol k egy pozitív egész. 
Ekkor a próbasorozat legyen 
<math> 0,1^2,(-1)^2, 2^2,(-2)^2,..,\left ( \frac{M-1}{2} \right )^{2}, -\left ( \frac{M-1}{2} \right )^{2} </math>

}}

===3. Feladat (Van megoldás)===
Adja meg az UNIÓ-HOLVAN adatszerkezet definícióját! (A fákkal való implementálást nem kell leírnia.) Mutassa meg, hogy mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban!

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a Kruskal algoritmus?''' 
A Kruskal algoritmust minimális költségű feszítőfák meghatározására használjuk. A piros-kék algoritmus egyik implementációja. 
Lényege, hogy a gráf éleit súlyuk szerint nem csökkenő sorrendbe állítja, majd sorban megpróbálja kékre színezni őket. 
Ennek az a feltétele, hogy az újonnan kékre színezendő él beszínezése után se legyen kör a kékre színezett élek által alkotott gráfban. 
Ha ez mégis kört eredményezne, úgy az él nem kék, hanem piros lesz. 
A kékre színezett élek egy minimális összsúlyú feszítőfát adnak. 
}}
'''UNIÓ-HOLVAN adatszerkezet definíciója: ''' 
Adott egy véges S halmaz, amelynek egy felosztását (partícióját) akarjuk tárolni. 
2 műveletünk van: 

UNIÓ(U, V halmazok, amelyek S részhalmazai): S-ből kivesszük az U-t és a V-t, majd hozzáadjuk (unió) U és V unióját. 

HOLVAN(v pont, v benne van S-ben): Azt az U halmazt adja meg, amelynek v eleme. 

'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:''' 
A Kruskal algoritmus lelke az UNIÓ-HOLVAN adatszerkezet. 
Kezdetben a gráf minden pontja másik <math>U_i</math> részhalmazban van, tehát minden <math>U_i</math> egy pontot tartalmaz. 
Az algoritmus elindul a legkisebb súlyú éleken. 
Az élek két végpontjára (v és w) megvizsgálja, hogy HOLVAN(v) egyenlő-e HOLVAN(w)-vel. 
Ha igen, akkor egy részhalmazban vannak, kört okoznának => piros él lesz. 
Ha nem áll fenn az egyenlőség, akkor a (v,w) kék lesz, a két részhalmazt pedig nyugodtan egyesíthetjük (hozzávehetjük az új élet a kék gráfhoz): 
UNIÓ(<math>U_v</math>,<math>U_w</math>).

}}

===4. Feladat===
Pista bácsi fel akar ugrálni egy n hosszú, fekete illetve fehér fokokból álló csigalépcsőn. Legfeljebb k fokot tud ugrani, de arra vigyáznia kell, hogy páros (>=2) sok foknyi ugrás után páratlan sokat és páratlan sok után mindig páros (>=2) sokat ugorjon. Adjon O(nk) lépésszámú algoritmust, amely megmondja, hogy fel tud-e úgy ugrálni a csigalépcső tetejére, hogy csak egyféle színű lépcsőfokot használ. (A lépcső fokai rendszertelenül vannak színezve, a színezést ismerjük.)
''Vizsgán megjegyzést fűztek hozzá: a talaj és a legteteje nem színes, csak a lépcsők; csak fölfele (előrefele) ugrál, visszafele nem. ''

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

todo

 

}}

===5. Feladat (Van megoldás)===
A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett?

{| class="wikitable" border="5"
|-
!
! 0
! 1
! 2
! 3
! 4
! 5
! 6
! 7
|-
| 1
| 0
| 0
| 0
| 0
| 10
| 10
| 10
| 10
|-
| 2
| 0
| 0
| 5
| 5
| 10
| 10
| 15
| 15
|-
| 3
| 0
| 0
| 5
| 5
| 13
| 13
| 18
| 18
|}

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

Az egyszerűség kedvéért a súly legyen kg, az érték pedig €.

#Az első sor alapján az 1-es csomag értéke €10, súlya 4kg.
#A második sor alapján a 2-es csomag értéke €5, súlya 2kg.
#A 3. lépésben 2 lehetőségünk van, a 3. csomag értéke vagy 13-5=€8, vagy 13-0=€13.
##€8 nem lehet, mert akkor a súlya 2kg lenne, de akkor a [2,3] cellába 8 lenne, nem 5.
##Így csak a €13 jöhet szóba, súlya pedig 4kg, ami jó megoldás lesz.

{{Rejtett
|mutatott=''Avagy kicsit gépiesebb megoldás:''
|szöveg=
 
Jelölje <math> T[s,cs]</math> a táblázat <math>[s,cs]</math> celláját, továbbá <math> V_3</math> a 3. csomag értékét, <math> S_3</math> pedig a súlyát. 
Tudjuk, hogy <math> T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}</math>, ami ebben az esetben: 
<math> T[4,3]=max\left \{ T[4,2];V_3+T[4-S_3,2] \right \} \rightarrow 13=max\left \{ 10;V_3+T[4-S_3,2] \right \}</math>, amiből következik, hogy: 
<math> 13=V_3+T[4-S_3,2] \rightarrow V_3 = 13-T[4-S_3,2]\Rightarrow\Rightarrow S_3=4, V_3=13</math> (Átgondolható, hogy a 3. csomag súlya nem lehet 1,2 vagy 3kg).
}}
Tehát végeredményben a megoldás:
*1-es csomag (€10, 4kg)
*2-es csomag (€5, 2kg)
*3-as csomag (€13, 4kg)

}}

===6. Feladat (Van megoldás)===
Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

<math>A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).</math>
* '''(a)''' Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC. ''Vizsgán megjegyzést fűztek hozzá: az élsúlyok pozitív egész számok, a pozitív szót kifelejtették véletlenül.''
* '''(b)''' Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
[[File:Algel vizsga 2013tavasz V2 6.png]]

'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC
# A fához hozzáadjuk a BE élt.
# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>.
# Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>.

$$$ Észrevétel/kérdés $$$

Nem vagyok nagy algel tudós, de miért ne lehetne y>=1? Tudomásom szerint, a Prim az mindig a legkisebb olyan élt veszi be ami olyan csúcsba visz ami eddig nem volt a halmazba. Ha pedig nincs igazam, akkor meg y>=2 mivel (AE) súlya 2 és akkor azt kellene, (ha csak a sulyok szerint növekvőt nézzük).

$$$$$$

'''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört.

1 súlyú - AB, BE, ED

2 súlyú - AE

3 súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
#Maradtak a BC, EC és DC oldalak.
##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}}

===7. Feladat (Van megoldás)===
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll?

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*'''Tétel:''' Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP
*'''Tétel:''' A SAT probléma NP teljes, tehát része NP-nek.
*A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet.

}}

===8. Feladat===
P-ben van vagy NP-teljes az alábbi eldöntési probléma: 
*'''Input:''' irányítatlan G gráf 
*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető? 

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
Legyen az eldöntési probléma neve A 
G ∈ A akkor, ha G∈3SZÍN vagy G∈H 
Adjunk 3SZÍN < A Karp redukciót, ekkor mivel a 3SZÍN probléma NP-teljes az A is NP-teljes lesz. 

G' legyen az a gráf, amelyet úgy kapunk, hogy G-t kiegészítünk egy 3 csúcsból álló körrel. Mivel G'-ben biztosan nincs Hamilton-út ( Nem összefüggő ), ezért G' ∈ A akkor és csakis akkor, ha G ∈ 3SZÍN
}}

[[Kategória:Infoalap]]

Algoritmuselmélet - Vizsga, 2013.06.06.

2015-06-18T14:10:10Z

Bartos Bence: /* 6. Feladat (Van megoldás) */

{{Vissza|Algoritmuselmélet}}

==2013.06.06. vizsga megoldásai==
===1. Feladat (Van megoldás) ===
Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.
* '''(a)''' Adja meg a keresztél definícióját!
* '''(b)''' A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket? ''Vizsgán megjegyzést fűztek hozzá: irányított gráfokra kell gondolni.''
* '''(c)''' Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''a)''' 
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.

'''b)''' 
msz - mélységi szám 
bsz - befejezési szám 
Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél. 
[[Fájl:Algel vizsga 2013tavasz Keresztel 1.png]] 
'''c)''' 
A '''b)''' rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna. 
'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben. 
[[Fájl:Algel vizsga 2013tavasz Keresztel 2.PNG]] 
}}

===2. Feladat (Van megoldás)===
Milyen műveletek vannak a nyitott címzésű hash-elésnél? Hogyan kell megvalósítani a keresést, ha a nyitott címzésű hashelésnél kvadratikus maradék próbát használunk?

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a nyitott címzésű hash-elés?''' 
lásd: [[Hash_tömb]] 

'''Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?''' 
todo 
}}
'''Nyitott címzésű hash-elés műveletei:''' 
Új elem beszúrása, elem keresése, elem törlése. 
A törlés speciális jelzéssel történik. 

'''Keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:''' 
A kvadratikus maradék próba egy álvéletlen próba, ezért másodlagos csomósodáshoz vezethet. 
Legyen M egy 4k + 3 alakú prímszám, ahol k egy pozitív egész. 
Ekkor a próbasorozat legyen 
<math> 0,1^2,(-1)^2, 2^2,(-2)^2,..,\left ( \frac{M-1}{2} \right )^{2}, -\left ( \frac{M-1}{2} \right )^{2} </math>

}}

===3. Feladat (Van megoldás)===
Adja meg az UNIÓ-HOLVAN adatszerkezet definícióját! (A fákkal való implementálást nem kell leírnia.) Mutassa meg, hogy mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban!

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a Kruskal algoritmus?''' 
A Kruskal algoritmust minimális költségű feszítőfák meghatározására használjuk. A piros-kék algoritmus egyik implementációja. 
Lényege, hogy a gráf éleit súlyuk szerint nem csökkenő sorrendbe állítja, majd sorban megpróbálja kékre színezni őket. 
Ennek az a feltétele, hogy az újonnan kékre színezendő él beszínezése után se legyen kör a kékre színezett élek által alkotott gráfban. 
Ha ez mégis kört eredményezne, úgy az él nem kék, hanem piros lesz. 
A kékre színezett élek egy minimális összsúlyú feszítőfát adnak. 
}}
'''UNIÓ-HOLVAN adatszerkezet definíciója: ''' 
Adott egy véges S halmaz, amelynek egy felosztását (partícióját) akarjuk tárolni. 
2 műveletünk van: 

UNIÓ(U, V halmazok, amelyek S részhalmazai): S-ből kivesszük az U-t és a V-t, majd hozzáadjuk (unió) U és V unióját. 

HOLVAN(v pont, v benne van S-ben): Azt az U halmazt adja meg, amelynek v eleme. 

'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:''' 
A Kruskal algoritmus lelke az UNIÓ-HOLVAN adatszerkezet. 
Kezdetben a gráf minden pontja másik <math>U_i</math> részhalmazban van, tehát minden <math>U_i</math> egy pontot tartalmaz. 
Az algoritmus elindul a legkisebb súlyú éleken. 
Az élek két végpontjára (v és w) megvizsgálja, hogy HOLVAN(v) egyenlő-e HOLVAN(w)-vel. 
Ha igen, akkor egy részhalmazban vannak, kört okoznának => piros él lesz. 
Ha nem áll fenn az egyenlőség, akkor a (v,w) kék lesz, a két részhalmazt pedig nyugodtan egyesíthetjük (hozzávehetjük az új élet a kék gráfhoz): 
UNIÓ(<math>U_v</math>,<math>U_w</math>).

}}

===4. Feladat===
Pista bácsi fel akar ugrálni egy n hosszú, fekete illetve fehér fokokból álló csigalépcsőn. Legfeljebb k fokot tud ugrani, de arra vigyáznia kell, hogy páros (>=2) sok foknyi ugrás után páratlan sokat és páratlan sok után mindig páros (>=2) sokat ugorjon. Adjon O(nk) lépésszámú algoritmust, amely megmondja, hogy fel tud-e úgy ugrálni a csigalépcső tetejére, hogy csak egyféle színű lépcsőfokot használ. (A lépcső fokai rendszertelenül vannak színezve, a színezést ismerjük.)
''Vizsgán megjegyzést fűztek hozzá: a talaj és a legteteje nem színes, csak a lépcsők; csak fölfele (előrefele) ugrál, visszafele nem. ''

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

todo

 

}}

===5. Feladat (Van megoldás)===
A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett?

{| class="wikitable" border="5"
|-
!
! 0
! 1
! 2
! 3
! 4
! 5
! 6
! 7
|-
| 1
| 0
| 0
| 0
| 0
| 10
| 10
| 10
| 10
|-
| 2
| 0
| 0
| 5
| 5
| 10
| 10
| 15
| 15
|-
| 3
| 0
| 0
| 5
| 5
| 13
| 13
| 18
| 18
|}

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

Az egyszerűség kedvéért a súly legyen kg, az érték pedig €.

#Az első sor alapján az 1-es csomag értéke €10, súlya 4kg.
#A második sor alapján a 2-es csomag értéke €5, súlya 2kg.
#A 3. lépésben 2 lehetőségünk van, a 3. csomag értéke vagy 13-5=€8, vagy 13-0=€13.
##€8 nem lehet, mert akkor a súlya 2kg lenne, de akkor a [2,3] cellába 8 lenne, nem 5.
##Így csak a €13 jöhet szóba, súlya pedig 4kg, ami jó megoldás lesz.

{{Rejtett
|mutatott=''Avagy kicsit gépiesebb megoldás:''
|szöveg=
 
Jelölje <math> T[s,cs]</math> a táblázat <math>[s,cs]</math> celláját, továbbá <math> V_3</math> a 3. csomag értékét, <math> S_3</math> pedig a súlyát. 
Tudjuk, hogy <math> T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}</math>, ami ebben az esetben: 
<math> T[4,3]=max\left \{ T[4,2];V_3+T[4-S_3,2] \right \} \rightarrow 13=max\left \{ 10;V_3+T[4-S_3,2] \right \}</math>, amiből következik, hogy: 
<math> 13=V_3+T[4-S_3,2] \rightarrow V_3 = 13-T[4-S_3,2]\Rightarrow\Rightarrow S_3=4, V_3=13</math> (Átgondolható, hogy a 3. csomag súlya nem lehet 1,2 vagy 3kg).
}}
Tehát végeredményben a megoldás:
*1-es csomag (€10, 4kg)
*2-es csomag (€5, 2kg)
*3-as csomag (€13, 4kg)

}}

===6. Feladat (Van megoldás)===
Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

<math>A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).</math>
* '''(a)''' Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC. ''Vizsgán megjegyzést fűztek hozzá: az élsúlyok pozitív egész számok, a pozitív szót kifelejtették véletlenül.''
* '''(b)''' Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
[[File:Algel vizsga 2013tavasz V2 6.png]]

'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC
# A fához hozzáadjuk a BE élt.
# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>.
# Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>.

$$$ Észrevétel/kérdés $$$

Nem vagyok nagy algel tudós, de miért ne lehetne y>=1? Tudomásom szerint, a Prim az mindig a legkisebb olyan élt veszi be ami olyan csúcsba visz ami eddig nem volt a halmazba. Ha pedig nincs igazam, akkor meg y>=2 mivel (AE) súlya 2 és akkor azt kellene, (ha csak a sulyok szerint növekvőt nézzük.

$$$$$$

'''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört.

1 súlyú - AB, BE, ED

2 súlyú - AE

3 súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
#Maradtak a BC, EC és DC oldalak.
##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}}

===7. Feladat (Van megoldás)===
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll?

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

*'''Tétel:''' Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP
*'''Tétel:''' A SAT probléma NP teljes, tehát része NP-nek.
*A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet.

}}

===8. Feladat===
P-ben van vagy NP-teljes az alábbi eldöntési probléma: 
*'''Input:''' irányítatlan G gráf 
*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető? 

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
Legyen az eldöntési probléma neve A 
G ∈ A akkor, ha G∈3SZÍN vagy G∈H 
Adjunk 3SZÍN < A Karp redukciót, ekkor mivel a 3SZÍN probléma NP-teljes az A is NP-teljes lesz. 

G' legyen az a gráf, amelyet úgy kapunk, hogy G-t kiegészítünk egy 3 csúcsból álló körrel. Mivel G'-ben biztosan nincs Hamilton-út ( Nem összefüggő ), ezért G' ∈ A akkor és csakis akkor, ha G ∈ 3SZÍN
}}

[[Kategória:Infoalap]]

Szerkesztővita:Renesans

2014-11-01T16:31:50Z

Bartos Bence: Új oldal, tartalma: „A második feladatnál az XL = gyök(Z^2+R^2) és nem XL = gyök(Z^2-R^2). Rosszul lett rendezve szerintem.”

A második feladatnál az XL = gyök(Z^2+R^2) és nem XL = gyök(Z^2-R^2). Rosszul lett rendezve szerintem.