Схемы и линейные программы
Указанное выше свойство характерно и для программ, в которых один раз вычисленное значение выражения можно использовать неоднократно. Рассмотрим один из простейших классов программ - линейные или неветвящиеся программы. Такие программы представляют последовательности присваиваний вида:
где X, X1, … , Xk - переменные, F - имя k-местной базисной функции.
В случае нашего базиса B0={
Линейная программа 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, вычисляет функцию .
- По каждой линейной программе 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.
Программа PS будет последовательностью m присваиваний.
- Пусть вершина un+i помечена ¬ и в нее входит
- ребро из uj. Тогда в качестве i-ой команды поместим в PS присваивание un+i= ¬ uj.
- Пусть вершина un+i помечена \circ {
,} и в нее входят ребра из uj и uk. Тогда в качестве i-ой команды поместим в PS присваивание un+i= uj ? uk.
Упорядочение вершин по глубине гарантирует, что j <n+ i и k <n+ i. Поэтому при вычислении u_{n+i} значения аргументов уже получены и индукцией по глубине легко показать, что для каждого i=1,…,m программа PS вычисляет в переменной vi функцию
Доказательство пункта (2) проведите самостоятельно (см. задачу 2.1).
Пример 2.1.
Применим конструкцию теоремы к схеме S1, представленной на рис.2.1. Ее вершины можно упорядочить по глубине так: x, y, z, a, b, c, d, e, f. Порождая команды по описанным выше правилам, получим следующую линейную программу P_{S1}:
Замечание. Число команд в линейной программе PS, т.е. время ее выполнения, совпадает со сложностью L(S) схемы S. Глубина схемы D(S) также имеет смысл с точки зрения времени вычисления. Именно, D(S) - это время выполнения PS на многопроцессорной системе. Действительно, все команды, соответствующие вершинам одинаковой глубины, можно выполнять параллельно на разных процессорах, так как результаты любой из них не используются в качестве аргументов другой.