Zadania 2

d) Przypuśćmy, że udogodniłeś, iż 3SATa.n. Co symbolicznie op.losi.sz światu ? c) Przypuśćmy, że udowodniłeś, iż IlaSSAT. Co symbolicznie ogłosisz światu ? f) a) O nie należy^7, ?,

5) b) H należy P.

h)    c) P=NP, '

i) d) ? należy NPC,    (chyba tu powinno być nic ...)

j) e) nic,    (a ru p należy do NPC)

5. Następujący algorytm rozwiązuje optymalizacyjna wersję problemu Suma Podzbioru w sposób 2-przybiiżony, tzn. znajduje podzbiór A’<zA taki, że p/2^£(po i:a,należących do A*) a_;, przy ograniczeniu S(po kajnnleżących do A’)

2i<p.

procedurę SS*(A_łn_łp); begin

(*) uporządkuj zbiór A nierosnąco;

b:=0;    -

for i:=l to n do if tMAfyj^p tbea b:=b+Ajij; write (b); {tj. PssOO) end;

a)    Oszacuj złożoność tego algorytmu,

b)    Podaj przykład danych I, dla który ch F_o0D=2Fss(I)_?

c)    Niech ’SS będzie algorytmem, z którego usunięto instrukcję (*). Pokaż, że nie istnieje stała £<co taka, że SS jest algorytmem e-przybliżonym.

d)    0(nlogn) - sortowanie,

e)    np. dla n=3,1=100,99,99; p=19S; F_SS(I)=100, F₀(I)=19S,

f)    po usunięciu linii (*) konstruuję dane I=l,e-j-l: n=2, p=eM=F_c(I), F_Ss(I)-l; z def. f(I)=Fo(r)/F_A(I)<p_I a więc więcej niż założenie e F₀(I)=s*F_Ss(I)-

6. Problem Ograniczone Drzewo Spinające (ODS) zdefiniowany jest następująco: “Dany jest graf G i liczba naturalna k. Czy G raa drzewo spinające stopnia £k ?”. Udowodnij, że : a) graf półhamiltonowski aODS,

dla żadnego e<lp nie istnieje w ielomianowy* algorytm e-przybliżony dła znajdowania drzewca spinającego o miniiDainym stopniu (chyba, że P=NP).

a)    przyjmijmy k=2, jeżeli w G znajdziemy drzewo spinające <3ę to znaczy, że w G istnieje ścieżka pólbamiltonowska procedurę ODS(G:graph);bcclean;

fcegin i; =2:

if ODS(G,i) then return tnie ełse return faise;

end;

b)    e<l,5, Gdyb>^r istniał algorytm, który rozwiązywałby problem drzewa spinającego o minimalnym stopniu z e-przybliżenicm (e<l,5) tzn. rozwiązuje problem grafu pólhamiltonowskiego, gdzie stopień wierzchołków drzewa spinającego jest £2, to taJd algorytm mógłby się max pomylić o mniej niż 1, a stopień wierzchołka musi być liczbą całkowitą, wobec tego taki algorytm rozwiązałby to w czasie wielomianowym - ale taki algorytm nie istnieje.

7. Rozw iąż równanie rekurcncyine T(n)=T(n/2)*rlog;n wiedząc, że T(l)=3 Niech : n=2M Mamy : T(2^m)=7(2^/2)trr^T(2^r- )-m;"

Niech : L‘(m)=T(2~); Mamy : U(m)=U(m-I)+rn; Ponieważ d(m)=a(aⁿ). Mamy : U(m)=0(md(m))=O(m-); Wracając do_n : T(n)=0(log^:n)

8. Zaprojektuj algorytm sortowaniu z liniową złożonością najlepszego przypadku i kwadratową złożonością najgorszego przypadku danych.

Metoda postępowania jest prosta : najpierw sprawdzamy, czy dane są już posortowane, jeśli tak to opuszczamy procedurę, jeśli me, to sortujemy bąbelków o. Zakładamy, źc sortujemy niemalejneo.

Proccdu re So rt (A [ 1.. n j: i mege r).