kolp2

AISDE - Kolokwium 23 listopada 2009 - godz. 17	Podpis:
Zadanie 1 (5p)
Dane: liczba całkowita nieujemna n Wynik: liczba całkowita s function s = alg(n) s=0; while s<n s=s+1; end Dla podanego algorytmu określić wzorami analitycznymi s(n), złożoności czasowe t=(n), t+(n), t<(n), jeśli operacją dominującą jest odpowiednio przypisanie, dodawanie i porównanie. Niech m będzie długością bitową n i t+(m)= 0(g(m)). Określić najprostszą postać g(m).	t-(n)=.........,(4.±d..................................(lp) t+(n)=.....................................................(lp) t<(n)=.........D.±d...................................(lp) g(m)=....................................................(2p) S[h)~ h &f>)
Zadanie 2 (5p)
Pewien algorytm ma złożoność czasową: n\ogndlal<n<\6 t(n) = \ [64 + 2{n -16) dla n> 16 Określić takie najprostsze g(n), takie że t(n)= 0(g(n)). Udowodnić prawdziwość tego oszacowania asymptotycznie dokładnego z definicji.	8(ti)=..........M..............f..... Dowód:.^ ?oUts^-&-c Z C. i o hi^t £ fajrl cĄyO f c2 ->ó (Ho> Qo c2 lo CA ^ 2. ( c 2 = 3 2v\ Źz 2 (A -V 0) cUOs-' t/\ 'y & ^ 2 4 v\y/^2-

n =

Zadanie 3 (5p)_

Mamy dwa ciągi: a, b, stanowiące pewne permutacje ciągu {1,2,.Sortujemy je algorytmem selcctionsort. Sortowanie a wymaga 10 porównań. Określić n. Ile porównań wymaga sortowanie b? W jakim przedziale domkniętym zawiera się liczba porównań przy sortowaniu ciągu a algorytmem inser-tionsort?

Zadanie 4 (5p)

Tablica a=[2,l,3,5,4] jest wynikiem parti-tion(b). Operacja c=heapify(a, 1) wymaga tl porównań elementów’ tablicy. Operacja t-countsort(a) wymaga k komórek pamięci na tablice używane w algorytmie. Tablicę a sortujemy algorytmem mergesort. Drzewo podziału będzie miało wysokość p krawędzi. Określić b(l), c. tl, k, p.

tsclcctionsori(b) ...JM.............

tinscrtionsorl(«0 £    , ./.i..

c

(2p)

•dp)

(2p)

b(l)=..............2>.........................(lp)

.......tu

-??■....................................(ip) ^

3

tl =

k=

P=

(lp)

n L *2eScng i