„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
Visszavontam Arklur (vita | szerkesztései) szerkesztését (oldid: 167483) |
|||
| 74. sor: | 74. sor: | ||
===5. Feladat=== | ===5. Feladat=== | ||
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? | 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? ''Vizsgán megjegyzést fűztek hozzá: rengetegen odahívták a felügyelőket, hogy márpedig itt el vannak írva a számok, mert semmi nem jön ki. Emiatt hangosan elmondták a felügyelők, hogy jók a számok. Személyes hozzáfűzésem: kell mondani 3 számot, melyek közül 0-át 1-et 2-őt vagy 3-at kiválasztva és ezeket összeadva előállnak ezek a számok: 0, 5, 10, 13, 15, 18. Ezek mondjuk lehetnének az 5, 8 és 10. Viszont ezekkel ellentmondásba keveredhetünk. :-((( ''<br> | ||
{| class="wikitable" border="5" | {| class="wikitable" border="5" | ||
| 125. sor: | 125. sor: | ||
|szöveg= | |szöveg= | ||
todo | |||
<br><br> | |||
}} | }} | ||
| 181. sor: | 171. sor: | ||
|szöveg= | |szöveg= | ||
'''(''Nem kérdezték, csak kieg.'') NP osztály?'''<br><br> | <big>'''(''Nem kérdezték, csak kieg.'') NP osztály?'''<br><br></big> | ||
<br> | <br> | ||
| 197. sor: | 187. sor: | ||
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> | 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> | |||
<br><br> | <br><br> | ||
'''(''Nem kérdezték, csak kieg.'') SAT probléma? '''<br><br> | <big>'''(''Nem kérdezték, csak kieg.'') SAT probléma? '''<br><br></big> | ||
todo <br><br> | todo <br><br> | ||
'''A feladat megoldása: '''<br><br> | <big>'''A feladat megoldása: '''<br><br></big> | ||
todo <br><br> | todo <br><br> | ||