Файлы для подготовки к экзамену (Анализ структурной сложности)

Посмотреть архив целиком

1. АНАЛИЗ СТРУКТУРНОЙ СЛОЖНОСТИ



Методы и алгоритмы структурного анализа подробно рассмотрены в [2, 3]. В частности, результаты этого анализа позволяют строить эффективные стратегии планирования процессов параллельного выполнения функциональных программ на кластерах [2].



1.1 Структурная сложность



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

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

Для того чтобы охарактеризовать некоторый объект, необходимо определить его структуру и связи. На этой точке зрения и основан структурный анализ, ставящий цель определения взаимосвязей внутри функциональной схемы, выявления рекурсивных и циклических определений в ней.

Ниже кратко изложены основные результаты разработанного подхода к анализу структурной сложности функциональных программ по их функциональным схемам [3]. Будем предполагать, что функциональная схема анализируемой программы представлена в виде системы функциональных уравнений


, (1.1.1)

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

Введем необходимые далее определения.

  1. Переменная непосредственно зависит от в (1.1.1), если входит в терм . Отношение непосредственной зависимости между и обозначим .

  2. Множество переменных, принадлежащих транзитивному замыканию непосредственной зависимости для будем обозначать [] и будем называть [] – множеством или классом транзитивности . Для пустого множества введём символ . Ясно, что если [] = , то – терм-композиция только базисных функций.

  3. Функция определена рекурсивно, если .

  4. Рекурсивное определение является простым, если .

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

  6. Определение простое, если не является рекурсивным и [] не содержит рекурсивных определений.

  7. Определения и взаимно рекурсивны, если и . Легко показать, что в этом случае .

  8. Назовём классом взаимной рекурсивности для множество всех взаимно рекурсивных с определений. Будем обозначать класс взаимной рекурсивности для через . Очевидно, что для взаимно рекурсивных определений классы взаимной рекурсивности будут эквивалентны. Легко показать, что неэквивалентные классы взаимной рекурсивности не пересекаются.

  9. Определение вложено (строго вложено) в , если (если и ). Очевидно, взаимно рекурсивные определения вложены друг в друга. Если определение – циклическое определение (простое циклическое определение), то будем также говорить, что циклическое вложение в определение (простое циклическое вложение в ).

  10. Введём отношение строгого включения () между классами , которое позволяет сравнивать структурную сложность определений функций ,