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

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

В случае нашего базиса линейная программа состоит из присваиваний вида:

Линейная программа с выделенными входными переменными порождает для каждого набора значений входных переменных естественный процесс вычисления: вначале переменным присваиваются значения соответственно, а каждой из остальных переменных присваивается значение ноль. Затем последовательно выполняются присваивания программы , в результате чего каждая из переменных программы получает заключительное значение: .

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

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

Теорема:

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

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

Доказательство:

Пусть – схема со входами и функциональными элементами . Построим по ней линейную программу с входными переменными следующим образом: упорядочим все входные и функциональные вершины по глубине (вершины одной глубины в любом порядке) – . Программа будет последовательностью присваиваний.

Пусть вершина помечена и в неё входит ребро из . Тогда в качестве -й команды поместим в присваивание .

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

Пример:

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