Zadania 6

a:=a*l;

end;

|/ 3 7. Przeanalizuj następującą procedurę funkcyjna zagadka procedurę zagaukn(a,n:imeger):integer; begin

if n=0 then rerum(l); else

begin

haif:=7.agadka(aj_n/2j); half:=half*half; ii* odd(n) then hałL^hajPm; retiirn(half); end;

end;

a)    Co oblicza zagadka ?

b)    Jaka jest złożoność tej procedury jako funkc ja n ?

c)    Jaka jest złożoność tej procedury jako funkcja rozmiaru danych?

fa) Oblicza a¹¹,

b) T(n)={ 1.    n=0

T(n/2)+4 n>0

d(b)>a, więc T(n)=n^Alog:4“n². T(n)=0(a².) - funkcja wykładnicza 3| c) Ponieważ wykonywana jest operacja a*a, więc złożoność obliczeniowa zaieży od rozmiaru a. Mogę dobrać dowolne a i spowodować, aby funkcja wykonywała się dowolnie diugo. _________.—_- 13. Dla małych rozmiarów danych algorytmy o dużej złożoności asymptotycznej są zwykle szybsze od algorytmów o mniejszej złożoności. Biorąc to pod uwagę programista napisał następujący ałgorytm hybrydowy dla obliczania warrości n-tej liczby Fibona. procedurę bybryda(n;integer):integer; fcegia

if n<10 then

if n<2 then reium(l)

else return{bynryda(n-l>Tbybryda(n-2)):

AI13:=A[2]:=1; for i:=3 to n do Aii]:=A[M]-AlF2); retura(A{nj); end;

Oszacuj liczbę kroków wykonywanych przez ten algorytm jako funkcję wartości n. Czy jest ona tożsama z funkcją złożoności obliczeniowej ?

Dla n<10 obowiązuje równanie rekurencyjne, ale nas to nie interesuje, bo n jest ograniczone z góry i ilość kroków też jest ograniczona. Dla n>ll T(n)=0(n). Tak więc złożoność jest O(n). Wydaje mi się, że jest to też złożoność obliczeniowa.

19. Problem Liczba Chromatyczna jest zdefiniowany następująco : TDany jest graf G oraz liczba dodatnia k. Czy liczba chromatyczna grafu    ?”* Problem ten pozostaje NP-zupelny nawet dla k=3. Pokaż, że skonstruowanie

1,33-pnzybliżonego algory tmu kolorowania grafu jest problemem NP-trudnym.

Jeśli zaiozymy, ze autor zadania oparł je na fakcie, że l.33<^J/j, to zadanie jest proste: Załóżmy, że mamy graf 3-ciiromaiyczny (czyli da się pokolorować 3 kolorami), a nie jest 2-chromatyczny (czyi: me można go pokolorować optymalnie w czasie wielomianowym). Nasz algorytm pokolorowałby ten graf w najgorszym przypadku 3“ 1.33=3.99<4 — kolorami. Czy li nie może pokolorować grafu 4 kolorami. Czyli koloruje 3 kolorami i daje rozwiązanie optymalne. Czyli nie. jest to algorytm -wielomianowy (chyba, że P=N^rP), ponieważ zawsze jednoznacznie odpowiada na pytanie “Czy'.liczba chromatyczna grafu x(G)<3 ?”.

20. Większość praktycznych kryptosySternów opiera się na założeniu dużej złożoności problemu faktoryzacji liczb naturalnych. Poniżej podano różne opinie na ten temat, z których przynajmniej jedna nie jest prawdziwa. Skomentuj w dwóch zdaniach każdą z nich :

a) mnożenie liczb całkowitych jest funkcją, kio rej odwrotność, czvli dzielenie pozostaje trudne obliczeniowo,