Algoritmuselmélet - Vizsga, 2013.06.06.

← Vissza az előző oldalra – 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!

Megoldás

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 É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 (msz[y] < msz[x]) } é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 (bsz[y] > 0) } , akkor az x → y egy keresztél.
Media: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 É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 (msz[y] < msz[x]) } é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 (bsz[y] > 0) } , 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.

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?

Megoldás

Kiegészítések a feladat megértéséhez

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

É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 0,1^2,(-1)^2, 2^2,(-2)^2,..,\left ( \frac{M-1}{2} \right )^{2}, -\left ( \frac{M-1}{2} \right )^{2} }

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!

Megoldás

Kiegészítések a feladat megértéséhez

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 É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 U_i} részhalmazban van, tehát minden É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 U_i} 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Ó(É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 U_v} ,É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 U_w} ).

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.

Megoldás

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?

	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

Megoldás

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

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

Avagy kicsit gépiesebb megoldás:

Jelölje É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 T[s,cs]} a táblázat É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 [s,cs]} celláját, tová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 V_3} a 3. csomag értéké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 S_3} pedig a súlyát.

Tudjuk, hogy É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 T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}} , ami ebben az esetben:

É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 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 \}} , amiből következik, hogy:

É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 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} (Á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):

É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: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).}

• (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!)

Megoldás

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

1. A fához hozzáadjuk a BE élt.
2. Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így É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 x = 1} . (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy É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 x \le 1} lehetne.)
3. Most az AB élt adjuk hozzá, ez alapján É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 y \ge 1} .
4. Most a BC élt adjuk hozzá, ez alapján É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 y \ge 3} , így végül É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 y \ge 3} .

$$$ É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 É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 y = 3} )

Az összes megoldás:

1. Az 1 súlyú éleket É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! = 6} féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
2. 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).
3. Maradtak a BC, EC és DC oldalak.
   1. Ha É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 y = 3} , akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
   2. Ha É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 y \ge 3} , 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∉NP és X≺SAT egyszerre fennáll?

Megoldás

• 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∉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ő?
  

Megoldás

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