AISDT - Kolokwium 1 poprawkowe 4 luty 2008

Podpis:

Zadanie 1 (4p)

Dane: liczba naturalna n Wynik: liczba naturalna j function j = alg(n) i=n; j=0; while (i>j) i=i-1; j=j+1; end Dla podanego algorytmu określić wzorem ana­litycznym wynik j(n) oraz złożoność czasową t(n), jeśli operacją dominującą jest dodawanie i odejmowanie (t+=t-=1).

j(n)=......................................................... t(n)=.........................................................

Zadanie 2 (4p)

Dane: tablica a o długości n Wynik: liczba całkowita s function s = dzw(a) n=length(a); if (n=1) s=1; else r=floor(n/2); s1=dzw(a(1:r)); s2=dzw(a(r+1:n)); s=polacz(s1,s2); end Dla podanego algorytmu podać równanie rekursywne opisujące złożoność czasową t(n) oraz jego rozwiązanie t(n), jeżeli operacjami dominującymi są wszystkie dzielenia występujące w kodzie. Wiadomo, że w funkcji polacz jest 1 dzielenie. Jak się nazywa ten typ algorytmów?

Równanie rekursywne: Rozwiązanie t(n)=..................................... Typ algorytmu:...........................................

Zadanie 3 (4p)

Z badania złożoności oczekiwanej pewnego algorytmu na laboratorium AISDT otrzymano przebieg A(n) pokazany obok. A(n)=Θ(g(n)). Oznacza to, że A(n) można przybliżyć asymptotycznie funkcją f(n)=p*g(n)+q. Dobrać p i q tak by f(n) było najlepszym przybliżeniem asymptotycznym. Podać g(n), p, q i dorysować wykres f(n) linia pogrubioną.

g(n)=.................................. p=....................., q=.......................

Zadanie 4 (4p)

function a=algorytm(a) for p=1:n-1 s=a(p); k=p; for j=p+1:n if (a(j)<s) s=a(j); k=j; end end s=a(p); a(p)=a(k); a(k)=s; end Jaki to algorytm? Pokazać zawartość tablicy a=[6,5,4,3,2,1] po wykonaniu kolejnych cykli pętli zewnętrznej for. Obliczyć liczbę t(6) wykonanych przy tych danych porównań <.

Jest to algorytm................................................ p=1: ......................................................... p=2: ......................................................... p=3: ......................................................... p=4: ......................................................... p=5: ......................................................... p=6: ......................................................... t(6)=.........................................................

Zadanie 5 (4p)

Tablicę a=n:-1:1 przetwarzamy za pomocą buildheap. Podać wynikową tablicę „a” i złożoność t(n) algorytmu mierzoną liczbą porów­nań kluczy. Czy są to dane optymistyczne?

a wynikowe=.................................................. t(n)= Czy dane są optymistyczne? ........................

Zadanie 6 (4p)

Algorytmem merge scalamy dwie tablice: [1,3,5] i [2,4,6]. Pokazać wynik po kolejnych krokach scalania. Obliczyć sumaryczną liczbę porównań elementów.

Stan początkowy: [1,3,5|2,4,6] Po 1 kroku:................................. Po 2 kroku:................................. .................................................... .................................................... .................................................... .................................................... liczba porównań=.......................

Zadanie 7 (4p)

W wyniku przetworzenia zwykłym algorytmem partition tablicy [a,b,c] otrzymano [2,1,3], a w wyniku przetworzenia [c,a,b] otrzymano [1,3,2]. Zidentyfikować a, b, c.

a=...................... b=...................... c=......................

Zadanie 8 (4p)

Algorytmem countsort sortujemy ciąg a stanowiący pewną permutację elementów ciągu 1:n. Dla pewnej operacji dominującej złożoność tego sortowania jest Θ(g(n)). Wszystkie wyrazy sortowanego ciągu podniesiono do kwadratu. Teraz złożoność czasowa sortowania wynosi Θ(h(n)). Określić g(n) i h(n).

g(n)=...................................................... h(n)=.......................................................

---