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;
