|
|
| (10 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> |
| [[Fájl:keresztel_1.png]]<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> |
| [[Fájl:keresztel_2.PNG]]<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> |
| todo <br><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> |
| todo <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> |
| todo <br><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= |
| [[File:2013_06_06_V2_6.png]] | | [[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= |
|
| |
|
| {{Rejtett
| | *'''Tétel:''' Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP |
| |mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
| | *'''Tétel:''' A SAT probléma NP teljes, tehát része NP-nek. |
| |szöveg=
| | *A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet. |
| <big>'''Eldöntési probléma osztályok? '''<br><br></big>
| |
| | |
| <br>
| |
| [[File:bonyolultsag_elmelet.JPG|390px]]
| |
| <br>
| |
| | |
| A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. <br><br>
| |
| | |
| Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik.<br><br>
| |
| | |
| A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. <br><br>
| |
| | |
| Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre nem feltétlenül ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') <br><br>
| |
| | |
| A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). <br><br>
| |
| | |
| Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). <br><br>
| |
| | |
| Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. <br><br>
| |
| | |
| <big>'''Karp-redukció?'''<br><br></big>
| |
| Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. <br><br>
| |
| | |
| Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. <br><br>
| |
| | |
| Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen.<br><br>
| |
| | |
| <big>'''SAT probléma? '''<br><br></big>
| |
| A SAT probléma NP-teljes.<br>
| |
| forrás:http://www.cs.bme.hu/algel/12elo-2012.pdf<br>
| |
| }}
| |
| | |
| <big>'''A feladat megoldása: '''<br><br></big>
| |
| Tétel: Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP<br>
| |
| Tétel: A SAT probléma NP teljes, tehát része NP-nek.<br> | |
| 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> |
|
| |
|
| {{Rejtett
| | 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 |
| |mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
| |
| |szöveg=
| |
| <big>'''Eldöntési probléma osztályok? '''<br><br></big>
| |
| | |
| <br>
| |
| [[File:bonyolultsag_elmelet.JPG|390px]]
| |
| <br>
| |
| | |
| A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. <br><br>
| |
| | |
| Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik.<br><br>
| |
| | |
| A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. <br><br>
| |
| | |
| Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre nem feltétlenül ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') <br><br>
| |
| | |
| A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). <br><br>
| |
| | |
| Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). <br><br>
| |
| | |
| Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. <br><br>
| |
| | |
| <big>'''Karp-redukció?'''<br><br></big>
| |
| Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. <br><br>
| |
| | |
| Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. <br><br>
| |
| | |
| Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen.<br><br>
| |
| | |
| <big>'''H-út? '''<br><br></big>
| |
| todo <br><br>
| |
| | |
| <big>'''3 színnel színezhetőség problémája? '''<br><br></big>
| |
| todo <br><br>
| |
| }} | | }} |
|
| |
|
| <big>'''A feladat megoldása: '''<br><br></big>
| | [[Kategória:Infoalap]] |
| todo <br><br>
| |
| | |
| }}
| |