3

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

Ocena

Nazwisko

Imię

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

I | 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

max{X[fc]: 1 < k < i} > jnax{Y[fc]: 1 < k < j}

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 mod

— 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;

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

stałych.

Jeżeli T* jest pesymistyczną / złożonością obliczeniową pro- 1* = Q cedury A, to

Jeżeli X* jest optymistyczną , złożonością obliczeniową pro- X* = 0
	\
cedury A. to

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

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

Strona 1