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

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 $(msz[y]<msz[x])$ és $(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.

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

$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 $U_{i}$ részhalmazban van, tehát minden $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Ó($U_{v}$,$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 $T[s,cs]$ a táblázat $[s,cs]$ celláját, továbbá $V_{3}$ a 3. csomag értékét, $S_{3}$ pedig a súlyát.

Tudjuk, hogy $T[s,cs]=max\left\{T[s,cs-1];V_{i}+T[s-S_{i},cs-1]\right\}$, ami ebben az esetben:

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

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

$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

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 $x=1$. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy $x\leq 1$ lehetne.)
3. Most az AB élt adjuk hozzá, ez alapján $y\geq 1$.
4. Most a BC élt adjuk hozzá, ez alapján $y\geq 3$, így végül $y\geq 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 $y=3$)

Az összes megoldás:

1. Az 1 súlyú éleket $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 $y=3$, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
   2. Ha $y\geq 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