Схемы и линейные программы

Указанное выше свойство характерно и для программ, в которых один раз вычисленное значение выражения можно использовать неоднократно. Рассмотрим один из простейших классов программ - линейные или неветвящиеся программы. Такие программы представляют последовательности присваиваний вида:

$X = F(X_1, \ldots , X_k),$

где X, X1, … , Xk - переменные, F - имя k-местной базисной функции.

В случае нашего базиса B0={

, ¬} линейная программа состоит из присваиваний вида: Z = X

Y, Z = X

Y и Z = ¬ X.

Линейная программа P с выделенными входными переменными X1, … , Xn

порождает для каждого набора ?1, …, ?n значений входных переменных естественный процесс вычисления: вначале переменным X1, … , Xn присваиваются значения ?1, …, ?n, соответственно, а каждой из остальных переменных присваивается значение 0. Затем последовательно выполняются присваивания программы P, в результате чего каждая из переменных Z программы получит заключительное значение PZ(?1, …, ?n).

Определение 2.6.

Скажем, что программа P со входными переменными X1, … , Xn

вычисляет в выходной переменной Z функцию F(X1, …, Xn), если для любого набора значений входов ?1, …, ?n после завершения работы PZ(?1, …, ?n)=F(?1, …, ?n) .

Между схемами и линейными программами имеется тесная связь.

Теорема 2.1.

По каждой логической схеме S со входами x1, … , xn и функциональными элементами v1, …, vm можно эффективно построить линейную программу PS со входными переменными x1, … , xn и рабочими переменными v1, …, vm, которая в любой переменной vi, i=1,…,m, вычисляет функцию
$f_{v_i}(x_1, \ldots, x_n)$
.
По каждой линейной программе P со входными переменными X1, … , Xn, вычисляющей в выходной переменной Z некоторую функцию F(X1, …, Xn) можно эффективно построить логическую схему SP со входами X1, … , Xn, в которой имеется вершина v такая, что fv((X1, …, Xn) = F(X1, …, Xn).

Доказательство. (1) Пусть S - схема со входами x1, … , xn и функциональными элементами v1, …, vm. Построим по ней линейную программу PS со входными переменными x1, … , xn следующим образом. Упорядочим все входные и функциональные вершины S по глубине (вершины одной глубины в любом порядке): u1, …, un+m.

Содержание Назад Вперед