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!

kinyitMegoldá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?

kinyitMegoldás

kinyitKiegé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

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!

kinyitMegoldás

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

Mi az a Kruskal algoritmus?

todo

UNIÓ-HOLVAN adatszerkezet definíciója:

todo

Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:

todo

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.

kinyitMegoldá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

kinyitMegoldá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.

kinyitAvagy 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\{T[s,cs-1];V_i+T[s-S_i,cs-1]\}$, ami ebben az esetben:

$T[4,3]=max\{T[4,2];V_3+T[4-S_3,2]\}\to 13=max\{10;V_3+T[4-S_3,2]\}$, amiből következik, hogy:

$13=V_3+T[4-S_3,2]\to 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!)

kinyitMegoldás

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

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\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?

kinyitMegoldá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ő?
  

kinyitMegoldás

TODO