Algoritmuselmélet - Vizsga, 2013.06.06. forrásának megtekintése

==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!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''a)'''<br>
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)'''<br>
msz - mélységi 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>
[[Fájl:keresztel_1.png]]<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>
'''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>
}}

===2. Feladat===
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? 

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a nyitott címzésű hash-elés?'''<br><br>
todo <br><br>

'''(Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?'''<br><br>
todo <br><br>
}}
'''Nyitott címzésű hash-elés műveletei:'''<br><br>
todo <br><br>

'''Keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:'''<br><br>
todo <br><br>

}}

===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! 

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a Kruskal algoritmus?'''<br>
todo <br><br>
}}
'''UNIÓ-HOLVAN adatszerkezet definíciója: '''<br><br>
todo <br><br>

'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:'''<br>
todo <br><br>

}}

===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. ''

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

todo

<br><br>

}}

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

{| class="wikitable" border="5"
|-
! 
! 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 
|}

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

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, ami jó megoldás lesz.


''Avagy kicsit gépiesebb megoldás:''<br><br>
Jelölje <math> T[s,cs]</math> a táblázat <math>[s,cs]</math> celláját, továbbá <math> V_3</math> a 3. csomag értékét, <math> S_3</math> pedig a súlyát.<br><br>
Tudjuk, hogy <math> T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}</math>, ami ebben az esetben:<br><br>
<math> 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 \}</math>, amiből következik, hogy:<br><br>
<math> 13=V_3+T[4-S_3,2] \rightarrow V_3 = 13-T[4-S_3,2]\Rightarrow\Rightarrow S_3=4, V_3=13</math> (Á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):

<math>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).</math>
* '''(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!)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
[[File: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
# A fához hozzáadjuk a BE élt.
# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
# 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>.

'''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 <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> 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 <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
##Ha <math>y \ge 3</math>, 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===
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll? 

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|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 (jelenleg) nem 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>
todo <br><br>
}}

<big>'''A feladat megoldása: '''<br><br></big>
todo <br><br>

}}

===8. Feladat===
P-ben van vagy NP-teljes az alábbi eldöntési probléma:<br>
*'''Input:''' irányítatlan G gráf<br>
*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető?<br> 

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéshez'''</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 (jelenleg) nem 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>'''(''Nem kérdezték, csak kieg.'') 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>
todo <br><br>

}}