Zadanie 1

Czy podany program jest częściowo poprawny względem asercji:
a)

{ x=y } if x>5 then x:= x+3 else x:= x-1 { x<y }

b) { x=2 & y >4 } y:= x+y { y>5 }

Zadanie 2

Wyprowadź stwierdzenie: { x=y } x:= x+1 { x != y } w logice Hoare'a

Zadanie 3

Czy program
while x != y do x:= x-1
ma własność stopu dla x i y spełniających warunek:
x>0

Zadanie 4

Znajdź sumę szeregu a

1

+...+a

n+k

dla a

i

zdefiniowanych następująco

a) a

i

= i

b) a

i

= 2i-1

Zadanie 5

Czy suma szeregu a

1

+...+a

n

dla a

i

zdefiniowanych następująco

a

i

= 2i

2

-1

jest w klasie
a)

O(n)

b)

o(n

2

)

c)

O(n

3

)

d)

ω(n)

b)

Ω(n

2

)

c)

Ω(n

3

)

Zadanie 6

Złożoność programu można opisać równaniem

T(1) = const., T(n) = 3T(n/2) +n

jakiego rzędu jest funkcja T?