Анализ вычислительной сложности ФС (547593), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Ответ: C0(factorial) = 106.597.

Сложность последовательного выполнения предлагается вычислить самостоятельно.

2. Целенаправленные эквивалентные преобразования функциональных программ

При разработке функциональной программы обычно встает вопрос, каким образом, преобразовывая программу при сохранении ее эквивалентности исходной программе, улучшить ее характеристики (время параллельного выполнения, др.).

В [1] предложена система целенаправленных эквивалентных преобразований функциональных программ по их схемам, которая для ациклических схем (схем, не содержащих рекурсивных определений) позволяет получать эквивалентную схему с минимальным временем параллельного вычисления значений соответствующих ей в интерпретации функций.

При этом принципиальное значение при приведении функциональных схем к оптимальной форме с точки зрения минимизации времени параллельного вычисления значений представленных в интерпретации функций имеет эквивалентность (AB)C = ABC (здесь A, B и C – функциональные термы). Легко показать, что время вычисления значений функций, имеющих функциональную схему справа в этой эквивалентности, не больше времени вычисления значений тех же функций по схеме слева.

Приведем список основных аксиом, используемых для целенаправленных эквивалентных преобразований ФС к виду с минимальным временем параллельного вычисления.

1. (A  B)C = A  BC;

2. A(B  C) = AB  AC;

3. (A B)*C = A*C B*C;

4. C*(A B) = C*A C*B;

5. (A B)C = AC BC;

6. C(A B) = CA CB;

7. A  (B C) = A  B A  C;

8. (A B)  C = A C B C;

9. (AB)*( AC) = A(B*C);

10. A(id*id) = A*A.

Список литературы:

1) Кутепов В.П. Организация параллельных вычислений на системах. М.: МЭИ, 1988.

Характеристики

Список файлов ответов (шпаргалок)