ASD ITN k1 05 2002 1

Kolokwium ALGORYTMY I STRUKTURY DANYCH ITN

PJWSTK, 11 maja 2002

Proszę uważnie przeczytać treść zadań i odpowiedzieć zaznaczając, w przypadku pytań testowych, wybraną odpowiedź kółkiem , lub wpisując odpowiedź w miejsce do tego przeznaczone, w przypadku innch form zadania. Żadne materiały pomocnicze nie są dozwolone. Powodzenia!

•f-Ł t ~

Zad.l Uporządkuj następujące funkcje ze względu na ich rosnący rząd wielkości: fi(n)= 3n*sin(n²), f₂(n)= lg(n²), f₃(n)= 3n+ lg(n!), f₄(n)= 100n+ 2 ^3lgn, f₅(n)= 0.01*n² + lg n⁴

Zisy-A    ocitgł.)    -ticHfłi³    jk ^ ^{+ <}V^V'

Zad.l Niech n oznacza zmienną przebiegającą liczby naturalne. Oceń prawdziwość każdej z ^ podanych zależności ^2^lgn=0(n)    (jrawdaj^ fałsz^

f    2²ⁿ = 0(2ⁿ)    prawda / Cfałsz,

0(2")

prawda / \fałsz nrawda / (fałsz

ni

4

i=

n = 0(lg n)

[z-    ftj.

Zad.l Uporządkuj następujące funkcje ze względu na ich rosnący rząd wielkości: fi(n)= n^f/2+lg(n), f₂(n)= Ig(n²), f₃(n)= 2 ^lg(n), f₄(n)= n²(n+n^2/3 )^m, f₅(n)= lg (n!) +(2 lg n)*n² + L^Y\ 2.    -V\    fu

Zad.l Przy każdym z ciągów zaznacz, czy jest (zaznaczamy TAK) czy nie jest (zaznaczamy NIE) uporządkowany rosnąco, ze względu na rząd występujących w nim funkcji (ne N) •W lg(n²), sin2n+Vn , 2^lgT- vt    <JAKj/ NIE

" ⁱ 1 OOOOn ^1/3 +n^l/2, lg n, 0.001 *n³ +6 TAK /(ME> n²lgn, n^3/2 lgn, lg³n    TAK l(NIlT

Zad. 2 Niech A będzie algorytmem, ktorego złożoność wyraża się funkcją n². gdzie n jest 6^ s rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze 100 Qo Ozj y (na pewmym komputerze) wynosi 1 sek. Oblicz, jaki jest maksymalny rozmiar zadania, które można rozwiązać przy pomocy tego algorytmu ( na tym samym komputerze) w ciągu lh ?

/ .

Zad. 2 Niech A będzie algorytmem, ktorego złożoność wyraża się funkcją rr. gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze 60    .]

(na pewnym komputerze) wynosi 9 sek. Oblicz, jaki jest maksymalny rozmiar zadania, które można rozwiązać przy pomocy tego algorytmu w ciągu 20h ?

Zad. 2 Niech A będzie algorytmem, którego złożoność wyraża się funkcją lg(n+4). gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze