PAA 04.02.2011

Zadanie 1 (18pkt)
Udowodnij, że jeżeli P≠NP, to dla problemu minimalnego pokrycia wierzchołkowego
grafu nie istnieje:
a) wielomianowy algorytm 1-absolutnie aproksymacyjny
b) schemat FPTAS

Zadanie 2 (20pkt)
Ułóż odpowiednie równanie rekurencyjne, a następnie za pomocą symbolu

Θ

(

⋅

)

oszacuj asymptotyczną liczbę kroków wykonywaną przez poniższą funkcję f(n).
Podkreśl słowo, które najlepiej charakteryzuje jej klasę złożoności obliczeniowej:
subliniowa, liniowa, wielomianowa, superwielomianowa, wykładnicza,
superwykładnicza.

function f (n : integer) : real;
begin

x:=1;
if n>1 then for i:=1 to 4 do x:=3*f(



n/2



)+2*x;

j:=0;
while j<n do begin

j:=j+1;
if n≤j

3

then return x*j;

end;

end;

Zadanie 3 (10pkt)
Czy poniższy algorytm może być uznany za dowód tego, że problem testowania czy
liczba naturalna n jest złożona należy do klasy P? Dlaczego?

function LiczbaZlozona (n : integer) : boolean;
begin

for i:=2 to



n/2



do

if n mod i = 0 then return true

return false

end;

Zadanie 4 (20pkt)
Dany za pomocą symbolu

Θ

(

⋅

) oszacuj asymptotyczną liczbę kroków poniższej

procedury A(n) jako funkcji n będącego liczbą naturalną. Następnie podkreśl słowo,
które najlepiej charakteryzuje jej klasę złożoności obliczeniowej: subliniowa, liniowa,
wielomianowa, superwielomianowa, wykładnicza, superwykładnicza.

procedure A(n);
begin

i:=j:=1;
while i<n do begin

i:= i+i;
for k:=1 to i do j:=j+1;

end;

end;

Zadanie 5 (12pkt)
Pokaż, że rozstrzygnięcie, czy dla danego ciągu (n

1

,...,n

k

) liczb całkowitych (c

1

,...,c

k

)

taki, że |c

i

|=n

i

, dla i=1,...,k oraz c

1

+c

2

+...+c

k

=0 jest NP-zupełne.

Zadanie 6 (20pkt)
Wiadomo że problem komiwojażera jest NP-trudny. Opisz rozumowanie pozwalające
ustalić, czy pozostanie on NP-trudny czy wielomianowy, gdy w grafie n-
wierzchołkowym:
a) wszystkie wagi krawędzi będą parzyste
b) wszystkie wagi krawędzi będą nieparzyste
c) wszystkie wagi krawędzi będą identyczne
d) wszystkie wagi krawędzi należą do zbioru {1,n} i z każdego wierzchołka wychodzą
co najwyżej 2 krawędzie jednostkowe
e) wszystkie wagi krawędzi należą do zbioru {1,n} i z każdego wierzchołka wychodzi
co najmniej n-2 krawędzi jednostkowych