Параллельные вычисления. Баканов В.М. - 69 стр.

                                      - 69 -


метризованным по размеру входных данных. Ацикличность ГА следует из
невозможности определения любой величины в алгоритме через саму себя.
ГА также является ориентированным (все дуги направлены). Различают де-
терминированный ГА (программа не содержит условных операторов) и не-
детерминированный ГА (в противном случае). Для недерминированного ГА
не существует взаимно-однозначного соответствия между операциями опи-
сывающей его программы и вершинами графа при всех наборах входных па-
раметрах; поэтому чаще всего рассматриваются детерминированные алго-
ритмы. Не имеющие ни одной входящей или выходящей дуги вершины ГА
называются входными или выходными вершинами соответственно. Построе-
ние ГА не является трудоемкой операцией (чего нельзя сказать о процедурах
анализа графа) – любой компилятор (интерпретатор) строит (явно или неяв-
но) его при анализе каждого выражения языка программирования высокого
уровня
  Последовательность вычислений (один из вариантов) нахождения корней
                                                                 − b ± b 2 − 4ac
полного квадратного уравнения a x 2 + bx + c = 0 в виде x1,2 =
                                                                       2a
приведена в табл.4 и требует 11 операций высокоуровневого языка програм-
мирования (сложение, вычитание, умножение, деление, изменение знака,
вычисление квадратного корня и т.п.).

  Таблица 4 — Последовательность вычисления значений
       корней полного квадратного уравнения.

 № оператора       Действие                      Примечание
               Ввод a, b, c       Операции ввода не нумеруются
      0        a2 ← 2 × a         а2 – рабочая переменная
      1        a4 ← 4 × a         а4 – рабочая переменная
      2        b_neg ← neg(b)     b_neg – рабочая переменная,
                                  neg – операция изменение знака (‘унар-ный
                                        минус’)
      3        bb ← b × b         bb – рабочая переменная
      4        ac4 ← a4 × c       aс4 – рабочая переменная
      5        p_sqr ← bb-a4      p_sqr – рабочая переменная
      6        sq ← sqrt(p_sqr)   sq – рабочая переменная,
                                  sqrt – операция вычисления квадратного
                                        корня
     7         w1 ← b_neg+sq      w1 – рабочая переменная
     8         w2 ← b_neg-sq      w2 – рабочая переменная
     9         root_1 ← w1/a2     root_1 – первый корень уравнения
     10        root_1 ← w2/a2     root_2 – второй корень уравнения