DSC00002 (4)

A

0

1

Z*<U

Jeżeli algorytm o złożoności 0(n⁴) w ciągu lh jest w stanie rozwiązać problem o rozmiarze N. to jeżeli prędkość procesora wzrośnie 1000-krotnie wówczas w tym samym c/asic lh rozwiążemy problem o rozmiarze: a, 101 |    5,62 N

c.    250 N

d,    3.98 N

Zad.4

Jeżeli algorytm sekwencyjny w ciągu lh jest w stanie rozwiązać problem o rozmiarze N. to jeżeli dysponować będziemy p=10 procesorami (przy założeniu braku opóźnieó komunikacyjnych i połączeniach między procesorami typu to W czasie lh rozwiążemy problem o rozmiarze

a >**10 N |    «*!0N

c, «* 10 N d trudno powiedzieć

Zad. i

Jeżeli cza* działania algorytmu sekwencyjnego wynosi 3 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 2, to górne ograniczenie na czas działania alg równoległego reprezentowanego przez pewien AGS i wykorzystującego p~ł procesory będzie:

ji,
i	<*5
c<
1	«*3

I