od eis » 8. 6. 2011 17:51
Verze H
1) Ukaz, ze mnozina S = {e | |We | >= e + 1} je RS. Alg overujuci pre dane e, ci patri do S staci popisat neformalne.
2) Ukaz, ze K <=1 S
3) Ukaz, ze existuje PRF f(z) pre ktoru plati: Fif(z)(x) = xz
4) Mas black-box, co vie odpovedat, ci je mozne vyriesit danu instanciu LOUP v konstantnom case. Popis polynom. alg, ktory najde rozdelenie mnoziny prvkov na na polovice s rovnakou velkostou.
5) Najvacsi spolocny podgraf, dokaz, ze je NP-uply.
cca Riesenia:
1) We | >= e + 1 prepisat na existuje y : Fie(y) konverguje a pocet takych y je aspon e+ 1. To znamena, ze existuje s, take, ze Fie,s(y) konverguje. + pocitadlo, ze ich mam uz aspon e+1. veta => existuje a PRP => S je RS
2) vid dokaz Riceovej vety
3) s-m-n veta s11 (e,z) a 3 for cykly, ktore pre pevny parameter z a dane x ( nepotrebujes while ) spocitaju xz
4) cca Hlavna mnozina A, vytvorim A' a B. A' = A[0], B=A-A'. postupne pre kazdy vrchol v z B zistim, ci B-v (black-box) ma riesenie, ak ano, tak v z B odoberiem a pridam do A. cca
5) vid minule pisomky. Z HK, G1 = G, G2 = kruznica nad |V| vrcholmi
snad niekomu pomoze, vela stastia !
Verze H
1) Ukaz, ze mnozina S = {e | |W[sub]e[/sub] | >= e + 1} je RS. Alg overujuci pre dane e, ci patri do S staci popisat neformalne.
2) Ukaz, ze K <=[sub]1[/sub] S
3) Ukaz, ze existuje PRF f(z) pre ktoru plati: Fi[sub]f(z)[/sub](x) = x[sup]z[/sup]
4) Mas black-box, co vie odpovedat, ci je mozne vyriesit danu instanciu LOUP v konstantnom case. Popis polynom. alg, ktory najde rozdelenie mnoziny prvkov na na polovice s rovnakou velkostou.
5) Najvacsi spolocny podgraf, dokaz, ze je NP-uply.
cca Riesenia:
1) W[sub]e[/sub] | >= e + 1 prepisat na existuje y : Fi[sub]e[/sub](y) konverguje a pocet takych y je aspon e+ 1. To znamena, ze existuje s, take, ze Fi[sub]e,s[/sub](y) konverguje. + pocitadlo, ze ich mam uz aspon e+1. veta => existuje a PRP => S je RS
2) vid dokaz Riceovej vety
3) s-m-n veta s[sub]1[/sub][sup]1[/sup] (e,z) a 3 for cykly, ktore pre pevny parameter z a dane x ( nepotrebujes while ) spocitaju x[sup]z[/sup]
4) cca Hlavna mnozina A, vytvorim A' a B. A' = A[0], B=A-A'. postupne pre kazdy vrchol v z B zistim, ci B-v (black-box) ma riesenie, ak ano, tak v z B odoberiem a pridam do A. cca
5) vid minule pisomky. Z HK, G1 = G, G2 = kruznica nad |V| vrcholmi
snad niekomu pomoze, vela stastia !