Algoritmuselmélet - Vizsga, 2013.06.06.
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!
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.
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.
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?
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?
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
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!
Mi az a Kruskal algoritmus?
UNIÓ-HOLVAN adatszerkezet definíciója:
todo
Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:
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.
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 |
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.
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:
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!)
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 É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.)
- 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} .
- 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} .
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:
- 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).
- 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 É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.
- 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?
- 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ő?
