5

Kolokwium ze Złożoności Obliczeniowej_17 kwietnia 2003

Nazwisko Imię

Uwaga! W każdym z zadań, w których występuje litera r, oznacza ona rozmiar danych wejściowych.

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

n-elementowe tablice X oraz Y; ustal, ile jest takich par (i,j), że i < j oraz

fc=l    k~ 1

Algorytm ten musi spełniać następujące warunki:

•    może korzystać tylko ze zmiennych lokalnych typu word, integer, array of word lub array of integer;

•    może korzystać tylko z następujących instrukcji:

—    warunkowych: if ... then ... else lub if ... then

—    pętli: while ... do, repeat ... until, for... to ... do lub for ... downto ... do

—    logicznych: and, or i not

—    arytmetycznych: +, —, *. / (dzielenie całkowitoliczbowe!) i niod

—    porównania: >, <, >, <, =, ^

—    podstawienia (:=) i zamiany (:=:)

• jego pesymistyczna złożoność obliczeniowa musi mieć wielomianowe tempo wzrostu

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

begin

A := end;

I 1 3-2~| Uzupełnij poniższe zdania, korzystając tylko ze znaków r, +,    •, /, lg, yf, |_, J, [,],(,) oraz dowolnych

stałych.

X* = 0 X* = ©

Tl* = 0 Tl* = e

Jeżeli X* jest pesymistyczną złożonością obliczeniową procedury A, to

Jeżeli X* jest optymistyczną złożonością obliczeniową procedury A, to

Jeżeli Tl* jest pesymistyczną złożonością pamięciową procedury A, to

Jeżeli jest optymistyczną złożonością pamięciową procedury A. to

Strona 1