pto1

Grupa/rok.

sąsiad lewy

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.

Wyszukiwarka

Podobne podstrony:
10099 strona1 (10) 100 Nazwisko i imię 21.01.2005. Grupa/rok. Czas trwania testu: 120 minut sąsiad l
pto kolo1 1 05 tołPA- 100 Nazwisko i imię03.12.2005. Grupa/rok. sąsiad lewy sąsiad prawy Czas trwani
NAZWISKO I IMIĘ (numer albumu): EGZAMIN Z BANKOWOŚCI Test jedno- lup wielokrotnego ysyboru CZAS
bankowosc1 NAZWISKO I IMIĘ (numer albumu): EGZAMIN Z BANKOWOŚCI Test jedno- lub wielokrotnego wyboru
03 10 cz1 Nazwisko i imię...........................................................Egzamin UCYF cz
zad5 (18) Nazwisko Imię Podpis Nr albumu Grupa Sala Uw aga. Wypełnić górę kartki. Wyłożyć indeks do
87028 pto12 100 Nazwisko i imię21.01.2006. Grupa/rok. sąsiad lewy sąsiad prawy Czas trwania testu: 1
img387 (5) GQ 6^7‘yf 4fw mi Ki-y-2 Lbrofo. Nazwisko, Imię Gdańsk, 12, o "wf Kolokwium 1/1

więcej podobnych podstron