„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
a autoedit v2: fájlhivatkozások egységesítése, az új közvetlenül az adott fájlra mutat |
||
| (4 közbenső módosítás, amit 3 másik szerkesztő végzett, nincs mutatva) | |||
| 17. 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> | ||
}} | }} | ||
| 53. 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! | ||
| 65. 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>). | |||
}} | }} | ||
| 172. 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 | ||
| 179. 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. | ||
| 217. 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]] | [[Kategória:Infoalap]] | ||