Введение в схемы, автоматы и алгоритмы



     газон некст самосвал |         

Схемы и линейные программы - часть 2


Программа 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 функцию

f_{v_i}(x_1, …, x_n)
.

Доказательство пункта (2) проведите самостоятельно (см. задачу 2.1).

Пример 2.1.

Применим конструкцию теоремы к схеме S1, представленной на рис.2.1. Ее вершины можно упорядочить по глубине так: x, y, z, a, b, c, d, e, f. Порождая команды по описанным выше правилам, получим следующую линейную программу P_{S1}:

a = x \wedge y;\\ b = \neg z; \\ c = \neg a;\\ d = c \wedge z;\\ e =a \wedge b;\\ f =d \vee e

Замечание. Число команд в линейной программе PS, т.е. время ее выполнения, совпадает со сложностью L(S) схемы S. Глубина схемы D(S) также имеет смысл с точки зрения времени вычисления. Именно, D(S) - это время выполнения PS на многопроцессорной системе. Действительно, все команды, соответствующие вершинам одинаковой глубины, можно выполнять параллельно на разных процессорах, так как результаты любой из них не используются в качестве аргументов другой.




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