„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
a Hryghr átnevezte a(z) Algoritmuselmélet 2013.06.06. vizsga megoldásai lapot a következő névre: Algoritmuselmélet - Vizsga, 2013.06.06. |
a autoedit v2: fájlhivatkozások egységesítése, az új közvetlenül az adott fájlra mutat |
||
(9 közbenső módosítás, amit 6 másik szerkesztő végzett, nincs mutatva) | |||
1. sor: | 1. sor: | ||
{{Vissza|Algoritmuselmélet}} | |||
==2013.06.06. vizsga megoldásai== | ==2013.06.06. vizsga megoldásai== | ||
===1. Feladat (Van megoldás) === | ===1. Feladat (Van megoldás) === | ||
15. sor: | 17. sor: | ||
bsz - befejezési 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> | Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél.<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.<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.<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> | ||
[[ | [[Media:Algel vizsga 2013tavasz Keresztel 2.PNG]]<br> | ||
}} | }} | ||
51. sor: | 53. sor: | ||
}} | }} | ||
===3. Feladat=== | ===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! | 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! | ||
63. sor: | 65. sor: | ||
'''Mi az a Kruskal algoritmus?'''<br> | '''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> | '''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> | |||
2 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> | '''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>). | |||
}} | }} | ||
170. sor: | 187. sor: | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |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)''' 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 | ||
177. sor: | 194. sor: | ||
# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>. | # 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>. | # 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. | '''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. | ||
201. sor: | 224. sor: | ||
|szöveg= | |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. | |||
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. | |||
}} | }} | ||
251. sor: | 238. sor: | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |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]] | |||
A lap jelenlegi, 2017. július 12., 15:49-kori változata
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!
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?
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!
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.
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 |
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!)
7. Feladat (Van megoldás)
Létezik-e olyan X eldöntési probléma, amire X∉NP és X≺SAT egyszerre fennáll?
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ő?