2500335704

Ćwiczenie 5

Zaprojektuj algorytm typu CREW PRAM, który w czasie 0{n) znajdzie przechodnie domknięcie relacji binarnej.

Notatki

11 Sortowanie przez ranking

Czas 0(log n) i 0(n²) procesorów.

We: Wektor do posortowania X = [xi,... x_n\ Model: CREW PRAM._

Notatki

Notatki

Algorytm 8: Sortowanie przez ranking 1: for każda para i,j, gdzie 0 < i, j < n in parallel do

2:    if Xi >    Xj then

3:    Cij =    1

4:    else

5:    Cjj =    0

6:    end    if

7: end for

8: for i = 1 to n in parallel do

9:    policz Ti — Cij

10: end for

11: for i = 1 to n in parallel do

12:    ustaw element i na pozycji r, + 1 w tablicy wy

nikowej 13: end for

20