„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 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? | ||
{| class="wikitable" border="5" | {| class="wikitable" border="5" | ||
| 125. sor: | 125. sor: | ||
|szöveg= | |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. sornál kicsit rafkósnak kell lenni. Leírhatnám egyből a megoldást, de talán több értelme van, ha a logikai zsákutcákat is leírom. | |||
##Először gondolhatnánk arra, hogy a [4,3]-as cella 10+3 formában áll elő, így a 3-as csomag értéke €3. Viszont így a súlyának 0kg-nak kéne lennie, ami nyílván fatal error. | |||
##Második gondolatunk az lehetne, hogy akkor 5+8 formában áll elő, így a 3-as csomag értéke €8. Súlya ekkor 2kg kellene legyen, viszont akkor a [2,3]-as cellába 8-nak, és nem 5-nek kéne szerepelnie, tehát ez se jó megoldás. | |||
##Harmadik ötletnek nagyon más nem jöhet szóba, hogy akkor a 3-as csomag értéke €13, súlya pedig 4kg. És ha leellenőrizzük, látszik, hogy ez lesz a jó megoldás. | |||
Tehát végeredményben a megoldás: | |||
*1-es csomag (€10, 4kg) | |||
*2-es csomag (€5, 2kg) | |||
*3-as csomag (€13, 4kg) | |||
}} | }} | ||
| 171. sor: | 181. sor: | ||
|szöveg= | |szöveg= | ||
'''(''Nem kérdezték, csak kieg.'') NP osztály?'''<br><br> | |||
<br> | <br> | ||
| 187. sor: | 197. 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> | ||
<br><br> | <br><br> | ||
'''(''Nem kérdezték, csak kieg.'') SAT probléma? '''<br><br> | |||
todo <br><br> | todo <br><br> | ||
'''A feladat megoldása: '''<br><br> | |||
todo <br><br> | todo <br><br> | ||