Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

i
, 
k.
Элемент 
c
kj
рассылается по всем вершинам, имеющим те же самые 
координаты 
k, j.
Для 
n = 2
эти рассылки показаны на рис. 24 б. Все вершины 
соответствуют операциям вида 
а + bc
. 
 
Глава 7. Параллельные алгоритмы
 
Параллельный алгоритм –
алгоритм, предназначенный для реализации 
на параллельной вычислительной системе. Рассмотрим
задачу вычисления 
чисел Фибоначчи, решение которой реализовано в виде последовательного и 
параллельного алгоритмов. 
Математическая модель
Пример [2]
. 
Пусть последовательность Фибоначчи задана рекурентным 
соотношением 
F(n) = F(n 
–
 1) + F(n 
–
 
2), при F(0) = 1 и F(1) = 1
. Определить 
значение элемента n (для n>1).
Последовательный рекурсивный алгоритм
 
F(n) 
{ 
if(n<2) return 1; 
return F(n-2)+F(n-1); 
} 
Обозначим как 
G(n)
число операций для вычисления числа 
F(n).
G(n) = G(n 
–
 1) + G(n 
–
 2) + 1,
где 

---

72 
G(n 
–
 1) 
–
количество операций, необходимое для вычисления чисе
л F(n –
 1), 
G(n 
–
2) - 
количество операций, необходимое для вычисления чисел F(n –
2),
1 
–
одна операция для нахождения суммы.
Определяем: 
G(0) = 0, G(1) = 0. G