Część I

Zadanie 1.

Oszacuj złożoność następujących procedur i funkcji. Ustal, co one robią i zaproponuj (jeśli tylko istnieje) szybsze algorytmy:

a)

function J(n:integer):integer;

begin

if (n=0) then J:=1

else if (n mod 2 = 0) then J:=J(n-1)+1

else J:=J(n-1)-1;

end;

b)

function F(n:integer):integer;

begin

if (n=0) then F:=1

else if (n=1) then F:=2

else if (n mod 2 = 0) then F:= F(n div 2)*F(n div 2)

else F:=2*F((n-1) div 2)*F((n-1) div 2)

end;

c)

function Z(n:integer):integer;

begin

if (n=0) then Z:=1

else Z:=Z(n-1)*Z(n-1)

end;

d)

function N(n,k:integer):integer;

begin

if (k>n) then N:=0

else if (k=0) then N:=1

else N:=N(n-1,k-1)+N(n,k-1);

end;

Zadanie 2.

Ustal, co robią poniższe procedury i funkcje, a następnie oszacuj ich złożoność:

a)

procedure M(A,B: array [1..n] of integer;

var C: array [1..2n] of integer);

begin

i:=1; j:=1;

while (i<=n) and (j<=n) do

begin

if (A[i]>B[j]) then

begin

C[i+j-1]:=B[j];

j:=j+1;

end

else

begin

C[i+j-1]:=A[i];

i:=i+1;

end;

end;

if (i>n) then

for i:=j to n do C[i+n-1]:=B[i]

else

for j:=i to n do C[j+n-1]:=A[j];

end;

b)

function I(n,m:integer):integer;

begin

if (n<0) then I:=-I(-n,m)

else if (m<0) then I:=-I(n,m)

else if (n=0) then I:=0

else I:=m+I(n-1,m);

end;

c)

function S(n,m:integer):integer;

begin

if (n=0) then S:=m

else if (n<0) then S:=S(n+1,m)-1

else S:=S(n-1,m)+1

end;

Zadanie 3.

Rozwiąż równanie rekurencyjne:

T(n)=T(n/2)+log₂n,

wiedząc, że T(1)=1.

Rozwiązanie:

Niech: n=2­­­­­^m, mamy T(2^m)=T(2^m/2)+m=T(2^m-1);

Niech: U(m)=T(2^m), mamy U(m-1)+m, ponieważ d(m)=ω(aⁿ);

Mamy: U(m)=O(md(m))=O(m²); wracając do n: T(n)=O(log₂n)

Zadanie 4.

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

Rozwiązanie:

Metoda postępowania jest w miarę prosta: najpierw sprawdzamy, czy dane są już posortowane, jeśli tak to opuszczamy procedurę, jeśli nie, to sortujemy metodą bąbelkową. Zakładamy, że sortujemy niemalejąco:

procedure sort(A[1..n]:integer);

var

i,j:integer;

ok:boolean;

begin

ok:=true;

for n:=2 to n do

if A[i]<A[i-1] then ok:=false;

if ok then return(A);

for i:=1 to n do

for j:=i+1 to n do

if A[j]<A[i] then A[i]:=:A[j];

end;

Zadanie 5.

Graf zapisano w postaci macierzy sąsiedztwa wierzchołków. Napisz algorytm rozpoznający, czy ten graf jest gwiazdą i oszacuj jego złożoność obliczeniową

Rozwiązanie:

Aby graf był gwiazdą, musi mieć jeden wierzchołek stopnia n-1 i pozostałe stopnia 1. Tak więc w macierzy sąsiedztwa wierzchołków musi być jeden wiersz z n-1 jedynkami i pozostałe z 1 jedynką.

function star(G:graph):boolean:

var

i,j,k,srodek:integer;

begin

srodek:=0;

for i:=1 to n-1 do

begin

k:=0;

for j:=i+1 to n do if G[i,j]=1 then inc(k);

if k=n-1 then srodek := srodek +1

else if k<>1 return(false);

end;

if srodek<>1 then return(false)

else return (true);

end;

Zadanie 6.

