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


             

v всякий раз увеличивается на


Рассмотрим работу P на исходном состоянии ?, в котором ?(x1)=a, ?(y)=b. При b=0 цикл не выполняется и в результирующем состоянии ?1=P(?) имеем ?1(x1)=?1(?)(x1) =g1(a)= F2(a, 0). При b > 0 цикл будет выполняться b раз, так как в его теле v всякий раз увеличивается на 1, а значение y1=b и не меняется. Перед первым выполнением ?2 все ее рабочие переменные zi равны 0, x1=a, y=0, z=F2(a, 0), а после ее выполнения x1=h3(a,0,F(a,0))=F(a,1). Предположим теперь по индукции, что перед (i+1)-ым выполнением ?2 все ее рабочие переменные zi равны 0, x1=a, y=i и z=F2(a, i). После этого выполнения x1=h3(a,i,z)=h3(a,i,F(a,i))=F(a,i+1). Тогда присваивания z1:=0; … ; zm:=0; v:= v+1 после ?2 и z:=x1; x1:=u1; y:=v; перед ее следующим выполнением установят значения переменных ?2 так, что все ее рабочие переменные zi равны 0, x1=a, y=i+1 и z=F2(a, i+1). Следовательно, после b-го выполнения тела цикла x1=h3(a,b-1,F(a,b-1))=F(a,b).

Минимизация. Предположим, что функция Fn(x1,… ,xn) получена с помощью оператора минимизации (mu-оператора) из функции gn+1(x1,…, xn,y), т.е.



Пусть программа ?1 вычисляет gn+1, так что
, и пусть рабочие переменные ?1 - это z1,…, zm. Зафиксируем переменные x1',… , xn', y';, u, z, не входяшие в
. Рассмотрим следующую программу ?:



Рассмотрим работу ? на входных значених xi = ai (i=1,…,n). В первой строке они сохраняются в переменных x'i, которые нигде в ? не изменяются, z получает значение 0, которое тоже не меняется по ходу вычисления, а u вначале получает значение 1. Поэтому условие цикла после первой строки истинно и он хотя бы один раз выполняется. Докажем, что для каждого i
1, (i+1)-ая итерация цикла выполняется тогда и только тогда, когда g(a1, …, an,0)=b1 >0, …, g(a1, …, an, i-1)=bi-1 > 0, ? останавливается после (i+1)-ой итерации цикла с результатом x1=i тогда и только тогда, когда g(a1, …, an,i)=0. При этом перед выполнением ?1

входные переменные x1,…,xn,y имеют значения a1,…,an, i, соответственно, y'= i, а все рабочие переменные zj (j=1,…, m) равны 0.


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