1

Kolokwium ze Złożoności Obliczeniowej 26 kwietnia 2003

Kolokwium ze Złożoności Obliczeniowej 26 kwietnia 2003

Ocena [

Nazwisko    _ __________

Imię 1 11 M 11 II 1 II II 1 II 1 I 1

Uwaga! W każdym z zadań, w których występuje litera r, oznacza ona rozmiar danych wejściowych. Przyjmujemy, że funkcja Pow(x,y) oblicza x^v w czasie 0(y).

|    [ 20-0 | Uzupełnij poniższy kod tak, aby powstał algorytm, który rozwiązuje następujące zagadnienie: dana jest

macierz sąsiedztwa A grafu G oraz liczba naturalna k: ile fc-wierzchołkowych gwiazd zawiera się w grafie G? Uwaga! Pesymistyczna złożoność obliczeniowa tego algorytmu musi mieć wielomianowe tempo wzrostu!

function X( A: array [l..n, l..n] of word; fc: word ): word; var

begin

X : = end;

I 1 10-0 I Niech F: N —► N będzie funkcją daną wzorem F(n) = 3²". Uzupełnij poniższy kod tak, aby powstał algorytm, którego pesymistyczna złożoność obliczeniowa jest równa Q(F(r)).

function Y{ n: word ): word: var

begin

Y := 0; end;

Strona 1