Zadania 9

liniowa, kwadratowa, czy wykładnicza ? Podaj przykład sytuacji, dla której liczba kroków jest maksymalna. Chcemy oszacować liczbę kroków metody Student. W najgorszym przypadku ilość pięter jest postaci 2^k-l. Wtedy, gdy zrzucony profesor z piętra o numerze 2^k'¹ jeszcze nic zginie, studenci nie mogą podwoić numeru piętra, gdyż wyszli by na dach. W związku z tym, że nie wolno im stosować btsekcji idą po jednym piętrze do góry sprawdzając efekt ‘zrzutuT Tych pięter jest jeszcze n/2 -1, gdzie n to liczba pięter. W najgorszym przypadku to właśnie ostatnie pięrro przyniesie ofiarę (co zakończy test).

Czyli {(1) Dochodzenie do piętra o numerze T~^l

w ten sposób, że pietrOj:=2*piętrOj.i    0(lcg_;n)

(2) Piętro po piętrze do skutku C(n), bo C(n/2)=C(n)

T(n)-0(n) to jest metoda liniowa Najgorszy przypadek został omówiony powyżej Liczba kroków wynosi - log-(n/2)+ n/2 -I-Iog^n* n/2 - 2 Gdy n=2^k. to liczba kroków; = k-K2^k'¹-L

28. Dane są problemy decyzyjne A, —, F oraz X. Przypuśćmy, że A i B są problemami należącymi do klasy ?, C i D

są problemami w klasie NP.-P, £ jest NPC, zaś F nie należy do NP. Odpowiedz na każde z poniższych pytań słowem :

tak - gdy relacja jest prawdziwa zawsze (bez względu na to, czy P=NP),

nie - gdy relacja może być fałszywa,

może - gdy relacja jest prawdziwa, gdy P=NP.

a)    AaC,    f) CaE,    k)    2SATaB,    o)    AeNPC,

b)    CaA,    g) CaD,    1)    3SATctC,    p)    X<eN?C, gdy Xa£,

c)    FaA,    b) EeP,    1)    Ca3SAT,    r)    XeNPC, gdy EaX,

d)    AaE,    i) De?,    m)    3SATaE,    s)    XeNP, gdy XaC,

e)    EaA,    j) EeiYP, n)    Ea3SAT,    t)    XeNP,gdyCaX

f)    a) tak    ,    f) tak,    k) tak,    o)    może,

g)    b) może,    g) może,    1) może,    p) może,

h)    c) nie,    h) może,    1) tak,    r)    nie(?),

i)    g) tak, i) może.    m) tak,    s)    tak,

j)    e)może, j) tak n) tak,    t) nie(?).

2

29. Napisz dowolny algorytm o niewielomianowej złożoności obliczeniowej.

funetion Fib(n:integer):integer;

begin

11(0=110=2) then rerum (1);

else return (Fib(n-2)+Fib(n-l));

end:

30. Następujący problem Iloczyn Macierzy : “Dane są 3 macierze kwadratowe A, B i C; czy A*B=C ?” jest w relacji a do 3SAT. L^rdowodni] ten fakt.

Z definicji fljaLL wynika, że znamy algorytm na IN. Problem czy A*B=C a 35AT. Znamy algorytm na 3SAT (C_lf G>, .... CD, gdzie Cf={Xi_U X_a,..., X,₃). Algorytm ten sprawdza, czy dla wyrażenia (X_n-hX_n-5-X,₃)( Xz>+ Xr>)...( X„i+ X_lCr X_n3) istnieje podstawienie X takie, że wyrażenie jest prawdziwe. Budujemy transformację T, która będzie działać w czasie wielomianowym T: input A.B,C D:matri.x;

INPUT 3 SAT:set of G D=A"B;    } Ctn³)

if(D==C) then    } 0(n^:)

INPUT 3 SAT= {(x;,x;,x₃), (xi,Xj)}; nlsc

INPUT 3SAT={(xv\_:,x_:),(x₁,x_i,x₃)_>(x_ux₃,x₃).(x₁.X:\X;ó, (x₁.x_:.x_:i)_?(x₁.x₃,x2)};

Wiech¹, gdy przejdziemy przez T. to na wejściu do algorytmu 3SAT mamy jedną z dwóch wartości INPUT 3SAT. Gdy będzie pierwsze podstawienie io 3SAT zwraca truć, co jest zgodne z tym, że C-A*B. Gdy 3SAT dostanie drugą wersję 1NPU t 3SAT wówczas algorytm zwróci fałse co jest zgodne z tym, że CVA"B. A więc, ponieważ złożoność obliczeniowa 3(n)-0(n^J). twierdzę że problem A*B=C jest rcdukowaJny do problemu 33AT, czyli A*B=C a 3SAT.