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

(82 közbenső módosítás, amit 8 másik szerkesztő végzett, nincs mutatva)

1. sor:

==2013.06.06. vizsga megoldásai==

===1. Feladat===

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

* '''(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?

* '''(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!

* '''(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)'''

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

'''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~~:~~keresztel_1~~.png]]

[[Media:Algel vizsga 2013tavasz Keresztel 1.png]]

'''(c)'''

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

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.

'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.

[[~~Fájl~~:~~keresztel_2~~.PNG]]

[[Media: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>

}}

===2. Feladat===

~~TODO~~

===3. Feladat (Van megoldás)===

===3. ~~Feladat==~~=

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!

~~TODO~~

{{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===

~~TODO~~

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

===5. Feladat===

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

~~TODO~~

===6. Feladat===

{{Rejtett

~~TODO~~

|mutatott=<big>'''Megoldás'''</big>

===7. Feladat===

|szöveg=

~~TODO~~

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

| 10

|-

| 2

| 0

| 5

| 10

| 15

|-

| 3

| 0

| 5

| 13

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

* '''(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=

[[Media: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===

~~TODO~~

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

@@ 1. sor: / 1. sor: @@
+{{Vissza|Algoritmuselmélet}}
 ==2013.06.06. vizsga megoldásai==
-===1. Feladat===
+===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!
+* '''(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?
+* '''(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!
+* '''(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)'''<br>
+'''a)'''<br>
 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)'''<br>
+'''b)'''<br>
 msz - mélységi szám<br>
 bsz - befejezési szám<br>
 Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x →  y egy keresztél.<br>
-[[Fájl:keresztel_1.png]]<br>
+[[Media:Algel vizsga 2013tavasz Keresztel 1.png]]<br>
-'''(c)'''<br>
+'''c)'''<br>
-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.
+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.<br>
-Másképpen mondva: Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.<br>
+'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.<br>
-[[Fájl:keresztel_2.PNG]]<br>
+[[Media:Algel vizsga 2013tavasz Keresztel 2.PNG]]<br>
+}}
+===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?'''<br><br>
+lásd: [[Hash_tömb]] <br><br>
+'''Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?'''<br><br>
+todo <br><br>
+}}
+'''Nyitott címzésű hash-elés műveletei:'''<br><br>
+Új elem beszúrása, elem keresése, elem törlése.<br>
+A törlés speciális jelzéssel történik.<br><br>
+'''Keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:'''<br><br>
+A kvadratikus maradék próba egy álvéletlen próba, ezért másodlagos csomósodáshoz vezethet.<br>
+Legyen M egy 4k + 3 alakú prímszám, ahol k egy pozitív egész.<br>
+Ekkor a próbasorozat legyen<br>
+<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>
 }}
-===2. Feladat===
-TODO
+===3. Feladat (Van megoldás)===
-===3. Feladat===
+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!
-TODO
+{{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?'''<br>
+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. <br>
+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. <br>
+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. <br>
+Ha ez mégis kört eredményezne, úgy az él nem kék, hanem piros lesz.<br>
+A kékre színezett élek egy minimális összsúlyú feszítőfát adnak.<br><br>
+}}
+'''UNIÓ-HOLVAN adatszerkezet definíciója: '''<br><br>
+Adott egy véges S halmaz, amelynek egy felosztását (partícióját) akarjuk tárolni. <br>
+műveletünk van:<br>
+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. <br><br>
+HOLVAN(v pont, v benne van S-ben): Azt az U halmazt adja meg, amelynek v eleme.<br><br>
+'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:'''<br>
+A Kruskal algoritmus lelke az UNIÓ-HOLVAN adatszerkezet. <br>
+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.<br>
+Az algoritmus elindul a legkisebb súlyú éleken. <br>
+Az élek két végpontjára (v és w) megvizsgálja, hogy HOLVAN(v) egyenlő-e HOLVAN(w)-vel. <br>
+Ha igen, akkor egy részhalmazban vannak, kört okoznának => piros él lesz.<br>
+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):<br>
+UNIÓ(<math>U_v</math>,<math>U_w</math>).
+}}
 ===4. Feladat===
-TODO
+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.)
-===5. Feladat===
+''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. ''
-TODO
-===6. Feladat===
+{{Rejtett
-TODO
+|mutatott=<big>'''Megoldás'''</big>
-===7. Feladat===
+|szöveg=
-TODO
+todo
+<br><br>
+}}
+===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=
+<br>
+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.<br><br>
+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:<br><br>
+<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:<br><br>
+<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=
+[[Media: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.
+súlyú - AB, BE, ED
+súlyú - AE
+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===
-TODO
+P-ben van vagy NP-teljes az alábbi eldöntési probléma:<br>
+*'''Input:''' irányítatlan G gráf<br>
+*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető?<br>
+{{Rejtett
+|mutatott=<big>'''Megoldás'''</big>
+|szöveg=
+Legyen az eldöntési probléma neve A<br>
+G ∈ A akkor, ha G∈3SZÍN vagy G∈H<br>
+Adjunk 3SZÍN < A  Karp redukciót, ekkor mivel a 3SZÍN probléma NP-teljes az A is NP-teljes lesz.<br><br>
+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]]