pto1

100

Nazwisko i imię

04.12.2004

Grupa/rok.

sgsiad prawy

sąsiad lewy

Czas trwania testu: 90 minut

Nazwiska proszę pisać CZYTELNIE literami DRUKOWANYMI

UWAGA: Obok każdego pytania napisz końcowe rozwiązanie. Tok rozumowania prowadzącego do tego rozwiązania załącz

	20

1. Dana jest funkcja X

function A1(/i:integer):integer;

const printes:arrayfl ...6] of integer = {2,3,5,7,11,13};

begin

if ;»<=6 then return primes[n\

else return |2*A'(/7-l)-3*A'(«-2)+5*A'(n-3)-7^łA'(«-4)+l I ‘*(77-5)-13 **(77-6)1 inod 3;

end;

a)    Określ asymptotyczne tempo wzrostu czasu działania (liczby kroków) procedury X w zależności od n umieszczając je w jednej

z następujących klas: subliniowe, wielomianowe, superwielomianowe, wykładnicze, superwykładnicze (właściwą podkreśl).

b)    Podaj ogólną ideę i czas działania (w sensie symbolu O) innej, asymptotycznie najszybszej procedury wyliczającej tą samą funkcję X. Zakładamy, że jej kod nie może zawierać operacji arytmetyki zmiennoprzecinkowej.

Odpowiedzi uzasadnij.

2. Dana jest funkcja zagadka

function zagar/^(/7:integer):integer; begin

if n= I then return 102

else if 77=2 then return 20042004

else return max {I l_2*zagadka(n-\ )!zagadka(n-2)\}\

end;

a)    Podaj asymptotyczne tempo wzrostu funkcji zagadka (w sensie symbolu 0).

b)    Podaj asymptotyczne tempo wzrostu czasu działania procedury zagadka w funkcji n (w sensie symbolu 0).

c)    Określ słownie klasę złożoności obliczeniowej tej procedury jako: subliniową. wielomianową, superwielomianową, wykładniczą, superwykładniczą (właściwą odpowiedź podkreśl).

Odpowiedzi uzasadnij.

3. Mnożąc dwie duże macierze rozmiarów 777x77 i nxm (gdzie m<n) możemy użyć procedury klasycznej (z definicji) lub algorytmu Strassena dla macierzy kwadratowych uzupełniając wcześniej czynniki nie będące kwadratami o wiersze/kolumny zerowe. Podaj „krytyczne” tempo wzrostu parametru m w zależności od n, tj. taką funkcję m = J{ii), że dla ciągu par coraz większych macierzy, w których /// będzie rosło asymptotycznie wolniej niż/(/i) w końcu zacznie opłacać się procedura klasyczna, zaś dla w rosnących szybciej - Strassena.