[Zk] 8.6.2011

eis

[Zk] 8.6.2011

Příspěvek od eis »

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

Re: [Zk] 8.6.2011

Příspěvek od rur »

Řekl bych, že na 5. jde převést obecně hledání čehokoliv rozumného v grafu, ať už HK, HC, kliky nebo nezávislé množiny.
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“