Понятие линейной программы

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

Формализация понятий зависимости и независимости между операторами программы

Понятие множеств переменных, используемых в программе

Множеством C (P) изменяемых переменных программы называются переменные, которые в ходе выполнения программы P меняют свое значение хотя бы один раз.

C (S_i), где S_i – некоторый оператор, входящий в программу.

R(P) – упоминаемые (используемые) переменные программы P (множества), называются переменные участвующие при выполнении некоторых операций в программе.

R (S_i) - множество упоминаемых переменных некоторого оператора S_i.

Таким образом, упоминаемые переменные R (P), те, которые используются при вычислении переменных множества C(P).

Если через S_i обозначить некоторый вычислительный блок, R(P) и C(P) могут быть представлены виде:

R(P) ={ x | x

R( ) ={ xⁱ _1, xⁱ _2, xⁱ _{3, … ,} xⁱ _m,}

C(P) ={ y | y

C( ) ={ yⁱ _1, yⁱ _2, yⁱ _{3, … ,} yⁱ _m,},

где n – число операторов в программе Р, в которой выполняются вычисления; m – количество элементов в соответствующих множествах, связанных с _.

C(P) R(P) позволяет изучить все возможные переменные программы.

V(P) = C(P) R(P) V( _i) = C ( _i) R( _i)

Понятие входных переменных в программе

Входные переменные образуют множество I(P), формализуемое в виде:

I(P) ={ | x (x₁, x_{2, …,} x_x-1) , где

n – Количество операторов в программе;

i – Текущая операция.

Множества

Переменная x является используемой (упоминаемой) в операторе _iи ее значение не получено в любом из предшествующих i-му оператору.

Множество входных переменных программы:

O(P) ={ |Y C (S_i+1, S_{i+2 , … ,} S_n)}

Оператор Y должен быть результатом и не изменяться во всех последующих операциях.

I(P)V(P),

O(P)V(P).

Операции (операторы) в программе могут быть связаны различными отношениями зависимости и независимости.

3. Отношениями зависимости и независимости операций

3.1 Непосредственная (сильная) зависимость операций

Оператор S_j называется непосредственно зависимым от оператора S_i (обозначается S_i  S_j, i j ) если:

а). C(S_i)  R(S_j)  0

То есть изменяемые оператором S_i переменные является упоминаемыми (используемыми) в операторе S_j.

б). Нет такой совокупности операторов (операций) S_k1, S_k2, S_k3,…, S_kl

(ik1 k2 k3… kl), для которой при p  i, k1, k2,…, kl ,

g  k1, k2,…, kl, j и pg имело бы место одно из соотношений

C’(S_p)  C(S_g)

То есть изменяемые переменные операции (оператора) S_p не должны входить как подмножество в изменяемые переменные операции S_g – изменяемые переменные исходной операции не могут быть изменены до требуемой (конечной) операции. Имеет место соотношение:

C(S_i)  R(S_j) = (S_kr),

где C’(S_kr) C(S_kr), i kr j, r= , т.е. изменяемые переменные в операции S_i, фигурирующие в качестве используемых (упоминаемых) в операторе S_j, не могут быть изменены промежуточными операторами S_kr).