Oszacuj liczbę kroków procedury „zagadka”:

procedure zagadka(m:integer);

begin

(1) for i:=sqr(n) downto 1 do

(2) if odd(i) then

(3) for j:=1 to i do

(4) for k:=i+1 to n do x:=x+1;

end;

Rozwiązanie:

Należy rozpatrzyć dwa przypadki pętli głównej (1):

• i < n, w tym przypadku pętla (1) wykonuje się n razy, pętla (3) średnio O(n²) razy dla jednego obiegu petli (1). Tak wiec łączna liczba kroków algorytmu dla tego przypadku wynosi O(n³),

• i ≥ n, w tym przypadku pętla (3) nie wykonuje się w ogóle. Pętla (1) wykonuje się średnio n²-n, czyli O(n²) razy. Pętla (2) wykonuje się średnio (n²-n)/2, czyli O(n²) razy. Tak więc łączna liczba kroków algorytmu dla tego przypadku wynosi O(n⁴). Ponieważ czynnik O(n⁴) jest dominujący nad O(n³), liczba kroków algorytmu wynosi O(n⁴).

Zadanie 7.

W historii znajdowania maksymalnego przepływu w sieci znane są następujące coraz lepsze algorytmy:

• Forda-Fulkersona (1956)

• Edmondsona-Karpa (1969)

• Dinica (1970)

• Karzanowa (1974)

• Cherkaskyego (1977)

• Shiloacha (1979)

• Sleatora-Tarjana (1980)

• Goldberga-Tarjana (1988)

o złożonościach: O(n²m), O(mnlog(n²/m)), ?, O(n²sqrt(m)), O(nmlogm), O(nm²), O(n³), O(mnlog²n), gdzie ? oznacza brak informacji o złożoności w publikacjach. Uporządkuj te złożoności i wypisz obok odpowiednich nazwisk. Uwaga grafy spotykane w praktyce są rzadkie tj. mają m=o(nlogn).

Rozwiązanie (z tym ostrożnie, było kilka wersji i nie jestem pewny co do kolejności jeśli chodzi o „?”):

1. O(n³)

2. O(n²m)

3. O(nm²)

4. O(n²√(m))

5. O(nmlog³n)

6. O(nmlog(n²/m))

7. O(nmlogm)

8. ?

Zadanie 7.

Stosując wyszukiwanie sekwencyjne w tablicy nieposortowanej bądź binarne w tablicy posortowanej wybieramy pomiędzy czasem wyszukiwania a czasem przetwarzania wstępnego. Jak wiele wyszukiwań binarnych trzeba wykonać w najgorszym przypadku danych w tablicy n-elementowej, żeby opłacił się czas potrzebny na wstępne posortowanie tablicy? Przyjmując, że współczynniki proporcjonalności złożoności są równe !, odpowiedź sformułuj w terminach oszacowań asymptotycznych.

Zadanie 8.

Dana jest procedura rekurencyjna MacCarthy(n), n ≥ 0 jak niżej. Naszkicuj wykres liczby kroków (tj. liczby wywołań) tej procedury funkcyjnej i zapisz ją w terminach symbolu O().

Rozwiązanie:

function MacCarthy(n:integer):integer;

begin

if n > 100 then return(n-10)

else return(MacCarthy(n+11));

end;

Zadanie 8.

Napisz dowolny algorytm o następującej złożoności obliczeniowej.

Zadanie 8.

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 algorytm hybrydowy dla obliczenia wartości n-tej liczby Fibonacciego.

procedure hybryda(n:integer):integer;

begin

if n<10 then

begin

if n<=2 then return(1)

else return(hybryda(n-1)+hybryda(n-2));

end;

A[1]:=A[2]:=1;

for i:=3 to n do A[i]:=A[i-1]+A[i-2];

return (A[n]);

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?

1

Przykładowe zadania egzaminacyjne ze Złożoności Obliczeniowej Algorytmów

(niektóre z rozwiązaniami , a niektóre bez )

Opracowanie, oprawa i łamanie: KAGO

6

10 20 30 40 ...

n²

20

100

---