Анализ вычислительной сложности ФС (Файлы для подготовки к экзамену), страница 2
Описание файла
Файл "Анализ вычислительной сложности ФС" внутри архива находится в папке "Файлы для подготовки к экзамену". Документ из архива "Файлы для подготовки к экзамену", который расположен в категории "". Всё это находится в предмете "параллельные системы и параллельные вычисления" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "параллельные системы и параллельные вычисления" в общих файлах.
Онлайн просмотр документа "Анализ вычислительной сложности ФС"
Текст 2 страницы из документа "Анализ вычислительной сложности ФС"
Ответ: C0(factorial) = 106.597.
Сложность последовательного выполнения предлагается вычислить самостоятельно.
2. Целенаправленные эквивалентные преобразования функциональных программ
При разработке функциональной программы обычно встает вопрос, каким образом, преобразовывая программу при сохранении ее эквивалентности исходной программе, улучшить ее характеристики (время параллельного выполнения, др.).
В [1] предложена система целенаправленных эквивалентных преобразований функциональных программ по их схемам, которая для ациклических схем (схем, не содержащих рекурсивных определений) позволяет получать эквивалентную схему с минимальным временем параллельного вычисления значений соответствующих ей в интерпретации функций.
При этом принципиальное значение при приведении функциональных схем к оптимальной форме с точки зрения минимизации времени параллельного вычисления значений представленных в интерпретации функций имеет эквивалентность (AB)C = ABC (здесь A, B и C – функциональные термы). Легко показать, что время вычисления значений функций, имеющих функциональную схему справа в этой эквивалентности, не больше времени вычисления значений тех же функций по схеме слева.
Приведем список основных аксиом, используемых для целенаправленных эквивалентных преобразований ФС к виду с минимальным временем параллельного вычисления.
-
(A B)C = A BC;
-
A(B C) = AB AC;
-
(AB)*( AC) = A(B*C);
-
A(id*id) = A*A.
Список литературы:
1) Кутепов В.П. Организация параллельных вычислений на системах. М.: МЭИ, 1988.